Mandelbrotmængden er en fraktal af typen escape-fraktal. Lad iterationen
z_i+1 = z_i² + z_i, hvor z₀ er en værdi i de komplekse tal, være givet. Da er mandelbrot-mængden defineret som mængden af de z₀ hvis iterationsbaner er begrænsede. Dvs. iteration af disse punkter går ikke mod uendelig.

Nedenstående billede af mandelbrotmængden er fremkommet på følgende måde. Startpunktet for de baner, som ikke går mod uendelig, farves sort. Startpunktet for baner, som går mod uendelig, farves hvid.

mandelbrotmængden:

Da programmet skal igennem mange beregninger inden billedet er dannet, er det vigtigt at koden er optimeret. Derved kan man spare meget cpu-tid. Derfor lister vi senere nogle metoder til optimering af sin kode.

mandelbrotmængden i 3d:

Klik på billedet og zoom ind for at se mandelbrotlandskabet. Billedet er lavet ved at lade x- og y-koordinaterne være som normalt og ved at lade z-koordinaten være bestemt af hvor mange iterationer, der skal til for at z_n forlader en cirkel med radius 2. Billedet er fremkommet efter at hvert punkt max har itereret max. 150 gange.

1. Størrelsen af området man kigger på:

I praksis er det nok at tjekke for om banen undslipper en cirkel med centrum i (0,0) og radius 2, for at vide, om banen vil gå mod uendelig (dette følger af første sætning på siden om iteration af z² + c). Faktisk er det nok at kigge på -2.0 ≤ Re(z) ≤ 0.75 , -1.5 ≤ Im(z) ≤1.5.

2. Antallet af iterationer:

Jo nærmere vi kommer Mandelbrotmængden jo flere iterationer vil det tage for et punkt at undslippe cirklen (hvis det undslipper). Det er meget forskelligt hvor meget man får ud af at øge antallet af iterationer, men det koster en del udregningstid at forøge dette tal.

3. Rækkefølgen af udregningerne:

a. Man skal ikke tjekke om et punkt er kommet uden for cirklen med radius 2 ved at tjekke om |z|<2, men faktisk ved at tjekke om |z|² < 4, da man herved sparer, at skulle tage kvadratroden for at finde normen af det komplekse tal z.

b. Hvis man vil teste om punktet c går mod uendelig under mandelbrot-iterationen, så skal man teste om z_n+1 = z_n² + c går mod uendelig, hvor z_0 er (0,0). Dvs. at man faktisk ved, at z₁ altid er lig c. Derfor kan man spare den første iteration ved at starte med c i stedet for at starte med 0.

c. Kvadratet af z_n = (x,y) bør kun udregnes en gang, hvorefter den benyttes to gange. Een gang til at finde z_n+1 og derefter til at teste om |z_n+1| < 2.

d. Om udtrykket |z_n|² < 4 er sandt, kan man i flere programmeringssprog udregne hurtigere end ved at benytte sprogets flydende kommatals-multiplikation! Dette kan dog kun lade sig gøre, hvis man har adgang til addresserne på variable og ved hvordan resultatet af en multiplikation med 2 lagres på computeren (da computeren lagrer tal binært er det blot at flytte alle de binære cifre en tand) eller udnytte hvordan 4 lagres i hukommelsen (og så sammenligne pointeren til tallet som skal sammenlignes med denne addresse). Dette kan nok ikke lade sig gøre i Java. Denne metode (at regne direkte på adresser) kan udvides til at gælde alle regneoperationerne. Dette kan studeres nærmere i artiklen af Raúl Rojas [Rojas].

Vi udnytter at Mandelbrotmængden er en sammenhængende mængde. Derfor er komplementet til mandelbrotmængden (dvs. alt udenfor mandelbrotmængden) også en sammenhængdende mængde. Specielt er mandelbrotmænden og dens komplementærmængde derfor kurvesammenhængende.

I stedet for at tegne Mandelbrotmængden linie for linie, vil vi starte med at tegne kanterne af skærmvinduet. Lad os forestille os, at vi benytter sorte punkter til at tegne Mandelbrotmængden og hvide punkter til at tegne punkterne udenfor mandelbrotmængden. Hvis kanterne kun indeholder sorte punkter, Så kan vi være sikre på hele vinduet er sort, hvilket præcist er, hvad vi vil udnytte.

At hele vinduet vil være sort skyldes følgende. Var der et hvidt punkt inde i vinduet, skulle der være en kurve fra dette punkt til et hvidt punkt uden for vinduet (punkter langt væk fra 0 vil jo være hvide). Det kan ikke lade sig gøre, da randen af vinduet er sort (og komplementærmængden til mandelbrotmængden er jo kurvesammenhængende)!

Det omvendte er også sandt: hvis siderne af vinduet er hvide, så findes der ingen sorte punkter i vinduet (argumentet er det samme som før, da vi igen ser på enkeltsammenhængende kurvesammenhængende mængder). Dette gælder dog ikke hvis vinduet indeholder hele Mandelbrotmængden. Om vinduet indeholder hele Mandelbrotmængden kan vi tjekke ved at undersøge om vinduet indeholder punktet (0,0).

Lad os følge følgende strategi:

• Se hvor mange pixels der er i vinduet: Hvis vinduet har 2 gange 2 pixels, så tegn de fire punkter en efter en og stop.
• Hvis vinduet har mere end fire punkter så tegn siderne af vinduet.
• Kig på siderne af vinduet:
  • Hvis de fire sider har samme farve, så tegn hele vinduet med denne farve.
  • Hvis der er forskellige farver på vinduet, så del det i to mindre vinduer (ved at dele vinduet med en horisontal eller vertikal linie, som går igennem vinduets midte) og gentag proceduren for hvert af de to nye vinduer.

Der er dog et problem! Hvis man ikke fanger de fine grene af mandelbrotmængden er der dele af mængden, som ikke tegnes korrekt. Problemet kan ikke undgås, da grenene i mandelbrotmængden er uendeligt fine og da computeren udregner mængden pixel for pixel og derfor ikke kan fange detaljer, som er finere end en pixel. Man kunne dog godt sørge for, at computeren fangede finere detaljer, men da nogle af grenene er uendeligt fine, vil der jo altid være grene vi ikke kan fange.

Ifølge Raúl Rojas er denne kritik naturligvis korrekt, men han mener, at i praksis sker dette ikke særligt ofte hvis man benytter en god kombination af værdier for opløsningen og iterationstallet. Rojas siger desuden følgende om denne teknik:

"We conducted experiments using a program that scanned the whole screen and a program using the method described. The second program was consistently faster than the first when the size of the screen region was bigger than 32 by 32 pixels. We also made some graphics using a laser printer and a resolutin of about 1500 by 1500 pixels. The results confirmed that the alternative method grows even faster in comparison to the whole scanning method when the resolution used increases. Using a floating-point co-processor in a workstation, our method consumed a third of the time of the normal method (using 256 by 256 pixels and 25 iterations) when the main island of the Mandelbrotset was drawn. For a window size of 1024 by 1024 pixels and 25 iterations, our method consumed about a sixth of the time consumed by the normal program."

Lettere omskrevet siger Raúl ligeså:

"With the traditional method the CPU time grows linearly with the number of pixels used. Our experience is that the CPU time grows by a factor of about three for each increase in the number of pixels by a factor of four" ... "It is very important to mention that ... if you are using many more iterations than 25, the difference between one method and the other could be much more drastic. Instead of a speed up of aboout 10 with 1048 by 1048 pixels, you could get a speed up of as much as 100 if you are using 300 iterations or more."

Vi vil nu beskrive hvordan vi på en hurtig måde bestemmer om en side af vindue kun består af samme farve, hvor vi kun benytter farverne sort og hvid.

Vi definerer en tabel, som skal bestå af summer af farvetal, hvor 0 = sort og 1 = hvid. Lad os tage fat i en af vinduets kanter. Hver pixel på denne kant lader vi svare til en indgang i førnævnte tabel. Vi vil gå fra venstre til højre (i tilfældet en horisontal linie) og tilføje farven af hver pixel til farven af dennes højre nabo. Dvs. en indgang i tabellen kommer til at bestå af summen af farvetallene fra pixelen svarende til tabelindgangen og tilbage til starten af vindueskanten (dette kaldes en partialsum). Vi kalder summen af alle farvetallene på en vindueskant for "farvelængden" af kanten. Tabelværdien svarende til den sidste pixel på en kant vil således indeholde farvelængden af kanten.

Har vi gjort dette for en kant, er det meget simpelt at teste om hele kanten har pixels af samme farve: vi skal blot teste om farvelængden af kanten er lig længden af kanten i pixels multipliceret med farvetallet af kantens første pixel.

Hvis vi har en kant af længde 10 f.eks. og alle pixels er sorte, så er alle partialsummer lig 0. Hvis vi kigger på den sidste partial sum og den er lig 0, så ved vi at hele linien indeholder sorte punkter.

1	2	3	4	5	5	5	5	5	5

Hvis de første fem punkter er hvide (farvetal 1) og de sidste fem er sorte (farvetal 0), så er de føste fem partialsummer 1, 2, 3, 4, 5. De sidste fem partial summer er 5, 5, 5, 5, 5. Den totale sum er 5, som ikke er lig pixellængden (10) gange farven af den første pixel (i dette tilfælde 1).

1	2	3	4	5		5	5	5	5	5

Vi kan nu dele linien i to. Den første del indeholder de fem pixels til venstre. Den anden de fem pixler til højre. Hvis vi kigger på partialsummen som svarer til den femte pixel, så ved vi at denne del af linien kun indeholder hvide punkter, idet partialsummen (5) svarer til pixellængden (5) gange med farven af den første pixel (1).

0	0	0	0	0

Med den anden del kan vi gøre det samme, men vi skal først trække partialsummen af den sidste pixel i første del fra pixlerne i den anden del. Vi ser at pixlerne alle indeholder farven sort idet partialsummen (0) svarer til pixellængden (5) gange med farven af den første pixel (0).

Det er nemt med denne procedure at tjekke om siden af et vindue indeholder pixels med samme farve eller ikke. Det eneste vi skal gøre er, at udregne partialsummerne for de fire sider. Hvis farvelængden af hver side er lig pixellængden gange farvetallet af en pixel i linien, så er hele linien lavet af pixler af samme farve. Hvis ikke, så må vi dele vinduet horisontalt eller vertikalt og gentage processen.

Bemærk, at partialsummerne kan beregnes simultant med beregningen af en pixels farve på linien (så er overheadet blot en heltalsberegning per pixel). Hvis disse partialsummer gemmes på en stak, så behøver vi ikke genberegne partialsummerne hver gange vi skal vide hviken farve pixlerne i en linie har. Når vi ikke har brug for disse partialsummer mere (f.eks. hvis hele vinduet er fuldstændig tegnet) så kan vi poppe dem af stakken. På denne måde behøver vi ikke at gemme et heltal per pixel på stakken. Hvis divide-and-conquer-teknikken programmeres på en rekursiv måde, så er den nødvendige stak ikke større end 8 gange pixellængden af den største side på skærmen. Hvis vi benytter 1024 gange 1024 opløsning, så behøver vi altså ikke mere end 8192 heltal for at gemme partialsummerne.