Decimal expansions using lazy sequences in Clojure

Question

Is there a package which represents decimal expansions in Clojure using lazy sequences?

For example, syntax like

(defn r `(B N x_1 x_2 x_3 ...))

could represent a real number r in base B, with decimal expansion (in math notation)

r = N . x_1 x_2 x_3 ...

with integer significand N and decimal digits 0 ≤ x_i ≤ B-1.

If the type were "smart" enough, it could handle different decimal expansions of real numbers as valid inputs, such as (10 0 9 9 9 ...) and (10 1), and consistently output decimal expansions in the latter form. It should also be able to handle overflowing digits, like reducing (10 0 15) to (10 1 5).

Is there any obstruction to working with a lazy-sequence representation of real numbers instead of the usual decimal expansion? I don't know how efficient it would be in contrast to floating-point, but it would be convenient for doing rigorous precise arithmetic involving real numbers. For example, I think there are algorithms which recursively compute the decimal expansions of π and e.

Answer 1

TL;DR

The short answer is that no, there is no such library and I doubt that there will ever be one. It is possible to compute numbers to accuracy greater than IEEE double precision, but to do so by representation as a sequence of single digits is immensely wasteful in terms of memory and impossible to do entirely lazily in general case. For instance, compute (+ '(0 9 0 ... ) '(0 9 1 ...)) lazily by terms.

The Long Version

When "computing" (approximating) the value of a real number or expression to machine precision, the operation computed is the taylor series expansion of the desired expression to N terms, until that the value of the N+1th term is less than machine precision at which point the approximation is aborted because the hardware convention cannot represent more information.

Typically you will only see the 32 and 64 bit IEEE floating point standards, however the IEEE floating point specification extends out to a whopping 128 bits of representation.

For the sake of argument, let's assume that someone extends clojure.core.math to have some representation arbitrary-precision-number, being a software floating point implementation against a backing ByteArray which through a protocol appears for all intents and purposes to be a normal java.lang.Number. All that this representation achieves is to push the machine epsilon (representational error limit) out even lower than the 5x10e-16 bound offered by IEEE DOUBLE/64. Building such a software floating point system is entirely viable and relatively well explored. However I am not aware of a Java/Clojure implementation thereof.

True arbitrary precision is not possible because we have finite memory machines to build upon, therefore at some point we must compromise on performance, memory and precision. Given some library which can correctly and generally represent an arbitrary taylor series evaluation as a sequence of decimal digits at some point, I claim that the overwhemling majority of operations on such arbitrary numbers will be truncated to some precision P either due to the need to perform comparison against a fixed precision representation such as a float or double because they are the industry standards for floating point representation.

To blow this well and truly out of the water, at a distance of 1 light-year an angular deviation of 1e-100 degrees would result in a navigational error of approximately 1.65117369558e-86 meteres. This means that the existing machine epsilon of 5x10e-16 with IEEE DOUBLE/64 is entirely acceptable even for interstellar navigation.

As you mentioned computing the decimal terms of Pi or other interesting series as a lazy sequence, here one could achieve headway only because the goal is the representation and investigation of a series/sequence rather than the addition, subtraction, multiplication and soforth between two or more such representations.