Numeric Anecdote (Nerd Factor 9)

Dan Ingalls DanI at wdi.disney.com
Thu Jul 2 07:00:13 UTC 1998


Ted Kaehler reported to me that evaluating 2.0e78 asInteger caused Squeak to run out of memory.  This has been so for a long time.

I traced it down to the failure code for <Float> truncate.  <Float> truncate is a primitive that succeeds whenever the result can be expressed as a SmallInteger.  If it fails, it returns

	^ (self quo: 16383.0) * 16383 + (self rem: 16383.0) truncated

Clearly this code goes back to the days of 16-bit pointers.  But, hey, it works.  Mostly.

For fun, I timed the execution for values up to 2^150.  As follows...

	(1 to: 150) collect: [:i | Time millisecondsToRun: [(2.0 raisedTo: i) truncated]]

(0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 10 1 2 2 3 2 2 3 2 2 2 3 2 3 2 3 5 5 5 4 5 5 5 6 15 5 6 5 6 6 10 10 10 11 17 11 10 11 11 12 11 19 12 13 21 27 22 23 22 29 22 21 30 23 25 49 28 27 49 44 54 56 51 56 51 55 79 49 57 67 54 60 99 113 97 94 96 101 111 109 106 102 137 105 127 109 199 214 187 215 197 215 215 219 225 )

I thought about how to fix this.  Updating 16383 to Squeak's current SmallInteger limit helped -- it allowed 2.0e78 asInteger to complete, but it was still very slow.  It has to call itself N levels deep to deal with a number N times longer than the divisor used.  Moreover the code ultimately loses precision, and gets in a deadly embrace between quo: and rem: owing to the limited precision of Floats.  This is why 2.0e78 asInteger did not compute.

Clearly when the number is very large, we should just extract the mantissa, and shift it according to the exponent.  I had already fastened my seat belt to do this when, browsing around in Float, I (re)discovered asTrueFraction by David N. Smith and Luciano Esteban Notarfrancesco.  At first it looked as though it had a lot of similar code in it.  But after reading it more carefully, I realized that it actually computes exactly the result we need!

It's not often that you just happen across a method lying around, referred to nowhere, that will fix a bug you have, and run much faster to boot.  So here's the new code:

self abs < 2.0e16
   ifTrue: ["Fastest way when there may be a fractional part"
                ^ (self quo: 1073741823.0) * 1073741823 + (self rem: 1073741823.0) truncated]
   ifFalse: [^ self asTrueFraction.  "Extract all bits of the mantissa and shift if necess"]

It works!  Bit-perfect every time!  And never more than a millisecond.  Update forthcoming.





More information about the Squeak-dev mailing list