[squeak-dev] I went to Biloxi and all I got was a Tshirt, part 2

Kragen Javier Sitaker kragen at pobox.com
Tue Mar 20 15:35:02 UTC 2012


On Tue, Mar 20, 2012 at 07:27:22AM -0400, Chris Cunnington wrote:
> Here's a Ralph Johnson-ism for you: "Floating point is broken
> arithmetic". Seems his bete noire as an undergraduate and grad
> student was floating point. He'd get As in all his courses, but
> stumble on anything related to floating point. Then one day he
> figured it was just broken and never had a problem again.

One of the first things I ever did in Smalltalk was write a program to
draw the Mandelbrot set, with my own Complex class.   It worked, but I
was puzzled about why it was so slow.  I couldn't increase the maximum
number of iterations above about 7 or 8 before it got unusably slow.

For those who don't know the Mandelbrot set, it involves squaring
complex numbers repeatedly and adding stuff to them to see if they're
one of the numbers that eventually goes out to infinity, or if they just
loop around in a finite region.

I took a look with the debugger, and discovered that Squeak was doing
all of my arithmetic exactly, using rational numbers.  When you square
rational numbers, they get, on average, twice as big.  So I was ending
up with these fractions with 200 or 300 digits on both the top and
bottom, which slowed the arithmetic down a lot.  And every increment to
maxiter doubled the number of digits.

I added a decimal point to my code and suddenly it was lightning-fast.
The decimal point triggered a switch from exact rational arithmetic to
contagious, approximate, and O(1) floating-point, which was good enough.

Fixed point would have worked just as well, but of course it's broken
arithmetic too, just in a slightly different way.

Sometimes, late answers are wrong answers, and you just have to choose
which wrong answers you want.

Kragen


More information about the Squeak-dev mailing list