4
$\begingroup$

In programming languages like Haskell you can use lazy evaluation to delay calculations.

Why isn't a similar approach being used for numerical methods (I understand that there would be memory implications).

The approach would be that non-integer values would be stored as how they are calculated, so that the next digit can be found when requested.

This kind of approach should allow every value to be calculated to the correct number of significant figures.

Sorry that this is slightly garbled.

$\endgroup$
2
$\begingroup$

A similar approach is used, and in Haskell! Here is a page with some references:

https://wiki.haskell.org/Exact_real_arithmetic

Great minds think alike. As David Richerby notes, exact computation on reals is astronomically slower than with machine-backed floats, which are probably here to stay.

See also this question:

https://cstheory.stackexchange.com/questions/32011/computation-of-reals-floating-point-vs-tte-vs-domain-theory-vs-etc

$\endgroup$
6
$\begingroup$

It sounds extremely inefficient compared to floating point. We have a very good understanding of how to control the errors in floating-point calculations (e.g., adding small numbers before large ones, avoiding taking the difference of large numbers and so on) so the only benefit of the methods you're suggesting would appear to be that they offer increased precision. But, for almost all applications, 64-bit floating point is more than enough and the speed of being able to do calculations with single CPU (or GPU!) instructions is a huge win.

$\endgroup$
  • $\begingroup$ It might be useful to note just how much of a win: 2-3 orders of magnitude even for simple calculations is typical. $\endgroup$ – cody May 16 '17 at 21:44
4
$\begingroup$

This probably isn't exactly what you're looking for, but perhaps nevertheless interesting.

There have been proposals for different kinds of computables, for example these by Bill Gosper: Continued Fraction Arithmetic (hardware support is described at the bottom, for Continued Logarithms).

Doing calculations in software with continued fractions has seen many implementations, though they frequently have trouble computing anything that results in an exact integer, evaluating an infinite number of terms in an attempt to find the next digit but never finding anything because the number "ended", a condition which is impossible to test for with "black box" generators (which has a strong "neatness" appeal): given two black boxes that just happen to represent the same infinite CF, there is no way to tell whether they're actually the same or diverge after the billionth term. Lazily generated infinite lists of digits have the same problem and, on top of that, have to be actually infinite more often than CFs (which can represent anything in $\mathbb{Q}$ with finitely many terms).

Apart from that, such symbolically-represented CFs suffers the more obvious problem that building up a big computation symbolically takes a lot of memory, and evaluating a big structure is inherently slow. The slowness can be mitigated to some extend by "merging" the main calculation "boxes" when possible. Eg (x + 3)(y + 4) / (x - y) can be evaluated with one "box", which can be computed from the "boxes" that implement the sub-expressions, but even if everything merges down to one "box", each merge is slower than a typical hardware-implemented floating point operation and there's the final evaluation to worry about too.

It is possible to speed it up by periodically converting the symbolic representation to an approximate explicit one, but then it loses most of the appeal - both the exactness (even for rationals!) and the lazyness are sacrificed, leaving behind something that doesn't seem so interesting anymore.

The Continued Logarithms proposed by Gosper have even been implemented in hardware, though as far as I know it has never become more than a curiosity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.