Mandelbrot„algoritmer och uppsnabbningar av Pär Emanuelsson Mandelbrot-mängden är den kanske mesl kändafraktalen. Om man ritar den på en bild- skärm i svartvitt ser den ut så här: Vad är det då som kännetecknar en sådan här fraktal? Jo, som alla andra fraktaler är den självliknande! Det innebär att om man zoomar upp ett delområde av fraktalen kom- mer det att likna den stora fraktalen. Norrnalt ser man också att strukturen blir alltmer komplex ju mer man zoomar. Här är ett exempel på en uppzoomad del av ovanstående bild: Standardalgoritmer Fraktaler genereras normalt med en rekursiv iterationsformel. Jag lämnar emel- lertid generella fraktaler därhän och koncen- trerar mig på Mandelbrot. Mandelbrot är ett exempel på en iteraion i det komplexa talplanet. Iterationsformeln är . Zn+l = Zn+ C. Här är Zn+l det nya värdet i en punkt i mängden och Zn är det gamla. C är en kon- stant och sätts uill koordinaten för ursprungspunkten man itererar. Alla dessa komponenter är alltså komplexa tal. Hur räknar man då ut en sån här bild? Ja, om man har F-N går det bra, för där kan man ju räkna med komplexa tal. Om man an- vänder något annat språk skriver man lämpli- gen om ekvationerna ovan genom att med hjälp av sina omfattande analyskunskaper dela upp dem i sina reella och imaginära ko- mponenter. Om vi sätter x=realdel och y=imaginärdel kan ekvationema f& en ny punkt skrivas: ‚ xn+l = xn2 - Yn + Cx ‚ Yn+l=2XnYn+Cy Cx är C:s realdel och Cy imaginärdelen. C sätts ull koordinaten för startpunkten. Som ni ser kommer iterationsformeln att räk- na fram en ny punkt i det komplexa talplanet. Nu finns det två möjligheter: ‚ De nya punkternas avstånd till origo blir bara större och större. ‚ Punkterna kommer att få värden enligt en återkommande cykel. I det första fallet säger man att iterationen divergerar. Det innebär att ursprungspunkten inte ingick i Mandelbrotmängden. I det andra fallet säger man att punkten ingick i mäng- den. Om man enbart kan visa mängden i svarlvitt sätter man normalt punkter som tillhör mängden svarta och resten vita. Stoppkriterier Nu är det förstås självklart att vi inte kan iterera oändligt manga gånger, vilket egentli- gen skulle behövas för att vi skulle bli helt säkra på om en punkt ingår i mängden eller inte. I stäUet avbryter vi om något av följande villkor uppfylls: ‚ Avståndet till origo blir > 2. ‚ Antalet it«ationer > N. Här är det magiska nummer på gång! Att alla punkter med ett avstånd > 2 kommer att divergera har bevisats av någon med större hjäma än jag. Alltså behöv« vi inte iterera mer om detta villkor uppfylls. Om vi å andra sidan har itererat en massa gånger utan att punkten har divergerat kan vi lugnt anta att punkten tillhör mängden. Den observante iakttagaren lägger här märke till en tråkig assymetri: medan villkoret för di- vergens är klart uppställt är villkoret för kon- vergens lite flytande. Vad ska vi välja för N? 10? 100? 50000? Ja, det beror på. Det finns faktiskt möjligheter att ställa upp explicita villkor även för kon- vergens, vilket jag återkommer till. För det första: vad händer om vi väljer fdr litet N? Jo, vissa punkter behöver ganska många iterationer innan de divergerar. Om vi väljer för litet N kommer algoritmen att tro att dessa punkter ingår i mängden, fast de inte gör det. Vi får då en kluddig svart blob i stäl- let for en skarp njure. (Ja, det var sent när jag skrev det här!) Om vi väljer för stort N kommer vi att förlora tid. Vi har då redan hittat alla punkter som divergerar och att iterera konvergerande punkter är bortkastad tid. Det kan man göra till döddagar. Valet av N beror oekså på hur nära mäng- den man befinner sig. Nära mängden måste man iterera många gånger för att kunna skilja ut divergerande punkter från konvergerande. Det bästa är alltså tyvärr att prova sig fram! Som ett exempel kan jag nämna att jag har använt ett N på 50 till den fdrsta bilden. Presentation Nu är frågan hur man presenterar resul- tatet från algoritmen på ett så trevligt sätt som möjligt. Med en svartvit skärm utan gråskalor finns inte mycket val, utan det blir som på bil- dema här i Garb. Man kan i och för sig tänka sig att man rastrerar gråskaleinformationen och det kan bli snyggt om man har tur. Med färg har man helt andra möjligheter. Det vanligaste är att man räknar hur många gånger man itererar innan avståndet blir > 2 och sedan använder det värdet för att välja en färg. Att välja färgtabell är en uppgift som man kan tillbringa återstoden av sitt liv med. Man kan ha kontinuerliga övergångar mellan färgema, eller man kan ha skarpa språng. Något som kan rekommenderas är att ha någon ganska Ijus färg för punkter som ligger väldigt nära själva mängden. Det Iyser liksom upp kantlinjen till det svarta området på ett intressant sätt. Trix Den första frågan som inställer sig ä givetvis om vi kan göra en lika smidig formel för konvergens som för divergens, så vi slip- per iterera helt och hållet. Tyvärr har ingen kommit på det än, så fältet är öppet for egna bidrag. Några trick finns emellertid för att spara in på iterationema. Gemensamt for dem är au de försöker låta bli att iterera punkter som tillhör mängden, för de är de tyngsta att iter- era. Om man har väldigt lite av mängden (svart) i sin uppzoomade bild är de därfömnte så effektiva. Cykliska banor Som jag nämnde tidigare kommer vi att f en ny punkt i det komplexa talplanet för varje iteration. Om ursprungspunkten tillhör mäng- den kommer iterationema att resultera i er sluten kurva, dvs punktbanan kommer inte att rusa iväg mot oändligheten. Nu säger det sig självt att det är slöseri med tid att hålla på att iterera runt, runt i en cirkel för an vänta på att antalet iterationer blir > N. Metoden är alltså: så fort vi detekterar att den nya iterationspunkten redan har besökts så kan vi direkt avbryta och gå till nästa punkt. Vi kan då vara säkra på att ursprung- spunkten tillhörde mängden. Man kan t.ex. implementera det här med hjälp av en tabell över alla gamla iterations- värden, som man sbker i. Eftersom vi norrnalt använder flyttalsaritmetik måste vi tillåta ett litet fel när vi kontrollerar om vi har varit där fbrut. Rekursiv uppdelning Börja med hela området och beräkna vär- dena runt kanten av området. Om alla värden är samma, så fylle- vi hela området med det värdet. I annat fall delar vi upp området i två lika delar och tinar om någon av dessa upp- fyller villkoret. Om inte, så delar vi igen, och igen, och igen... Det inses lätt att man endast behöver räk- na en ny "sida" för varje ny delning. Man delar förstås också med fbrdel tvärs den läng- sta kanten så man inte får en massa smala remsor. Sökning Scanna bilden som vanligt. Så fort vi träf- far på en punkt som tillhör mängden startar vi en kantfdljningsrutin som fbljer kanten. (Hm... något blev redundant här...). När kant- en har följts kan vi fylla hela området med svart och kan hoppa över det vid fortsatt scan- ning. Sparar väldigt mycket tid, fbrutsatt att en viss del av området utgörs av själva mäng- den. Cirkelfyllning Genom att även beräkna derivatan på iterationsformeln kan man komma fram till ett uttryck som ger avståndet till närmaste punkt som tillhör mängden. Vi kan då direkt plotta en vit cirkel med radien satt till detta avstånd. För att fortsätta kan vi välja t.ex. fyra punkter på denna cirkels periferi och göra om beräkningen därifrån. Den här metoden är be- skriven i boken The Science of Fractal /rnag- es. Den ger normalt bara svartvita bilder, men färg kan också ge ganska lustiga resultat. Med den här metoden kan man snabbt få en gnv bild över hur det aktuella området ser ut, utan att man behöver iterera varje punkt. Andra ideer Fixtal En del komputtrar har inte flyttalsproces- sor och det blir då lite jobbigt att räkna frak- taler. En lämplig åtgärd kan vara att räkna med fixtal i stället. Genom att talen håller sig små och trevliga (< 2, annars kan man sluta) behöver man inte göra så många krångliga tester. Fargtabellen Genom an cykla fargerna i färgtabellen kan man få roliga effekter. Det går oftast att göra på de flesta datorer med färgskärm. Andra typer av presentation Ni kommer ihåg de där cyklema som man kunde använda för att detektera om en punkt tillhörde mängden? Bra! Dessa cykler kan man nämligen ocksa plotta, vilket ger skojiga resultat. S!.ltord Lycka till med fraktalema! Böcker The Beauty of Fractals - Peitgen & Richter. The Science of Fractal Irnages - Peitgen & Saupe. Fractals Everywhere - Michael Barnsley. The Fractal Ceornetry of Nature - Benoit Mandelbrot.