Version 1.2 of ai12s/ai12-0208-1.txt

Unformatted version of ai12s/ai12-0208-1.txt version 1.2
Other versions for file ai12s/ai12-0208-1.txt

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

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

From: Steve Baird
Sent: Tuesday, December 12, 2017  7:20 PM

I thought I'd take a look at how Java and C++ do bignums to see if there are any
ideas there worth incorporating.

My going-in idea is to have two packages with similar specs; one has "Capacity"
discriminants and the other is implemented using dynamic storage allocation of
some sort (e.g., controlled types and allocators). Like the bounded/unbounded
versions of the containers.

C++ doesn't really have a standard for bignums, but the GCC/GMP stuff
looks pretty similar to what I expected.

Java, however, surprised me (note that I am far from a Java expert so it could
be that I am just confused here).

The Java big-real spec doesn't have Numerator and Denominator functions which
yield big-ints.

The Java type seems to be named BigDecimal.

BigDecimal is implemented as a single big-int value accompanied by two ints
(Scale and Precision), at least according to
    stackoverflow.com/questions/10655254/how-bigdecimal-is-implemented

Which leads to my question:
    If Ada defined a spec where the intended implementation for bigreal
    is clearly two bigints (one for numerator, one for denominator),
    would this result in lots of "I coded up the same algorithm in Ada
    and Java and performance was a lot worse in Ada" horror stories?

Apparently BigDecimal lets you have, in effect, a lot of decimal digits but the
value "one third" still cannot be represented exactly.

Why did the Java folks do it that way? It seems like you lose a lot of value if
you can't exactly represent, for example, one third.

But perhaps most folks don't care about that functionality and the
performance/functionality tradeoff chosen by Java is closer to what most folks
want.

Opinions? Opinions about Java are of some interest, but what I really want is
opinions about what we should do in Ada.

p.s. Note that the current plan for this AI is to add one or more new predefined
packages but no changes to language rules. In particular, numeric literals for a
non-numeric type is the topic of another AI.

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

From: Tucker Taft
Sent: Wednesday, December 13, 2017  9:15 AM

We want rational, not decimal, computations, I believe.  So I would ignore
Java's BigDecimal.

A different and interesting capability is true "real" arithmetic, which works
for transcendentals, etc.  It is intriguing, but probably not what people really
want.

I'll send the PDF for an article by Hans Boehm about "real" arithmetic
separately, since it will probably not make it through the SPAM filter!

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

From: Randy Brukardt
Sent: Wednesday, December 13, 2017  10:57 AM

> We want rational, not decimal, computations, I believe.  So I would
> ignore Java's BigDecimal.

Isn't that Steve's question? Ada compiler vendors use rational computations
since that is required by the ACATS (it's necessary that 1/3 /=
0.33333333333333333333333333333). But is that the best choice for the Ada
community? I don't know.

> A different and interesting capability is true "real"
> arithmetic, which works for transcendentals, etc.  It is intriguing,
> but probably not what people really want.
>
> I'll send the PDF for an article by Hans Boehm about "real"
> arithmetic separately, since it will probably not make it through the
> SPAM filter!

It might be too large for the list as well. If so, I can post it in the Grab Bag
if you send it directly to me.

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

From: Edmond Schonberg
Sent: Wednesday, December 13, 2017  1:36 PM

> I'll send the PDF for an article by Hans Boehm about "real" arithmetic
> separately, since it will probably not make it through the SPAM filter!

Both the rational representation and Boehm’s approach require arbitrary
precision integer arithmetic, so the spec of that new package is
straightforward. The papers describing the implementation of Boehm’s approach
claim that it is much more efficient than working on rationals, where numerator
and denominator grow very rapidly, while the other method only computes required
bits. I have no idea whether numerical analysts use this method, From the
literature it seems to be of interest to number theorists.

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

From: Randy Brukardt
Sent: Wednesday, December 13, 2017  4:49 PM

> > It might be too large for the list as well. If so, I can post it in
> > the Grab Bag if you send it directly to me.
>
> It was too big.

By about 4 Megabytes. :-)

Since the article is copyrighted, I put it in the private part of the website.
Find it at:

http://www.ada-auth.org/standards/private/real_arithmetic-boehm.pdf

Ed suggested privately:

> Additional details on the underlying model and its implementation in:
> http://keithbriggs.info/documents/xr-paper2.pdf

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

From: Randy Brukardt
Sent: Wednesday, December 13, 2017  5:10 PM

...
> Both the rational representation and Boehm's approach require
> arbitrary precision integer arithmetic, so the spec of that new
> package is straightforward.
> The papers describing the implementation of Boehm's approach claim
> that it is much more efficient than working on rationals, where
> numerator and denominator grow very rapidly, while the other method
> only computes required bits. I have no idea whether numerical analysts
> use this method, From the literature it seems to be of interest to
> number theorists.

The problem with the Boehm method is that it requires specifying those "required
bits", which seems problematic in a programming environment. One could do it
with a form of type declaration (Ada's "digits" seems to be the right general
idea), but that doesn't make much sense in a library form. Boehm's actual use
gets those on the fly (by interacting with the user), and they also use a
rational representation as a backup. So it seems that a rational representation
is going to show up somewhere.

I've repeatedly had the fever dream of a class-wide bignum base type, something
like:

      package Root_Bignum is
          type Root_Bignum_Type is abstract tagged null record;

          function Bignum (Val : in Long_Float) return Root_Bignum_Type is abstract;
          -- To get the effect of literals and conversions.

          function "+" (Left, Right : in Root_Bignum_Type) return Root_Bignum_Type is abstract;
          -- And all of the rest.

          function Expected_Digits return Natural is abstract;
              -- The number of digits supported by this type; 0 is returned
              -- if the number is essentially infinite.

          -- And probably some other queries.
      end Root_Bignum;

And then there could be multiple specific implementations with different
performance characteristics, everything from Long_Float itself thru infinite
rational representations.

This would allow one to create most of the interesting algorithms as class-wide
operations (with implementations that could adjust to the characteristics of the
underlying type), for instance:

   function Sqrt (Val : in Root_Bignum_Type'Class;
                  Required_Digits : Natural := 0) return Root_Bignum_Type'Class;

Here with "Required_Digits" specifies how many digits of result are needed.
If 0, the value would be retrieved from the underlying representation.
(Probably have to raise an exception if that gives "infinite".)

Such a layout would also allow easy changing of representations, which probably
would be needed for tuning purposes (most of these maths being slow, at least by
conventional standards).

This would have the clear advantage of avoiding being locked into a single form
of Bignum math, when clearly there are other choices out there useful for
particular purposes.

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

From: Randy Brukardt
Sent: Wednesday, December 13, 2017  5:25 PM

I said:
...
> The problem with the Boehm method is that it requires specifying those
> "required bits", which seems problematic in a programming environment.

but then also noted:

>           function Sqrt (Val : in Root_Bignum_Type'Class;
>                          Required_Digits : Natural := 0) return
> Root_Bignum_Type'Class;

essentially, recognizing that many non-terminating algorithms have to have some
sort of termination criteria.

For ease of use purposes, one would prefer to only specify numbers of digits if
they're really needed (as in Sqrt or PI, etc.). But if there are going to be a
lot of such operations, one would want to be able to specify that once. Hope
that explains my thinking here.

Also, a Bignum library needs a corresponding Text_IO library. And probably a
custom version of GEF. (The Janus/Ada compiler library has most of these
features, and they are used extensively.)

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


Questions? Ask the ACAA Technical Agent