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.

Traceable

Which you think is more exact, 1/1000 or 1152921504606847/1152921504606846976? Do you understand that 0.001 cannot be represented exactly in binary? See xhttps://mcmap.net/q/15914/-why-can-39-t-decimal-numbers-be-represented-exactly-in-binary for details. – Dikdik

@JamesFoster I do understand that 1/1000 cannot be exactly represented as a binary float. However, as a fraction represented as the ration of two integers numerator 1 and denominator 1000 is more exact than the alternatives being given. So what you're saying is that by "exact" they really mean, after attempting to represent 0.001 in binary float, you actually get 1152921504606847/1152921504606846976, then that's a different perspective on exact. It wasn't clear to me that's what was meant. – Traceable

Answer 1

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!}

Groundling

Thanks for the detailed explanation. I already understand the limitations of IEEE representation of floats in a computer, and that 0.001 to me isn't exactly 0.001 as represented. What threw me was not knowing what was meant by "exact". I was thinking that if I started with 0.001 and generated an IEEE floating point representation, then 1/1000 might be the closest rational number to that representation if I limit the denominator to a "large value". But I thought, perhaps for no good reason, that if that "large value" is the maximum representable integer, I would not get 1/1000 back. – Traceable

You've definitely inspired me to explore this further. :) – Traceable

Answer 2

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.

Tidal

Thanks for the thoughtful answer. I do know quite a bit about numeric representation in the computer and its limitations. I guess I didn't understand the intention of their choice of "exact". To me, if I have a number such as 0.001, I know it may have an exact binary floating point representation in the computer. When I convert to a fraction, my intention may be to get something more exact for arithmetic purposes. for that reason, I see the 1/1000 response as being more "exact" than the large fraction response. My definition of "exact" just didn't match theirs. :) – Traceable

I probably stumbled over this because I have degrees in both Computer Engineering and Mathematics. The Maths side took over my interpretation of "exact". – Traceable

I'm glad you asked the question because these messages may be confusing, even for people like you with a good understanding of floating point representations. – Tidal

I do find Float >> asApproximateFraction the most intriguing of the set. I would need to play with it a bit to see what they're getting at. :) – Traceable

Answer 3

While the other answers delve into why the fraction 1/1000 is not equal to the 64-bit binary float 0.001, here is slightly different answer:

0.001 printStringBase: 2
"=>" '1.00000110001001001101110100101111000110101001111111e-10'

This is what 0.001 really looks like under the hood, as a binary float of limited precision (64 bits only). And that is why it is not equal to 1/1000:

1/1000 = 0.001
"=>" false

If you want exact decimals with unlimited precision, you need to tell the system. A decimal number like 0.001s is indeed exactly equal to the fraction 1/1000:

0.001s asFraction
"=>" (1/1000)

1/1000 = 0.001s
"=>" true

The reason we are not using decimals as often is that they are less efficient - 64-bit binary float math is implemented in hardware, exact math is implemented in software, making it orders of magnitudes slower.

Illyricum

Answer 4

The only thing that I want to add to the already excellent answers is to highlight a few contracts.

First contract, is that equality, inequality and comparison operations in modern Smalltalk are always based on comparing the exact value. At least, this is true on Dolphin, gnu, Pharo, Squeak.

It's not always been so. Take this C code for example:

int64_t i=1<<60+1;
double d=(double) i;
printf("%d\n',d==i);

Those two numbers do not have equal values (they can't because the integer requires 61 bits, while double only provide a 53 bits significand). Though the result of equality is true, because the integer value is converted to double BEFORE the test.

This was the case of most Smalltalk dialects too, in early 2000, 1/10 = 0.1 did answer true, despite the two numbers are not carrying the exact same value... Fortunately, we adopted wiser strategy of Scheme language since: compare exactly.

Now that we have a contract on equality, we can express further contracts on the conversions. First:

aFloat asTrueFraction = aFloat.
"which means that they share the exact same value"
"replace with asExactFraction in gst"

The second contract is this:

aFloat asMinimalDecimalFraction asFloat = aFloat.
"Though the decimal fraction may differ, it will always convert back to same float"

asMinimalDecimalFraction will answer the shortest decimal fraction that will round back to the same Float. It's very related to printing a float shortly and accurately, and in fact share the same algorithm. This is exactly the same as repr in Python. See also absPrintExactlyOn: in Squeak/Pharo. Note that this is NOT a good name, because it does not print the EXACT value, but the SHORTEST value that will round back to the same float (hence, it can be used fearlessly in read/eval/print activities).

In Squeak, the way to print the exact decimal value of a Float is this:

aFloat printShowingMaxDecimalPlaces: Float emin - Float precision + 1.

This is because the minimal power of two that can be represented in double precision is

(2 raisedTo: Float emin - Float precision + 1) = Float fminDenormalized.

And because 1/2^n requires n places after decimal point to be printed (it is 5^n/10^n).

Though continued fractions are a nice thing, I am not aware of any contract concerning asApproximateFraction. It may or may not round back to the same Float. The question is where we stop the recursion?

Historical notes: the conversion Integer>>asFloat and Fraction>>asFloat will answer the Float nearest to their exact value in modern Smalltalk, at least in gst, Squeak/Pharo. It was not the case in early 2000, and maybe still not the case in each and every dialect dialect. Written as a contract:

(aFraction - aFraction asFloat asTrueFraction) abs <= (aFraction - aFraction asFloat predecessor asTrueFraction) abs and: [
(aFraction - aFraction asFloat asTrueFraction) abs <= (aFraction - aFraction asFloat successor asTrueFraction) abs] 

Failing to provide such basic properties ruin the chance to express clean and clear contracts of higher level. It also can be very misleading when you try to check and understand what happens.

Every Smalltalk implementation should care of these features (contracts) nowadays.

Postimpressionism

Thanks this is helpful. Some comments/answers seemed to assume that I have little understanding of number representation in the CPU, which is not at all where my quandary lay. Ultimately, I just wanted to know what was meant by "Exact" when it said asExactFraction (or "True" in asTrueFraction). But your answer went above and beyond that in a good way. – Traceable