Understanding Float>>asFraction and its variants

Question

I'm currently puzzling over the response provided by the class method Float>>asFraction and its various forms. Here are a few examples:

GNU Smalltalk

0.001 asFraction
1/1000
0.001 asExactFraction
1152921504606847/1152921504606846976

Pharo

0.001 asFraction
1152921504606847/1152921504606846976
0.001 asTrueFraction
1152921504606847/1152921504606846976
0.001 asMinimalDecimalFraction
1/1000
0.001 asApproximateFraction
1/1000

For obvious reasons, GNU's asFraction and Pharo's asMinimalDecimalFraction and asApproximateFraction make the most sense to me since they are producing, mathematically, more "exact" results. I don't understand the others. Why would a fraction with large numerator and denominator but with clearly a less exact value be the response to asExactFraction? Why would I want that kind of response? Why in Pharo does it not seem to matter whether I choose asFraction or asTrueFraction? Why are there these variants?

If I want representation of a float as a fraction, I would think I'd want the closes approximation based perhaps upon the precision class of the integers that form the numerator and denominator, or perhaps based upon a maximum denominator.

I looked in the Bluebook and it says very little about asFraction and mentions no variants.

Answer 1

A Float is a data structure that codifies a number, which regardless of how we see or interpret it, mathematically speaking, cannot be anything but a rational quantity (i.e., an integer or fraction). This codification is appropriate for arithmetic operations, which the CPU performs at high speed. The price we pay is that the codification doesn't exhibit the numerator and denominator it represents. The method Float >> #asTrueFraction answers with these numbers, in other words, it decodes the bits enclosed in the instance of Float, and answers with the actual fraction it codifies.

What you have to understand is that when you write 0.001 you are telling the Compiler to create a Float that approximates the fraction 1/1000. Had the CPU used decimal rather than binary representations, this would have been similar to asking it to codify 1/3 using a finite number of decimal places, which leads irrevocably to 0.33333..3, for some maximum number of digits 3. In the case where the denominator is not a power of 2, the CPU has to solve a similar problem and ends up approximating the provided quantity so that it fits in the number of bits allocated to Floats. The method #asTrueFraction reverses that process and reveals the exact value of the approximation, which Float hides behind the way it prints its instances.

In Pharo, Float >> #asFraction is the same as Float >> #asTrueFraction, so no difference there.

The comment in Float >> #asMinimalDecimalFraction is very clear, it will give what you usually expect, this is, the shortest decimal Fraction that will equal self when converted back asFloat.

Finally, Float >> #asApproximateFraction uses some algorithm to produce an acceptable approximation of the receiver.

Answer 2

For obvious reasons, GNU's asFraction and Pharo's asMinimalDecimalFraction and asApproximateFraction make the most sense to me since they are producing, mathematically, more "exact" results.

On the contrary, the operation they perform is to find an approximation to the input. But the input they receive is not, in fact, the number 0.001, even though that seems to be what you wrote—and there is no way for any of these methods to know what you originally wrote.

So some of the methods return exactly the number they are given (in different representation), while others return approximations that fortuitously (if confusingly!) coincide with the text you originally wrote.

---

It might help to rephrase the code a little bit so you see where the approximations are realy happening. Let's focus on GNU Smalltalk first.

x := '0.001' asNumber.
y := x asExactFraction.

In this fragment, '0.001' asNumber is the only operation that does any approximation: instead of returning a Float instance representing the number 0.001 (there is, in fact, no such float!), it returns a Float representing the nearest (IEEE 754 binary64) floating-point number, which can be variously written as 1152921504606847/1152921504606846976, or as 0.001000000000000000020816681711721685132943093776702880859375, or as 0x1.0624dd2f1a9fcp−10 in the most convenient form for writing binary floating-point numbers exactly.

You get the same result by just writing 0.001: Smalltalk will automatically round to the nearest floating-point number. I write it explicitly as '0.001' asNumber to make it clear that this is the operation that returns an approximation to the number 0.001 you wrote.

Then y := x asExactFraction sets 𝑦 to a Fraction instance representing exactly the same number; likewise with y := x asTrueFraction in Pharo. The number is still 1152921504606847/1152921504606846976; asExactFraction will never return a number with anything but a power of two in the denominator (at least, not with a class for storing binary floating-point numbers).

---

If, instead, you evaluate (in GNU Smalltalk)

z := x asFraction.

then what you get in 𝑧 is a Fraction instance representing the simplest rational number that rounds to 𝑥—very roughly, the simplest rational number in the interval [𝑥 − ulp(𝑥)/2, 𝑥 + ulp(𝑥)/2], where ulp(𝑥) ≈ 2⁻⁵²𝑥 is the magnitude of the least significant digit of the floating-point representation of 𝑥 (with caveats around the edges of the intervals and when 𝑥 is equal to a power of two). Here the “simplest” rational number within an interval is the rational number with the smallest denominator. This approximation to 𝑥 is obtained by expanding the continued fraction representation of 𝑥 until the first convergent that rounds to 𝑥.¹

This is probably (though I haven't looked closely enough to verify) the same as what you get with Pharo's definition of asApproximateFraction. In contrast, Pharo's asMinimalDecimalFraction doesn't return the simplest rational; instead, it considers only rational numbers with powers of 10 = 2⋅5 in the denominator, and returns the one with the smallest numerator that will be rounded to 𝑥.

---

In summary:

• x := '0.001' asNumber sets 𝑥 to a Float instance representing the (IEEE 754 binary64) floating-point number nearest to 0.001, which is 1152921504606847/1152921504606846976 = 0.001000000000000000020816681711721685132943093776702880859375 = 0x1.0624dd2f1a9fcp−10; you get the same effect by writing x := 0.001 but that makes it a little more obscure that approximation is happening
• y := x asExactFraction in GNU Smalltalk, or y := x asTrueFraction or y := asFraction in Pharo, sets 𝑦 to a Fraction instance representing exactly the same number as 𝑥
• z := x asFraction in GNU Smalltalk or z := x asApproximateFraction in Pharo sets 𝑧 to a Fraction instance representing the simplest rational number that would be rounded to 𝑥
• w := x asMinimalDecimalFraction in Pharo sets 𝑤 to a Fraction instance representing the number with the shortest decimal expansion that would be rounded to 𝑥; you can use this if you want to write floating-point numbers in decimal notation and make sure you get the same number back without writing more digits than you have to

(As you can see, GNU Smalltalk and Pharo disagree on whether asFraction should return an approximation or not: in GNU Smalltalk it does, while in Pharo it does not. Which is unfortunate, because it's the only name that the two share!)

---

For fun, try the following examples in Pharo:

3.141592653589793 asApproximateFractionAtOrder: 1
3.141592653589793 asApproximateFractionAtOrder: 2
3.141592653589793 asApproximateFractionAtOrder: 3
3.141592653589793 asApproximateFractionAtOrder: 4
3.141592653589793 asApproximateFractionAtOrder: 5
3.141592653589793 asApproximateFraction
3.141592653589793 asMinimalDecimalFraction
3.141592653589793 asTrueFraction

1.618033988749895 asApproximateFractionAtOrder: 1
1.618033988749895 asApproximateFractionAtOrder: 2
1.618033988749895 asApproximateFractionAtOrder: 3
1.618033988749895 asApproximateFractionAtOrder: 4
1.618033988749895 asApproximateFractionAtOrder: 5
1.618033988749895 asApproximateFraction
1.618033988749895 asMinimalDecimalFraction
1.618033988749895 asTrueFraction

See if you notice anything about the outputs—maybe you'll recognize some of the fractions; see how far they are in absolute and relative error from the true fraction; see how large the denominators are.

---

_{¹ This is what GNU Smalltalk's definition of asFraction currently does. Technically the documentation makes no promises about the nature of the approximation, but this is the most natural approach for Fraction, since it provides the best rational approximation independent of any choice of radix. See A. Ya. Khinchin, Continued Fractions, University of Chicago Press, 1964, §6 “Convergents as best approximations” for further discussion of continued fraction convergents as best rational approximations. Continued fractions are a beautiful corner of mathematics but sadly neglected in modern education!}