--- 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