3 ms·

Cool article. Does anyone have any pointers to what the state of the art is for arbitrary precision? Is that even viable or will it just be a boring extremely s

Cool article. Does anyone have any pointers to what the state of the art is for arbitrary precision? Is that even viable or will it just be a boring extremely slow exercise long before you reach the zoom levels where 64bit float breaks down?

deleted 3y ago
[deleted]
dahart 3y ago
64 bit doubles break down pretty quickly when zooming into the Mandelbrot: you can zoom in by 2x about 64 times. Doubles only get you twice the zoom level as 32 bit floats, meaning with fp32, you can zoom 2x about 32 times. I feel like using doubles makes zooming a little better but isn’t all that meaningful of an improvement over floats. You can use arbitrary precision, and yes it will be an exercise in patience (both in coding and in waiting for Mandel to render), but there are some really crazy tricks for deep zooming into Mandel that don’t use arbitrary precision, tricks that I know of but don’t understand yet. I’ve seen hints on some of the Mandel deep-zoom videos on YouTube, and also on ShaderToy. BTW I wrote a 128 bit quad-float emulator for ShaderToy, and it seems that it’s somewhere around 100x slower than using floats. It was a very fun exercise.
QuadmasterXLII 3y ago
The state of the art for arbitrary precision is in rapid flux right now. The naive approach is O(pixels * iterations * bits_precision^2) which is just hopeless. K. L. Martin[1] took it to O(iterations * bits_precision^2 + pixels * iterations) which was a massive improvement. I explain my webgl implementation of that algorithm here [2] and I think it's currently the fastest web implementation for depths up to 2000 bits. However, in 2022 Zhouran [3] dramatically improved the constant factor for the first term, then made a breakthrough in overall complexity, taking it to O(pixels * log(iterations) + iterations * bits_precision^2) which blows the approach I used out of the water for deep images. It's so recent that there's not really a blog post properly explaining it anywhere, you just have to sort through the forum thread., There is a webassembly implementation at https://fraktaler.mathr.co.uk/live/latest/ https://fraktaler.mathr.co.uk/live/latest/ with public source. 1 http://www.science.eclipse.co.uk/sft_maths.pdf http://www.science.eclipse.co.uk/sft_maths.pdf 2 https://www.hgreer.com/JavascriptMandelbrot/ https://www.hgreer.com/JavascriptMandelbrot/ 3 https://fractalforums.org/fractal-mathematics-and-new-theories/28/another-solution-to-perturbation-glitches/4360/msg29835#msg29835 https://fractalforums.org/fractal-mathematics-and-new-theori...
- sigil 3y ago
  Incredible reply, thanks! The Mandelbrot set is my Hello World when learning new graphics APIs, and I was learning WebGL with it recently. Immediately ran into the precision issues you describe in [2]!
- dahart 3y ago
  Thanks for this; I’ve been meaning to work through the ‘perturbation theory’ stuff and implement a deep zoom capable Mandel myself one of these years. What are the options today for doing this stuff on a GPU? The core of these techniques is to have pre-computed an arbitrary precision orbit, right? Does that mean in practice that the reference orbit is computed on the CPU, and rendering could optionally be done on the GPU? Does anyone compute reference orbits on the GPU?
  - QuadmasterXLII 3y ago
    No one knows how to accelerate computing the reference orbit with a GPU yet- I'm hopeful we'll find a way! Until then, yeah computing the reference orbit on CPU and then sending it to the GPU is the usual approach.

deleted 3y ago

[deleted]

dahart 3y ago

64 bit doubles break down pretty quickly when zooming into the Mandelbrot: you can zoom in by 2x about 64 times. Doubles only get you twice the zoom level as 32 bit floats, meaning with fp32, you can zoom 2x about 32 times. I feel like using doubles makes zooming a little better but isn’t all that meaningful of an improvement over floats. You can use arbitrary precision, and yes it will be an exercise in patience (both in coding and in waiting for Mandel to render), but there are some really crazy tricks for deep zooming into Mandel that don’t use arbitrary precision, tricks that I know of but don’t understand yet. I’ve seen hints on some of the Mandel deep-zoom videos on YouTube, and also on ShaderToy. BTW I wrote a 128 bit quad-float emulator for ShaderToy, and it seems that it’s somewhere around 100x slower than using floats. It was a very fun exercise.

QuadmasterXLII 3y ago

The state of the art for arbitrary precision is in rapid flux right now. The naive approach is O(pixels * iterations * bits_precision^2) which is just hopeless. K. L. Martin[1] took it to O(iterations * bits_precision^2 + pixels * iterations) which was a massive improvement. I explain my webgl implementation of that algorithm here [2] and I think it's currently the fastest web implementation for depths up to 2000 bits. However, in 2022 Zhouran [3] dramatically improved the constant factor for the first term, then made a breakthrough in overall complexity, taking it to O(pixels * log(iterations) + iterations * bits_precision^2) which blows the approach I used out of the water for deep images. It's so recent that there's not really a blog post properly explaining it anywhere, you just have to sort through the forum thread., There is a webassembly implementation at https://fraktaler.mathr.co.uk/live/latest/ https://fraktaler.mathr.co.uk/live/latest/ with public source. 1 http://www.science.eclipse.co.uk/sft_maths.pdf http://www.science.eclipse.co.uk/sft_maths.pdf 2 https://www.hgreer.com/JavascriptMandelbrot/ https://www.hgreer.com/JavascriptMandelbrot/ 3 https://fractalforums.org/fractal-mathematics-and-new-theories/28/another-solution-to-perturbation-glitches/4360/msg29835#msg29835 https://fractalforums.org/fractal-mathematics-and-new-theori...

sigil 3y ago
Incredible reply, thanks! The Mandelbrot set is my Hello World when learning new graphics APIs, and I was learning WebGL with it recently. Immediately ran into the precision issues you describe in [2]!
dahart 3y ago
Thanks for this; I’ve been meaning to work through the ‘perturbation theory’ stuff and implement a deep zoom capable Mandel myself one of these years. What are the options today for doing this stuff on a GPU? The core of these techniques is to have pre-computed an arbitrary precision orbit, right? Does that mean in practice that the reference orbit is computed on the CPU, and rendering could optionally be done on the GPU? Does anyone compute reference orbits on the GPU?
- QuadmasterXLII 3y ago
  No one knows how to accelerate computing the reference orbit with a GPU yet- I'm hopeful we'll find a way! Until then, yeah computing the reference orbit on CPU and then sending it to the GPU is the usual approach.