!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..."

****************************************************************