Toward an API for the real numbers

10052020, 01:19 AM
Post: #1




Toward an API for the real numbers
Thought this (and the ACM paper referenced) might be of interest here..
https://blog.acolyer.org/2020/10/02/towa...lnumbers/ 

10052020, 03:13 AM
Post: #2




RE: Toward an API for the real numbers
(10052020 01:19 AM)Bill Duncan Wrote: Thought this (and the ACM paper referenced) might be of interest here.. Nice find. Thanks for sharing. Quote:Results don’t display as users expect, for example using IEEE double precision and Java output formatting rules, 0.1 + 0.7 = 0.77999999999999999, and not the expected 0.8. Most calculators and spreadsheets are programmed with BCD instead of IEEE754 for many reasons, including these obvious issues. There isn't anything inherently surprising here. I don't understand the rationale of this API. The application that started the work on the API was a calculator, which can use any available libraries and general knowledge that exists to get this right. This work sounds more of an excuse to look for a reason to fix (or hide) their calculator bugs with a new shiny API to assign properties to numbers. Seems that they found out that a calculator is not just a trivial piece of Java code to operate on IEEE754 floats and doubles (with accurate rationals represented in other ways e.g. a pair of bigint.) Quote:"To our knowledge, this is the first exploration of a practical general purpose real number type that both reflects the mathematical laws of the real numbers, and also supports exact comparisons in situations in which that’s normally expected." That is quite a claim with a dose of arrogance. First off all, one has to be careful using the phrase "real numbers" (not in general constructible) versus floating point (rationals, constructible). Secondly, uniformly representing and implementing operations and comparisons on floating point, rationals, and irrationals (typically pi, e, and sqr2) isn't new. Thirdly, algebraic laws generally don't hold on floating point so claiming that the API "reflects the mathematical laws of real numbers" is sketchy, see e.g. "What every computer scientist should know about floatingpoint arithmetic" https://dl.acm.org/doi/10.1145/103162.103163 "I can count on my friends"  HP 71B,PrimeTi VOY200,Nspire CXII CASCasio fxCG50...Sharp PCG850,E500,2500,1500,14xx,13xx,12xx... 

10052020, 04:36 PM
Post: #3




RE: Toward an API for the real numbers
Also "How to print floating point numbers accurately" by Steele and White from 1990 ACM SIGPLAN
"Isn’t it a pain when you ask a computer to divide 1.0 by 10.0 and it prints 0.0999999? Most often the arithmetic is not to blame, but the printing algorithm." Abstract: We present algorithms for accurately converting floatingpoint numbers to decimal representation. The key idea is to carry along with the computation an explicit representation of the required rounding accuracy. We begin with the simpler problem of converting fixedpoint fractions. A modification of the wellknown algorithm for radixconversion of fixedpoint fractions by multiplication explicitly determines when to terminate the conversion process; a variable number of digits are produced. The algorithm has these properties: * No information is lost; the original fraction can be recovered from the output by rounding. * No “garbage digits” are produced. * The output is correctly rounded. * It is never necessary to propagate carries on rounding. We then derive two algorithms for freeformat output of floatingpoint numbers. The first simply scales the given floatingpoint number to an appropriate fractional range and then applies the algorithm for fractions. This is quite fast and simple to code but has inaccuracies stemming from roundoff errors and oversimplification. The second algorithm guarantees mathematical accuracy by using multipleprecision integer arithmetic and handling special cases. Both algorithms produce no more digits than necessary (intuitively, the “1.3 prints as 1.2999999” problem does not occur). Finally, we modify the freeformat conversion algorithm for use in fixedformat applications. Information may be lost if the fixed format provides too few digit positions, but the output is always correctly rounded. On the other hand, no “garbage digits” are ever produced, even if the fixed format specifies too many digit positions (intuitively, the "4/3 prints as 1.333333328366279602” problem does not occur). 

10052020, 07:24 PM
Post: #4




RE: Toward an API for the real numbers  
10062020, 01:16 AM
Post: #5




RE: Toward an API for the real numbers
(10052020 07:24 PM)Wes Loewer Wrote:(10052020 03:13 AM)robve Wrote: Most calculators and spreadsheets are programmed with BCD instead of IEEE754 SuperCalc initially used BCD but switched to binary. Also Microsoft Multiplan (later replaced by Excel) used BCD. Newer spreadsheet software does not, at least I am not aware of any. Obviously the battle for "sheet speed" was won by binary floating point, especially with the arrival of math coprocessors and later with CPUs supporting IEEE754 floating point operations. In the (distant) past, floating point was done in software, so perhaps the overhead of BCD wasn't a significant factor to consider anyway. But BCD did produce accurate decimals that were especially important for financial calculations. One dollar and cent is exactly $1.01, not some number close to $1.01. Imagine repeatedly adding $0.01 in a loop (or a recursive spreadsheet cell formula) in which the error accumulates. Before the arrival of IEEE754, floating point representations and operations were not as well designed, producing artifacts and roundoff errors. Dealing with that was tricky, so BCD was deemed safer. That's changed with the IEEE754 standard that's carefully designed. William Kahan, the “father” of IEEE754 floating point, said in 1998: "My reasoning was based on the requirements of a mass market: A lot of code involving a little floatingpoint will be written by many people who have never attended my (nor anyone else's) numerical analysis classes. We had to enhance the likelihood that their programs would get correct results. At the same time we had to ensure that people who really are expert in floatingpoint could write portable software and prove that it worked, since so many of us would have to rely upon it. There were a lot of almost conflicting requirements on the way to a balanced design." "I can count on my friends"  HP 71B,PrimeTi VOY200,Nspire CXII CASCasio fxCG50...Sharp PCG850,E500,2500,1500,14xx,13xx,12xx... 

10072020, 01:35 PM
Post: #6




RE: Toward an API for the real numbers
I imagine this is why MS created the new decimal type:
https://docs.microsoft.com/enus/dotnet/...cimaltype but AFAIK, Excel does not use it. 

10072020, 05:40 PM
Post: #7




RE: Toward an API for the real numbers
(10072020 01:35 PM)KeithB Wrote: but AFAIK, Excel does not use it. Yes, sure Excel uses doubles. MS early on advertised Excel as the fastest spreadsheet software for IBM PC and hence the battle was for speed rather than "decimal accuracy" of BCD when used in financial calculations. I should have been a bit more careful by stating "some of the early spreadsheet software used BCD". A quick demo in Excel: Enter 1.01 in cell A1 Enter =A1+0.001 in cell A2 Copy cell A2 to cells A3A100 Format column A to 14 decimal places Cells A47 to A100 show 1.05599999999999 to 1.10899999999999 It's sad that VisiCalc is largely forgotten as the first spreadsheet invention. Everything that came after is an incremental improvement. VisiCalc was implemented by programmers that were familiar with COBOL. For "business computing reasons", COBOL used packet BCD. "I can count on my friends"  HP 71B,PrimeTi VOY200,Nspire CXII CASCasio fxCG50...Sharp PCG850,E500,2500,1500,14xx,13xx,12xx... 

10072020, 08:58 PM
Post: #8




RE: Toward an API for the real numbers
(10072020 05:40 PM)robve Wrote: A quick demo in Excel: My goto demo for things like this is (4/31)*31. The result indicates the base and the precision used. 1e11 Prime Home 2^46 Prime CAS (nonexact) 1e13 TI Nspire (nonexact) 2^52 Google Sheets, LibreOffice [requires RAWSUBTRACT], Excel [requires redundant parenthesis ((4/31)*31) ] +2^63 Lotus Improv (1990's, coolest spreadsheet ever) 

10082020, 03:26 AM
Post: #9




RE: Toward an API for the real numbers
It's an interesting approach. It still boils down to deceiving the user about results. Albeit, it is giving "good" approximations.
E.g. it seems like it only deals with single transcendental functions. Something like log(log(x)) would throw it off. I think, that by maintaining an expression tree, results could be extended ondemand to whatever precision is required to get a "correct" answer. The memory use could get large since real numbers would never be stored. Pauli 

10082020, 01:07 PM
Post: #10




RE: Toward an API for the real numbers
(10082020 03:26 AM)Paul Dale Wrote: It's an interesting approach. It still boils down to deceiving the user about results. Albeit, it is giving "good" approximations. Can you elaborate what is the "interesting approach" ? From what I've read, this API seems able to do whole expression, returning correctly rounded results. I were thinking it does calculations like spigot, a commandline exact real calculator All digits it returns guaranteed correct (the down side, take lots of time, sometimes literally stuck) Lets try first example from Why and how to use arbitrary precision >spigot printf="%.34g" "173746*sin(1e22) + 94228*log(17.1)  78487*exp(0.42)" 1.341818957829619549704278684230959e12 Free42Decimal, RAD mode: 1e22 SIN 173746 × → 148066.4888436499855528005582160138 17.1 LN 94228 × + → 119454.1966158397094008651162133881 0.42 EXP 78487 × → 119454.1966158397107426840740430076  → 0.0000000000013418189578296195 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)