An int128 Mandelbrot Set

The example of using GMP to create a fixed point Mandelbrot Set is flexible, in that it will zoom without limit, but it is slow.

Most 64-bit CPUs support a 128 bit datatype, and addition, subtraction and bitshift operations on it. Furthermore, they support the multiplication of two 64 bit numbers such that the result is 128 bits (rather than only the "low" 64 bits being returned, as one would expect in C, Fortran or Java).

If we use 64 bit integers for most of our variables, but for the immediate results of multiplications we use 128 bit variables, we can support a bit shift of up to about 60. This gives a range of -8<x<8 for our usual variables, and no overflows on multiplications. Comparisions with double precision floating point are not completely clear, for our format has 60 binary digits in the factional part, whereas floating point has just 53, but leading zeros in the fractional part do not count towards this total. Conversely, any bits needed for the integer part reduce the bits available for the fractional part for the floating point format.

The good news for uses of MacOS and Windows is that this approach does not need the GMP library. The bad news is that it relies on a common GCC extension, but one supported by MacOS too.

The C is much simpler, and we do not need to write our own function for converting a PyLong object to our desired integer, as python provides a function for conversion to long long, whereas it did not for converting to a GMP mpz_t. Note that one cannot guarantee that C's long is 64 bits.

Again to compile one has to download the three files above and then type

python3 setup.py build_ext --inplace

to build the module, before running the program as

python3 mandel_tk_int128_par_col.py

The good news for all is that this approach is about a dozen times faster than using GMP. It may only give half a dozen or so extra bits of precision, but, if that is sufficient for one's needs, then it is a good solution.

The example given does not constrain the bit shift to be no more than 60. I believe that 61 works, but larger values quickly give entertainingly wrong answers.

When the Mandelbrot set first became popular in the late 1980s, most home computers did not have dedicated hardware for floating point operations. Floating point operations had to be emulated in software using integer instructions, and were thus very slow. An early, popular, and fast, program for exploring the Mandelbrot set was called Fractint, and used fixed point maths as much as possible. Computers then were 32-bit, but assuming one can multiply two 32 bit numbers to obtain a 64 bit product efficiently, then a bit shift of up to 28 will certainly work, which is sufficient for modest zooms into the set.