!standard A.20(0) 16-12-19 AI12-0208-1/00 !class Amendment 16-12-19 !status work item 16-12-19 !status received 16-09-27 !priority Low !difficulty Medium !subject Predefined bignum support !summary Define a "bignum" package. [Editor's note: I surely hope that we have a better name for it than "bignum", which is as non-Ada a name as possible (two words with no underscore and an unnecessary abbreviation.] !problem Some applications need larger numbers than Standard.Integer. All Ada compilers have this capability in order to implement static expressions; shouldn't some such package be available to Ada users as well? (Yes.) !proposal (See Summary.) !wording ** TBD **. !discussion !ASIS No ASIS effect (assuming this is ONLY a library). !ACATS test An ACATS C-Test is needed to check that the new capabilities are supported. !appendix From: Steve Baird Sent: Tuesday, September 27, 2016 4:09 PM professor at U. of Utah: blog.regehr.org/archives/1401 Regehr says: In most programming languages, the default integer type should be a bignum: an arbitrary-precision integer that allocates more space when needed. Efficient bignum libraries exist and most integers never end up needing more than one machine word anyway, except in domains like crypto. Nobody is suggesting changing how Standard.Integer works for Ada, but a language-defined Bignum package (presumably supporting Rationals as well as Integers) would be a step in the right direction. It seems like the same arguments which were used (correctly, IMO) to justify adding predefined container packages to the language also apply here. As Tuck phrased it in a private message: portability and more capability "out of the box." Does some de facto standard already exist? **************************************************************** From: Bob Duff Sent: Tuesday, September 27, 2016 4:32 PM > Nobody is suggesting changing how Standard.Integer works But somebody might suggest that things like "type T is range 1..10**100;" should be supported by all Ada compilers. > It seems like the same arguments which were used (correctly, IMO) to > justify adding predefined container packages to the language also > apply here. As Tuck phrased it in a private message: > portability and more capability "out of the box." Plus the fact that all Ada compilers have to support that functionality at compile time, but can't provide it to their users in a portable way at run time. > Does some de facto standard already exist? For C and C++, yes. For Ada, no. For Common Lisp, Java, C#, and many others, a de jure standard exists. **************************************************************** From: Randy Brukardt Sent: Wednesday, September 28, 2016 12:49 PM > Does some de facto standard already exist? No. I could be convinced to contribute RR's Univmath package as a starting point for discussion. **************************************************************** From: Jean-Pierre Rosen Sent: Thursday, September 29, 2016 12:22 AM There are several packages available, see http://bignumber.chez.com/index.html **************************************************************** From: Randy Brukardt Sent: Thursday, September 29, 2016 12:28 PM Surely, like containers there are as many Bignum packages as there are Ada programmers (much like containers - everybody has one). But is someone putting them into RM format?? That's what it means to "contribute" a package here. **************************************************************** From: John Barnes Sent: Thursday, September 29, 2016 2:05 PM I see there has been chatter on big number packages. I wrote such a package many years ago. I was intending to write a book called Fun with Ada using big examples of Ada 83 programs. But it got overtaken by events such as having to write the book on Ada 95. But I kept the package, used some child stuff from Ada 95 but otherwise left it alone, I still use it for dabbling with large prime numbers and so on. I think it is based on base 10,000 which will run on a 16 bit machine and is easy for conversion for printing. But I fear that agreeing on something might be tricky. **************************************************************** From: Florian Schanda Sent: Friday, September 30, 2016 2:35 AM > But I kept the package, used some child stuff from Ada 95 but > otherwise left it alone, I still use it for dabbling with large prime > numbers and so on. I think it is based on base 10,000 which will run > on a 16 bit machine and is easy for conversion for printing. Generally, these days, you would probably want to stick to largest power-of- two as printing these is not a massive concern but performance is. :) Anyway, I think whatever we come up with, it should be possible to implement it via a binding to GMP [https://gmplib.org] which is more or less the gold standard for arbitrary precision arithmetic. Of course, some runtime may wish to have a more verifiable implementation... So, I think there are two requirements we should make sure to fulfil: 1. the api should be amenable to static analysis and formal verification 2. the api should make it easy to bind to gmp (Not saying this list is exhaustive.) I just want to avoid people starting from various in-house and private projects; its probably a good idea instead to start from established libraries. **************************************************************** From: Steve Baird Sent: Friday, September 30, 2016 12:27 PM > So, I think there are two > requirements we should make sure to fulfil: > > 1. the api should be amenable to static analysis and formal verification > 2. the api should make it easy to bind to gm It is also at least possible that we'll want something similar to what we have with the containers, where we have one version for use in situations where controlled types and dynamic storage allocation are ok and another for use in other situations. **************************************************************** From: Jean-Pierre Rosen Sent: Friday, September 30, 2016 2:44 PM Hmmm... bounded and unbounded bignums? **************************************************************** From: Tucker Taft Sent: Friday, September 30, 2016 3:52 PM Perhaps: "big enough nums, already..." ****************************************************************