Generating the Mandelbrot Set

https://scionofbytes.me/misc/generating-mandelbrot-fractals/

by scionofbytes • 7 years ago

90 76 7 years ago

eb0la• 7 years ago

Take a look at Fractint (fractint.org) and all kind of fractals it can generate.

I became obsessed with IFS (iterated function systems) a looooong time ago. Take a look at the colage theorem and try to make your own ;-)

Cheers

trollied• 7 years ago

Oh, me too. I was obsessed with Fractint when I was a teenager - It's what got me into coding. Wrote some Pascal that morphed one IFS pattern into another & was soooo pleased with myself :-)

Some modern fractal things that I appreciate:

Example IFS generator: http://sirxemic.github.io/ifs-animator/ Mandelbulb 3D (amazing): http://www.mandelbulb.com

If anyone wants to start with something simple, try and write a Sierpinski Gasket generator. Very very simple, yet infinitely complicated.

ghaff• 7 years ago

Fractint was one of a number of programs that were very popular for a period because they really showed off graphics cards that, for the first time on consumer hardware, could display reasonably high resolution graphics (EGA then VGA).

Twirrim2• 7 years ago

There's some fun to be had with the Java based jwildfire these days, http://www.jwildfire.org/, although arguably it's a bit more focussed on making things pretty.

manifestsilence6• 7 years ago

Playing with Fractint and reading Chaos shaped my world view more than most things in my youth. It formed the basis for what passes for spirituality in me.

JadeNB• 7 years ago

I thought for a moment you were referring to FRACTRAN (https://en.wikipedia.org/wiki/FRACTRAN), which is a whole different kind of interesting.

melling• 7 years ago

I’ve got some Mandelbrot resources at the bottom of this Github page:

https://github.com/melling/ComputerGraphics

jrockway• 7 years ago

What I like about generating this picture is that the color of every pixel is completely independent. If you have 2 cores, you can generate it twice as fast. If you have a million cores, you can generate it a million times faster.

Apparently I attempted this in Haskell 10 years ago: https://gist.github.com/jrockway/291074. I seem to recall adding things to that GTK image builder the slowest part by far. I bet things are better 10 years later though.

sorenjan4• 7 years ago

If you want to use a browser to generate the Mandelbrot set I think the best option is a WebGL shader. I found this, but there should be plenty of variants out there as it's a classic example of a parallel problem that benefits immensely from using the GPU.

https://www.shadertoy.com/view/4df3Rn

jerf3• 7 years ago

As the comments on that page indicate, you have problems with float precision pretty quickly. It's hard to intuit just how fast you're shedding bits when you zoom in.

Some quick DDG-ing around suggests that there isn't a great solution for arbitrary-precision GPU numbers, and that trying to force it on to GPUs either loses all the speed advantages it has over CPUs or even just loses to CPUs. Corrections solicited.

(Remember... GPUs aren't "faster" than CPUs. They're different. There are things GPUs are much faster than CPUs, but there's also plenty of tasks... indeed, it's most of them that we actually perform... where CPUs are faster. You can get differentials of 100x-1000x in either direction. That's why we use CPUs.)

sorenjan4• 7 years ago

I know GPUs aren't necessarily faster than CPUs, but they are more parallel. The article's graphics didn't work in my browser so I haven't looked at the results other than the rendered images, but there's no arbitrary precision in the linked code. It's an attempt to speed up the rendering using threads, when the GPU would be faster.

I found this version [0] that uses perturbation theory to get deep zoom on the GPU. I haven't seen it before and haven't looked into it, but it seems neat.

[0] https://github.com/munrocket/deep-fractal

londons_explore• 7 years ago

It should be possible to use fixed point math for a fractal. That should fit in the GPU well.

Obviously for more zoom, you're still going to need more bits (and therefore different codepaths for different zoom levels).

Fancy approximations can probably be done to look at computation results from neighbouring pixels too. The number of bits to store the difference from an intermediate pixel is far smaller.

dahart• 7 years ago

For a fun variation, check out this twist I made. I use Mandelbrot as a warp instead of visualizing the iterations. https://www.shadertoy.com/view/XsKfDc

If it doesn’t work in your browser because of the camera input, try replacing the iChannel0 input with one of the built-in videos. Firefox seems to work best for me to use the Camera input, and turning your head into MandelHeads is pretty hilarious...

ryanmercer• 7 years ago

Mandelbrot is of the devil Bobby Boucer! It is entirely too easy to lose a Saturday on YouTube just watching these videos.

Damogran6• 7 years ago

It took 4 Amiga 500s about 3 days to render the mandelbrot set at 320x200 when I was in High School. In case anyone is plotting out the increase in computer power over the years.

yodsanklai2• 7 years ago

you had to code it in assembly! I believe it took about a few minutes on my Amiga.

zimpenfish2• 7 years ago

I wrote a version in False[1] (sadly lost to the sands of time) which was pretty nippy on my A5000.

[1] http://strlen.com/false-language/

yason• 7 years ago

This article reminded me of the good old days as well. I wrote some toy Mandelbrot renderers on Amiga. Mine didn't have an FPU so any trivial algorithm would choke itself with the floating point emulation code and would probably take days to finish. So, the first fix would be to rewrite it for integer math. (And, eventually, write a proper floating-point implementation at the time when I did obtain an Amiga with an FPU...)

The results were nothing close to real-time but the speed difference was astronomical. With a bit of tricking the compiler to produce good code you could get a screenful in a few minutes. There were good Mandelbrot zoomers for Amiga written in assembler that you could, maybe barely but still, call real-time renderers. Of course, I added panning and zooming in mine as well eventhough the performance at the time was more akin to "real-long-time" rather than "real-time".

The number of optimisations available are mind-boggling, especially for real-time renderers which only need to care about correctness in the final image -- which often won't be rendered at all because the user has moved elsewhere or zoomed deeper before getting there.

So, rendering as you iterate is one thing you can do: as soon as the image has enough detail, it's "finished" for all practical purposes and either the user moves around elsewhere or leaves the renderer to finish the final iterations with hopefully only minor updates on the actual screen.

Also, because the set is the (typically) black area the details for the nice color shades are quicker to compute because those pixels run away sooner. On the other hand, the shaded areas are really not where the genuine details are so you're left with a lot of ways to precalculate estimated values for these pixels when you're certain you're not too close to the set. A real-time renderer can also save work in only computing new pixels revealed by panning and reusing pixels that have only moved but still on the screen. To some extent it's also possible to quickly extrapolate temporary pixel colors after panning, then try to lock down where there might be pixels that belong to the set.

Of course, the usual, more mechanical inner-loop optimisations apply as well. This becomes mandatory at deeper zoom levels where you raise the threshold for discarding pixels, and you actually have to run lots of iterations for nearly all pixels.

I just love these applications where a seemingly simple algorithms lends itself to endless amount of performance optimisations. Especially with fractals the limits are literally... unlimited.

rbanffy3• 7 years ago

Did that with Apple II+. 32 bit floats helped it be less slow, but it wasn't fast by any measure. I also exploited some PAL-M artifacting to fake more colors (with bigger pixels, which also sped up things)

buckminster• 7 years ago

That's surprising. BBC BASIC on a 2Mhz 6502 could render 128x256 (a square using fat pixels) in about 6 hours. I've seen a recent optimised 6502 assembly version, also on the BBC Micro, that runs in about a minute.

Nursie3• 7 years ago

I have a python fractal drawer here - https://github.com/starnose/fract

That can do a load of different types (Pickover Biomorphs, Newton-Raphson approximations, burning ships, Mandel-drops etc). Always loved drawing fractals. One day I'll get around to implementing Ray-marching and draw the mandelbulb!

ipython• 7 years ago

It’s a right of passage to generate the Mandelbrot set. I have fond memories of being handed the scientific American article introducing it- apparently you can download a pdf version here: https://static.scientificamerican.com/sciam/assets/media/inl...

As a high school student I was fascinated and implemented it on any machine I had access to. I remember being bored in math class and coding it on my TI-81 calculator. That took a while to render in black and white but it did work!

Great memories. Thanks for posting.

Nursie3• 7 years ago

As a high school student I was fascinated and implemented it on any machine I had access to. I remember being bored in math class and coding it on my TI-81 calculator.

In a recent contract I had very little to do for a few weeks and access to a ~9000 core server cluster and a workload-distribution framework...

felixyz• 7 years ago

Wait! Don't stop, tell us the rest of the story...

yodsanklai2• 7 years ago

I remember it too. I got the algorithm from some programming magazine, without understanding the maths behind it. I went to the local bookstore in my little town to find books on the topic, but they didn't have any. I envy the kids today who have access to so much resources.

zimpenfish2• 7 years ago

TI-81 calculator

I did one on my Casio FX-7000G. The fun of programming under real[1] constraints!

[1] Yes, yes, it wasn't punch cards or core memory or using a hammer to magnetise rocks...

BeetleB• 7 years ago

Thanks for posting the Sci Am article. I discovered Mandelbrot around 1994, and proceeded to program it in QB. Soon after, I found an old Sci Am article sitting around, and it was the one with the Mandelbrot! We almost never bought Sci Am articles, so it was a very pleasant surprise.

phkahler2• 7 years ago

A right of passage - yes. Another object to render is the Lorenz Attractor - not quite as cool, but interesting in a different way.

jackfraser2• 7 years ago

I keep reading that the Lorenz can be modeled on an analogue computer, and I want to find an example of how, so I can port it to a synthesizer and listen to it

FreeFull2• 7 years ago

On a side note, the actual saying is "rite of passage". "rite" as in ritual.

colordrops• 7 years ago

I could have written every word of your comment and it would have been accurate haha.

manifestsilence6• 7 years ago

Me too! I think I used a TI85 or 89 but yup! It was awesome learning how to make them after years of playing with them on Fractint, just zooming around.

jackfraser2• 7 years ago

I miss Fractint. I spent hours playing with that thing as a kid, with no idea about the math behind it (and no Numberphile to help explain it). So I just zoomed and plotted and got really familiar with which particular SVGA modes I could use and which I couldn't.

I still remember discovering Render To Disk and realizing I could save stuff out and open it up in Rainbow Paint... which has been lost in the sands of internet.

mordechai9000• 7 years ago

Programming in the built calculator language was worse than hand coding assembly language, due to the tedious input method.

I killed the battery by setting the bailout to a ridiculously high value and forgetting about it overnight.

I still have the calculator, but the memory was cleared at one point. I have been tempted to recreate the Mandelbrot program to show my kids, but I can't bring myself to devote that much of my life to it again.

AtomicOrbital• 7 years ago

luckily I had a subscription to Scientific American so when I read that article I immediately wrote it up in the language at hand - turbo pascal - which would take overnight to generate a full screen Mandelbrot image - that was about 1987 or so - excellent motivation for young brash explorers who loved the unknown - the algorithm was just easy enough to get working without too much frustration yet capable of generating infinitely beautifully complex views into reality

YjSe2GMQ• 7 years ago

I once wrote a PostScript program that generates Mandelbrot, tuned it so that it finishes up in reasonable time, and sent to some old laser printer. On next day morning the machine finished up churning numbers and spat out a known picture.

BTW: .ps (PostScript) is a fun little stack based language, similar to JVM. Document is simply the result of the program execution. You can program it by hand, though I do not recommend anything large.

RBerenguel• 7 years ago

It's a very fun exercise when you are starting with PostScript... and indeed, unless you are familiar with Forth or any other stack based language, it's a big pain to write. A long time ago I wrote a very short "tutorial" [1] on my blog (which right now looks very bad due to change in stylesheets that don't have translated well... The code for the Mandelbrot set there is broken (due to googlecode dying), but I just moved from my local copy to a gist [2]. And the code for the Christmas postcard (with Koch snowflakes and Gosper curves) is here [3]. It is commented, but not sure how useful it can be.

[1] https://www.mostlymaths.net/2008/12/quick-postscript-program...

[2] https://gist.github.com/rberenguel/9a5239034cafdeaabdf665444...

[3] https://gist.github.com/rberenguel/38f5106fee2a795be45d6a335...

Edit: having a blog with posts from 10 years ago you want to reference is painful... Broken links, grammar errors, unclear writing, typos...

rbanffy3• 7 years ago

It was really cool in the early 80s became the printer was often the most powerful computer in the office.

Multi-megabyte memories and fast RISC processors with FPUs were not uncommon.

manifestsilence6• 7 years ago

I used to work in a proprietary concatenative/stack language that was used for the GUI front-end for medical software. I wrote a Mandelbrot in it that used zero variable names, just two functions with a recursive call. It was beautifully terse and dense. That sort of language is really satisfying for that sort of problem.

pvg• 7 years ago

It's 'similar to [the] JVM' in that the word 'stack' pops up when either is described. In most substantial ways, they are quite dissimilar.

fanf2• 7 years ago

I managed to get an Apple LaserWriter II to render a Mandelbrot set very nicely at 300dpi in reasonable time by tracing the boundaries of a few select level sets: much fewer points to examine so much faster.

liveoneggs• 7 years ago

https://www.sqlite.org/lang_with.html scroll down to the bottom to see a sqlite mandelbrot

dghf• 7 years ago

Picky point:

Let’s just say that for our purposes we can think of complex numbers existing on a line perpindicular to our regular number line. If you take a piece of graph paper and mark a line from left to right, and then another line that crosses that line at 90 degrees, from top to bottom, you can imagine that the horizontal line represents the real number line, and the vertical line represents the complex number line.

The vertical line is the imaginary number line. 2 is as much a complex number as 3i is (2 + 0i vs 0 + 3i).

ocfnash2• 7 years ago

Here's a fun fact about the Mandelbrot set, which I will communicate in Python in the hope that you can have a little fun witnessing the results:

  def N(eps):
    c = -0.75 + eps*1j
    n = 0
    z = 0
    while abs(z) < 2:
      z = z*z + c
      n += 1
    return n

  [N(eps) for eps in [0.1, 0.01, 0.001, 0.0001, 0.00001, 0.000001]]

Twirrim2• 7 years ago

That was interesting. It continues for a little bit, but it soon falls apart:

    $ pypy3 man.py
    [33, 315, 3143, 31417, 314160, 3141593, 31415927, 7853981629]

ocfnash2• 7 years ago

It continues forever! See here for example: https://mathoverflow.net/questions/215187/is-there-a-referen...

I believe you are just running into the limits of double precision arithmetic; indeed log_2((10^8)^2) > 53.

FreeFull2• 7 years ago

Interestingly, 7.853981629 is close to pi*2.5

throwawaymath• 7 years ago

When you begin with z = k i - 0.75, you can obtain an arbitrarily good approximation of pi by multiplying the p for which f_p(z) = z^2 + z diverges by k. The approximation increases in precision as k tends to 0.

There's a neat video explaining it here: https://www.youtube.com/watch?v=d0vY0CKYhPY

manifestsilence6• 7 years ago

very cool!

doodpants• 7 years ago

Pardon the off-topic comment, but is anyone else finding the discussed web page to be sluggish to the point of unusability? (This is on Firefox 67, on Windows 7.) I'm not talking about page load time; once the page has finished loading:

- trying to scroll the page using arrow keys or Page Up/Down keys takes several seconds between key press and response

- when dragging the scroll bar manually, the new scrolled-in area is blank white for several seconds before finally filling in with content

- even right-click, or click-drag to select text, takes a few seconds to respond

I tried disabling javascript on the page, but it makes no difference, so it's not some runaway script. I'm guessing that maybe there are some very high resolution Mandelbrot images that are being scaled in the browser?

stan_rogers• 7 years ago

FF 67.0 on Win10 w/uBlock Origin, i3 7100/8 GB, snappy. Scrolling back up reloads/regens images, so there's a sub-second flash of empty in the image locations, but otherwise it's not misbehaving for me at all.

jjar• 7 years ago

I always found implementing fractals very satisfying, so this was a good read. Shameless plug for my own subpar Julia set viewer (Julia set results "make up" the Mandlebrot set): http://thejamespaterson.com/scripts/julia/

scionofbytes2• 7 years ago

Your website hurt my brain but I enjoyed the Julia Fractal generator.

cr0sh• 7 years ago

Hah - s/he's complaining about "slow" being 2-7 seconds...

...I remember back when I was in high school making a generator for this in BASIC on an Apple IIe, running 16 colors in the "double high res mode" (needed the 80-column card for it - only machine that had it) - and having it run for hours just to generate one image.

Slow...sigh.

ChrisGranger• 7 years ago

I have those memories as well, only it was a Commodore 64. I believe I found the program used to generate the set in Compute! magazine and had to type it manually. Good times.

rsl7• 7 years ago

same here - regular hi res took overnight sometimes.

manifestsilence6• 7 years ago

It gives me warm fuzzies being surrounded by fellow Mandelbrot lovers on this thread. I've been enchanted by fractals ever since seeing IFS ferns that someone made in BASIC on a green monochrome screen.

I've wanted for a long time to get around to generating the Mandelbrot as a 3D height map (Fractint could do that from a static viewpoint), and make it explorable. Ideally where you can change size to explore it all...

scionofbytes2• 7 years ago

That sounds like a cool idea. Do you mean the height would be based on color with the blackness being either a deep point or a high plateau?

manifestsilence6• 7 years ago

Yeah, pretty much, though really the colors are based on how long it takes a point to "escape" the set, if it does, with the blackness being ones that never do (to whatever level of diligence you have time to compute "never"). I was thinking the center black bug would be a deep crevasse or the "floor", with mountains rising on either side, so you could wander around in the canyons around a giant flat lowland, surrounded by mountain ridges.

lozf• 7 years ago

Whilst we're on the subject, let's not forget ffmpeg:

     ffplay -f lavfi -i mandelbrot

lovasoa• 7 years ago

I made a pull request with large performance improvements, and compatibility with all modern browsers: https://github.com/ScionOfBytes/smooth-mandelbrot/pull/1

graycat• 7 years ago

The Mandelbrot set is bizarre, astoundingly so. E.g., since it is a fractal, it is astoundingly irregular.

Mandelbrot argued that commonly shapes in nature are fractals. So, we could go to a mountain range, find a lake, and then suspect that the surface is a 2D fractal.

Well, as bizarre as the Mandelbrot set is, actually it is a closed set in the usual topology for the plane. Then there is a theorem that there is a function from the plane to the line that is 0 on the Mandelbrot set, strictly positive otherwise, and infinitely differentiable. Similarly there is a function that is 0 on the boundary of that set, negative in the interior, and positive otherwise.

So, in general, with the Mandelbrot set just an example, these results hold for any closed set in the plane. And the result generalizes to dimension 1 and all finite dimensions greater than 2. So, a set is closed if and only it it is the level set of an infinitely differentiable function 0 on the boundary of the set, negative in the interior, and positive otherwise.

This result can be used to show that in the constraint qualifications for the Karush-Kuhn-Tucker conditions, the (i) Zangwill and (ii) Kuhn-Tucker constraint qualifications are independent. For a while that fact was an outstanding unanswered question about constraint qualifications.

Somewhere in one of the papers of Arrow, Hurwicz, and Uzawa on mathematical economics there is a similar question about constraint qualifications asked but not answered that is easily answered with an example based on these results about infinitely differentiable functions and closed sets.

Back to the mountains, we can argue that the surface of the land, above, at the boundary, and on the bottom of the lake can be infinitely differentiable while the lake is the Mandelbrot set or any closed set.

Bizarre stuff!

ctoth• 7 years ago

As I was reading this I just kept hearing in my head...

Take a point called Z in the complex plane,

let z[1] be z^2+C...

let z[2] be z[1]^2+c...

let z[3] be z[2]^2+c

And so on.

https://www.youtube.com/watch?v=QrztrxV9OtQ

Tempest1981• 7 years ago

Also popular around that time in the 80s:

https://en.wikipedia.org/wiki/Bifurcation_diagram

And the book Chaos, by James Gleick

Oh, and The Cuckoo's Egg, by Clifford Stoll

joseph8th• 7 years ago

Invariably when learning a new language, making a Mandelbrot generator is my first project (after tutorials). Added benefit: I can compare benchmarks since Mandelbrot algorithm is CPU heavy.

Generating the Mandelbrot Set

Related Stories