Arbitrary precision - two or three approaches

[EdS2]

Most calculators, and even most calculator apps, have some specific precision, often a number of decimal digits, and typically they will have a few extra digits to hide most rounding errors...

... but it's possible to do better, to offer precision limited only by memory, at the cost of some performance, and some extra effort.

This video discusses an app for Android which allows scrolling to keep fetching up more digits:
Google's ingenious variable-precision Calculator app

From the description:

Quote:This video is about an under-appreciated feature of Google's standard Calculator app on Android.

The Google Calculator supports an exact arithmetic variable-precision engine that always displays full and correct results. The user can swipe results to see digits that are always accurate and never rounded.

This arithmetic engine was created by Hans-J. Boehm:
- https://hboehm.info/

There is an high level article in Communications of the ACM about how the arithmetic engine was implemented:
- Small-Data Computing: Correct Calculator Arithmetic
by Hans-J. Boehm

There is also a detailed technical paper about it here:
- Towards an API for the Real Numbers, Hans-J. Boehm, 15 pages)

I think I'm right in saying Boehm describes two different approaches in those two articles: the more detailed paper is from 2020.

As another offering, Simon Tatham has written a command line calculator, like the venerable bc, but offering arbitrary precision by use of spigot algorithms:
spigot : an exact real calculator
(It's open source.)

For interest, see particularly Chapter 5: Hazards to computation.

It might be that the microcontrollers used, for example, by Swiss Micros could support something like these approaches - as much precision as memory allows, with some interface which allows the user to get a useful result quickly and more digits on demand.

[robve]

Fascinating stuff.

It's great to have a calculator compute the digits of pi ad infinitum and any other interesting formulas we throw at it.

But in the real physical world quantities are derived from observations that have some level of noise and measurement errors. However small that error might be, it's never zero.

The smallest possible size of anything in the universe is the Planck Length \( 1.6 10^{-35}m \). The visible universe is 46.508 billion light years. Times \( 9.461 10^{15}m \) gives \( 4.4 10^{26}m \). So anything in the visible universe, its size, position, energy and so on requires no more than 61 digits (26+35). Just a quick back-of-the-envelope estimate. I didn't look it up. I could be off (disclaimer!). For example, if we need to exactly represent the center of a subatomic particle on Betelgeuse at an instant of time and measured without noise and no quantum effect (no spooky things), then less than 61 digits will do.

I want a quantum calculator that can calculate spooky things

Wait, aren't those not already available as a true RNG?

- Rob

[Joe Horn]

A huge THANK YOU to EdS2 for bringing the "Spigot" program to our attention. WOW, what a blast to play with! And it really tickles my toes because it's based on two of my absolute favorite things in the world: (1) Jeremy Gibbons' "Unbounded Spigot Algorithm for the Digits of Pi" (enhanced to support more inputs and functions), and (2) William Gosper's famous HAKMEM Memo 239 which gives algorithms for doing basic arithmetic on continued fractions. My heart skipped a beat when I read that description in the Spigot documentation.

If any other members here like to play with numbers like I do, and haven't given the Spigot program a try, I highly recommend it. The documentation is lengthy but well worth the time it takes to read it.

Thanks again, EdS2!

[Paul Dale]

(06-03-2022 08:06 PM)robve Wrote:  So anything in the visible universe, its size, position, energy and so on requires no more than 61 digits (26+35).

I want to measure volumes


Pauli

[Paul Dale]

I've seen a few arbitrary precision packages over the years. One that sticks in my mind was done in Haskell, sadly I don't remember it's name. The premise was that a number was represented as a sequence and whenever more digits were required, the sequence was extended until the desired digit values could be guaranteed to be correct. Want more digits later, keep extending.

Being Haskell and having lazy evaluation, it essentially built an expression tree for the computation and when more digits were required, potentially all the the nodes in the tree could be extended. Pretty neat idea but very memory intensive.


Pauli

[robve]

(06-07-2022 11:19 PM)Paul Dale Wrote:  I've seen a few arbitrary precision packages over the years. One that sticks in my mind was done in Haskell, sadly I don't remember it's name. The premise was that a number was represented as a sequence and whenever more digits were required, the sequence was extended until the desired digit values could be guaranteed to be correct. Want more digits later, keep extending.

Being Haskell and having lazy evaluation, it essentially built an expression tree for the computation and when more digits were required, potentially all the the nodes in the tree could be extended. Pretty neat idea but very memory intensive.

You mean this paper? https://link.springer.com/chapter/10.100...49498-1_16

Lazy evaluation (NOR+WHNF+sharing+lazy constructors to be precise) can make on-demand infinite precision elegant to implement e.g. in Haskell, Gofer, Miranda, etc.

So-called "arbitrary precision" packages are typically not producing digits on demand ad infinitum. Perhaps some package names may suggest otherwise, such as uLisp's "infinite precision arithmetic" package, which is a bignum package.

- Rob

[EdS2]

Great to hear your enthusiasm Joe! I too have been very engaged by Gibbons' work and nearby related algorithms.

Cheers
Ed

(06-07-2022 11:08 PM)Joe Horn Wrote:  A huge THANK YOU [...] WOW, what a blast [...] really tickles my toes [...]

If any other members here like to play with numbers like I do, and haven't given the Spigot program a try, I highly recommend it. The documentation is lengthy but well worth the time it takes to read it.

Thanks again, EdS2!