## Re: [Fractdev] Perturbation Theory Implementation |

This message is part of the following thread: | |
---|---|

the complete thread tree sorted by date | |

Rupert Millard at | |

Hi Rupert,

Thanks for responding. Did you try the program? It's free.

Of course there's a need for arbitrary precision, but not in the iteration

loop. However, the speed seems almost independent of depth of zoom. I am

currently running a zoom over 10^10000.

You said:

So how would I do it, if I had the required product of programming skill and

free time? A recursive algorithm, like SOI. You'd need to pass the

coordinates for a rectangle and incomplete arbitrary precision iteration

data for a (hopefully) central point.

Complete iteration of central point until bailout / maxit / or possibly

periodicity check positive. (I suspect periodicity checking would be more of

a hindrance.)

Calculate other key points in turn, recursing when the approximation breaks

down.

Are you able to express this as an algorithm that I could code to? I just

can't visualise what the code would look like. I appreciate any help you can

give.

Here are some comments that may be useful:

Perturbation

<http://dinkydauset.deviantart.com/journal/Perturbation-for-the-Mandelbrot-s

et-450766847> for the Mandelbrot set

Perturbation for the Mandelbrot set

Perturbation for rendering the Mandelbrot set has been around for a while. I

would have written a journal before because it's very awesome, but right

from the start there was a fundamental problem: reliability. A recent

discovery by Pauldelbrot on fractalforums.com indicates that perturbation

can now be used to render the Mandelbrot set reliably. Is the project

approaching completion? "Correctness" now appears to be achieved.

Discovery

Roughly a year ago, Kevin Martin published a relatively short document

<http://www.deviantart.com/users/outgoing?http://www.superfractalthing.co.nf

/sft_maths.pdf> about the Mandelbrot set, containing some equations that

staggered everyone. His idea was to apply the principle of perturbation to

rendering the Mandelbrot set, and combining that with something he called

series approximation. Perturbation allows the iteration count of a pixel to

be derived from a different, fully calculated pixel "nearby" (to be called a

reference pixel). In practice this means that it's possible to calculate

just one single pixel in an image, and derive the rest using perturbation.

At great depths with millions of iterations, this saves an enormous amount

of render time, which is the main result.

Series approximation allows large number of iterations of pixels to be

skipped entirely, good for another enormous speed-up, but it doesn't stop

there. In addition, no arbitrary precision calculations are required to do

the "deriving" work. Floating point calculations, which are much faster to

perform, are sufficient. Martin concludes his document with the following

statement:

Using [the equations] means that the time taken rendering Mandelbrot images

is largely independent of depth and iteration count, and mainly depends on

the complexity of the image being created.

The implications of this are enormous and such a theory is of course yelling

to be implemented. Along with the mathematics, Martin also published a

simple software implementation of the theory dubbed SuperFractalThing, so

that everyone could see that it works. Since then, more software developers

have started working on their own implementations.

The simple equation of the Mandelbrot set has long been famous of being so

computationally intensive that it can bring any supercomputer to it's knees,

as long as you zoom in deep enough. Although that is still the case even

with perturbation, the barrier has been shifted significantly.

Fractal extreme has been the fastest software to calculate the Mandelbrot

set for a long time, using traditional optimizations. If the deviation above

were to be rendered in Fractal extreme, the render would take roughly 6

months. The actual image was rendered in 6 hours using an implementation of

perturbation by Botond Kosa. What you're looking at right there is something

that, without perturbation, would have been totally out of reach for many

years, no matter how optimized the software is. As Bruce Dawson, the man

behind Fractal extreme, commented on fractalforums.com: good algorithms beat

optimized code.

Glitches

Although there is no doubt that perturbation is a "good algorithm", it came

with severe problems right from the start, that Kevin Martin couldn't solve

himself. If you have been paying attention, you may have noticed the

requirement of a reference pixel to be "nearby". More specifically, usage of

floating point numbers to do the calculations requires some numbers in the

perturbation equation to be "small". Mathematically, this is completely

useless, because there's no exact definition of what "small" is. Indeed, the

results of the calculations were shown to be unreliable in many cases. It

turned out that the results were correct "most of the time", but sometimes

not. Incorrect parts of renders have since been called glitches.

I tried to look at the source code and got totally lost. I hope we can get

something going here.

Thanks,

Paul.

_____

From: Fractdev [mailto:fractdev-bounces@mailman.xmission.com] On Behalf Of

Rupert Millard

Sent: Sunday, 18 January 2015 7:04 PM

To: Fractint developer's list

Subject: Re: [Fractdev] Perturbation Theory Implementation

You've said that it only uses the double float in the deep zooming code, but

where does it get X0....Xn from? There must be arbitrary precision code

somewhere.

*
*

>From that two page PDF, the algorithm looks simple, doesn't it? However we

know Δn gets "large" (< 4, mins) for sufficiently large n. That's chaos

theory for you, and it wouldn't look like a fractal if Δn remained of the

order of 10^-100 all the time. So it must do something when the

approximation breaks down - I expect it starts calculating at arbitrary

precision. (Although as we're working with floating point types, it would

be quite elegant to use that double-double / quad-double datatype here.)

So how would I do it, if I had the required product of programming skill and

free time? A recursive algorithm, like SOI. You'd need to pass the

coordinates for a rectangle and incomplete arbitrary precision iteration

data for a (hopefully) central point.

Complete iteration of central point until bailout / maxit / or possibly

periodicity check positive. (I suspect periodicity checking would be more of

a hindrance.)

Calculate other key points in turn, recursing when the approximation breaks

down.

Hope this helps. I can take a look at the source code too if that would

help.

Thanks for responding. Did you try the program? It's free.

Of course there's a need for arbitrary precision, but not in the iteration

loop. However, the speed seems almost independent of depth of zoom. I am

currently running a zoom over 10^10000.

You said:

So how would I do it, if I had the required product of programming skill and

free time? A recursive algorithm, like SOI. You'd need to pass the

coordinates for a rectangle and incomplete arbitrary precision iteration

data for a (hopefully) central point.

Complete iteration of central point until bailout / maxit / or possibly

periodicity check positive. (I suspect periodicity checking would be more of

a hindrance.)

Calculate other key points in turn, recursing when the approximation breaks

down.

Are you able to express this as an algorithm that I could code to? I just

can't visualise what the code would look like. I appreciate any help you can

give.

Here are some comments that may be useful:

Perturbation

<http://dinkydauset.deviantart.com/journal/Perturbation-for-the-Mandelbrot-s

et-450766847> for the Mandelbrot set

* by DinkydauSet <http://dinkydauset.deviantart.com/> , Apr 28, 2014, 3:46:13 PM * Journals <http://www.deviantart.com/journals/> / Personal <http://www.deviantart.com/journals/personal/>

Perturbation for the Mandelbrot set

Perturbation for rendering the Mandelbrot set has been around for a while. I

would have written a journal before because it's very awesome, but right

from the start there was a fundamental problem: reliability. A recent

discovery by Pauldelbrot on fractalforums.com indicates that perturbation

can now be used to render the Mandelbrot set reliably. Is the project

approaching completion? "Correctness" now appears to be achieved.

Discovery

Roughly a year ago, Kevin Martin published a relatively short document

<http://www.deviantart.com/users/outgoing?http://www.superfractalthing.co.nf

/sft_maths.pdf> about the Mandelbrot set, containing some equations that

staggered everyone. His idea was to apply the principle of perturbation to

rendering the Mandelbrot set, and combining that with something he called

series approximation. Perturbation allows the iteration count of a pixel to

be derived from a different, fully calculated pixel "nearby" (to be called a

reference pixel). In practice this means that it's possible to calculate

just one single pixel in an image, and derive the rest using perturbation.

At great depths with millions of iterations, this saves an enormous amount

of render time, which is the main result.

Series approximation allows large number of iterations of pixels to be

skipped entirely, good for another enormous speed-up, but it doesn't stop

there. In addition, no arbitrary precision calculations are required to do

the "deriving" work. Floating point calculations, which are much faster to

perform, are sufficient. Martin concludes his document with the following

statement:

Using [the equations] means that the time taken rendering Mandelbrot images

is largely independent of depth and iteration count, and mainly depends on

the complexity of the image being created.

The implications of this are enormous and such a theory is of course yelling

to be implemented. Along with the mathematics, Martin also published a

simple software implementation of the theory dubbed SuperFractalThing, so

that everyone could see that it works. Since then, more software developers

have started working on their own implementations.

The simple equation of the Mandelbrot set has long been famous of being so

computationally intensive that it can bring any supercomputer to it's knees,

as long as you zoom in deep enough. Although that is still the case even

with perturbation, the barrier has been shifted significantly.

Fractal extreme has been the fastest software to calculate the Mandelbrot

set for a long time, using traditional optimizations. If the deviation above

were to be rendered in Fractal extreme, the render would take roughly 6

months. The actual image was rendered in 6 hours using an implementation of

perturbation by Botond Kosa. What you're looking at right there is something

that, without perturbation, would have been totally out of reach for many

years, no matter how optimized the software is. As Bruce Dawson, the man

behind Fractal extreme, commented on fractalforums.com: good algorithms beat

optimized code.

Glitches

Although there is no doubt that perturbation is a "good algorithm", it came

with severe problems right from the start, that Kevin Martin couldn't solve

himself. If you have been paying attention, you may have noticed the

requirement of a reference pixel to be "nearby". More specifically, usage of

floating point numbers to do the calculations requires some numbers in the

perturbation equation to be "small". Mathematically, this is completely

useless, because there's no exact definition of what "small" is. Indeed, the

results of the calculations were shown to be unreliable in many cases. It

turned out that the results were correct "most of the time", but sometimes

not. Incorrect parts of renders have since been called glitches.

I tried to look at the source code and got totally lost. I hope we can get

something going here.

Thanks,

Paul.

---------------------------------------------------------- Paul de Leeuw Computers NSW Central Coast, Australia Email: <mailto:pdeleeuw@deleeuw.com.au> pdeleeuw@??? www: < <http://www.deleeuw.com.au/> http://www.deleeuw.com.au> ABN 72 360 822 562 ----------------------------------------------------------

_____

From: Fractdev [mailto:fractdev-bounces@mailman.xmission.com] On Behalf Of

Rupert Millard

Sent: Sunday, 18 January 2015 7:04 PM

To: Fractint developer's list

Subject: Re: [Fractdev] Perturbation Theory Implementation

You've said that it only uses the double float in the deep zooming code, but

where does it get X0....Xn from? There must be arbitrary precision code

somewhere.

>From that two page PDF, the algorithm looks simple, doesn't it? However we

know Δn gets "large" (< 4, mins) for sufficiently large n. That's chaos

theory for you, and it wouldn't look like a fractal if Δn remained of the

order of 10^-100 all the time. So it must do something when the

approximation breaks down - I expect it starts calculating at arbitrary

precision. (Although as we're working with floating point types, it would

be quite elegant to use that double-double / quad-double datatype here.)

So how would I do it, if I had the required product of programming skill and

free time? A recursive algorithm, like SOI. You'd need to pass the

coordinates for a rectangle and incomplete arbitrary precision iteration

data for a (hopefully) central point.

Complete iteration of central point until bailout / maxit / or possibly

periodicity check positive. (I suspect periodicity checking would be more of

a hindrance.)

Calculate other key points in turn, recursing when the approximation breaks

down.

Hope this helps. I can take a look at the source code too if that would

help.

This message was posted to the following mailing lists: | ||||
---|---|---|---|---|

FractdevMailing List Info | Nearby Messages | Re: [Fractdev] Perturbation Theory Implementation | Re: [Fractdev] [Fractint] Update to SDL version |

XMission Mailing List Archives administrated by XMission Support | Lurker (version 2.3) |