Integer Math

Robert P. Munafo, 2002 Apr 22.

Note: This material is now mostly obsolete, due to the redesign of home computers to emphasize good floating-point performance.

Prior to the Pentium and PowerPC, integer math (also called fixed point arithmetic) was a very important speed improvement for Mandelbrot programs.

The basic principle is very simple: pretend that your numbers are fractions with a specific denominator, and compute the values of the numerators.

For example, we will use the numbers 1.354 and 2.017. For ease of visualization, we will use a denominator of 1000. To represent these numbers as fractions, we use 1354/1000 and 2017/1000.

To perform addition you simply add the numerators:

1354/1000 + 2017/1000 = (1354+2017)/1000 = 3371/1000

To perform multiplication, you add the numerators, and then divide both numerator and denominator by 1000 (because the denominator of the answer always has to be 1000):

1354/1000 * 2017/1000 = (1354*2017)/1000*1000

= 2731018/1000000

=~ 2731/1000

Notice that roundoff has to occur. In Mandelbrot iterations, roundoff seldom seems to make a significant difference (see the roundoff error entry for a complete explanation). To minimize its effect, one can use either "round towards negative infinity" or "round to nearest". The obvious "round towards zero" works too, only not quite as well.

Integer math works with the Mandelbrot Set because the iterations

always stay within a small area of the origin (unless the point escapes, but then you stop iterating anyway)
are pretty much immune to roundoff errors as long as the roundoff errors are less than the pixel-spacing of the image being generated.

Integer math techniques can be combined with most other forms of optimization. However, integer math cannot be used with the distance estimator method because the first deriviative iterates don't stay near the origin and therefore floating-point is required.

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Jun 15.

s.27