CVS difference for ai12s/ai12-0208-1.txt

Differences between 1.1 and version 1.2
Log of other versions for file ai12s/ai12-0208-1.txt

--- ai12s/ai12-0208-1.txt	2016/12/20 00:40:53	1.1
+++ ai12s/ai12-0208-1.txt	2017/12/20 04:49:57	1.2
@@ -192,3 +192,225 @@
 
 ****************************************************************
 
+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