Toward an API for the real numbers

[Bill Duncan]

Thought this (and the ACM paper referenced) might be of interest here..

https://blog.acolyer.org/2020/10/02/towa...l-numbers/

[robve]

(10-05-2020 01:19 AM)Bill Duncan Wrote:  Thought this (and the ACM paper referenced) might be of interest here..

https://blog.acolyer.org/2020/10/02/towa...l-numbers/

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 floating-point arithmetic" https://dl.acm.org/doi/10.1145/103162.103163

[KeithB]

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
floating-point 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
fixed-point fractions. A modification of the well-known
algorithm for radix-conversion of fixed-point 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 free-format output
of floating-point numbers. The first simply scales
the given floating-point 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 round-off errors and oversimplification.
The second algorithm guarantees mathematical
accuracy by using multiple-precision 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 free-format conversion algorithm
for use in fixed-format 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).

[Wes Loewer]

(10-05-2020 03:13 AM)robve Wrote:  Most calculators and spreadsheets are programmed with BCD instead of IEEE754

Can you give an example of a spreadsheet program that uses BCD? All the computer spreadsheets that I'm aware of use binary. Maybe I'm just not aware of the right ones.

[robve]

(10-05-2020 07:24 PM)Wes Loewer Wrote:  

(10-05-2020 03:13 AM)robve Wrote:  Most calculators and spreadsheets are programmed with BCD instead of IEEE754

Can you give an example of a spreadsheet program that uses BCD? All the computer spreadsheets that I'm aware of use binary. Maybe I'm just not aware of the right ones.

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 IEEE-754 floating point, said in 1998:
"My reasoning was based on the requirements of a mass market: A lot of code involving a little floating-point 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 floating-point 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."

PS. (edit) interesting fact: the Sharp Wizard 3D spreadsheet cards IQ-706A and IQ-8B04(M) use BCD. The spreadsheet card is Lotus-123/Lucid 3D compatible.

[KeithB]

I imagine this is why MS created the new decimal type:
https://docs.microsoft.com/en-us/dotnet/...cimal-type

but AFAIK, Excel does not use it.

[robve]

(10-07-2020 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 A3-A100
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.

[Wes Loewer]

(10-07-2020 05:40 PM)robve Wrote:  A quick demo in Excel:

My go-to demo for things like this is (4/3-1)*3-1. The result indicates the base and the precision used.

-1e-11 Prime Home
-2^-46 Prime CAS (non-exact)
-1e-13 TI Nspire (non-exact)

-2^-52 Google Sheets, LibreOffice [requires RAWSUBTRACT], Excel [requires redundant parenthesis ((4/3-1)*3-1) ]
+2^-63 Lotus Improv (1990's, coolest spreadsheet ever)

[Paul Dale]

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 on-demand to whatever precision is required to get a "correct" answer. The memory use could get large since real numbers would never be stored.


Pauli

[Albert Chan]

(10-08-2020 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.

E.g. it seems like it only deals with single transcendental functions. Something like log(log(x)) would throw it off.

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 command-line 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.341818957829619549704278684230959e-12

Free42-Decimal, RAD mode:

1e22 SIN 173746 ×     → -148066.4888436499855528005582160138
17.1 LN 94228 × +     →  119454.1966158397094008651162133881
0.42 EXP 78487 ×      →  119454.1966158397107426840740430076
-                     →      -0.0000000000013418189578296195