Amiga MA Magazine 1997 #3/amigamamagazinepolishissue03-1/ma_1995/09/ami936.txt

Text File | 1997-04-07 | 12KB | 256 lines

***** PROSZË ABSOLUTNIE NIE POPRAWIAÊ NICZEGO WE WZORACH I W
LISTINGACH, ANI ROZDZIELAÊ "I" OD CYFRY TAM GDZIE JEST MOWA O
LICZBACH ZESPOLONYCH !!!!! **********************************

PORZÂDEK CZY CHAOS?

<lead>Wiëkszoôê z nas, obserwujâc przyrodë, upraszcza jâ,
dopatrujâc sië w niej prostych bryî geometrycznych. Góry to
stoûki, drzewa to walce, ziemia to pîaszczyzna, horyzont to linia
prosta. W ten wîaônie sposób przyrodë opisywaî juû Euklides.  Czy
tak jest naprawdë?

<a>Bolesîaw Szczerba

<txt>Inaczej potraktowaî problem Benoit Mandelbrot. W 1980 roku
badaî on numerycznie pewne wielomiany zespolone i otrzymaî
niesamowite i szokujâce obrazy (patrz ilustracje).  Doprowadziîo
go to do stwierdzenia, ûe geometria euklidesowa nie nadaje sië do
opisu przyrody -- góry nie sâ stoûkami, a linia brzegowa nie jest
odcinkiem. Sâ to raczej owe (jak to okreôlaî Euklides)
"bezksztaîtne" formy. Mandelbrot nazwaî je fraktalami od
îaciïskiego (chyba) sîowa "fractus", co oznacza "podzielony",
"uîamkowy". Nazwa nie jest przypadkowa -- odzwierciedla doskonale
strukturë fraktali. Charakteryzuje je bowiem wysokie
samopodobieïstwo -- kaûdy fragment przypomina caîoôê. Poza tym
okazuje sië, ûe sâ to twory o wymiarze nie bëdâcym liczbâ
caîkowitâ, co w oczywisty sposób przeczy tzw. zdrowemu
rozsâdkowi. Ale jak mawiaî Albert Einstein, "zdrowy rozsâdek" to
zbiór przesâdów i uprzedzeï, których czîowiek nabywa, zanim
skoïczy 16 lat. Cóû, czy nam sië to podoba czy nie, nie sâ to ani
twory jednowymiarowe (jak np. prosta czy odcinek) ani
dwuwymiarowe (jak koîo czy prostokât). Czymûe wiëc sâ te
tajemnicze fraktale?

Poniewaû ostatnio mimo "ôwiëtego" okresu wakacji byîa mowa o
caîkach, to tym razem postanowiîem napisaê (w nagrodë dla
wytrwaîych) o czymô bardziej spektakularnym. Nie bëdë nikogo
obraûaî pytaniem, czy sîyszaî o fraktalach. Myôlë, ûe lwia czëôê
Czytelników przynajmniej przewietrzyîa uszy tym terminem. Czëôê
bawiîa sië moûe jakimô generatorem fraktali w stylu Chaos Pro,
kilku bardziej ambitnych wklepaîo moûe jakiô
gotowiec-fraktalowiec w BASIC-u ze starego numeru "Bajtka" i na
tym koniec. Artykuî ten jest przeznaczony dla tych, którzy
chcieliby sië dowiedzieê czegoô wiëcej o fraktalach i metodach
ich generowania. Poniewaû nie dysponujë caîym numerem, tylko
paroma stronami, ograniczë sië tylko do tzw. zbiorów Mandelbrota.
O zbiorach Julii, przeksztaîceniach afinicznych i moûe jeszcze
innych ciekawych rzeczach napiszë innym razem (moûe juû w
nastëpnym artykule).

Aby zrozumieê istotë fraktali, trzeba przede wszystkim mieê
pojëcie o liczbach zespolonych. Wiedza do tego potrzebna nie
wykracza w zasadzie poza zakres materiaîu IV klasy o profilu
matematyczno-fizycznym, a dla studentów kierunków ôcisîych czy
technicznych jest to juû chleb powszedni. Dla przypomnienia:
liczba zespolona to liczba postaci z=a+bi, gdzie a to tzw.
czëôê rzeczywista (oznaczana jako Re(z)), b to czëôê urojona
(oznaczana jako Im(z)), zaô i to wielkoôê speîniajâca równanie
i^2 + 1 = 0. Zwróê uwagë, ûe i^2 = -1, co nie zachodzi dla ûadnej
liczby rzeczywistej. Wniosek: i to nie jest liczba rzeczywista.
Zbiór liczb zespolonych jest uogólnieniem zbioru liczb
rzeczywistych -- te ostatnie to szczególny wypadek tych
pierwszych dla b=0. Liczby zespolone przedstawiamy na
pîaszczyúnie jako parë punktów (a, b). Ukîad wspóîrzëdnych
przypomina kartezjaïski, ale zamiast osi x i y mamy oô
rzeczywistâ Re(z) i oô urojonâ Im(z). Liczbie 1-2i odpowiada wiëc
punkt (1,-2) w takim ukîadzie wspóîrzëdnych, liczbie 3i odpowiada
punkt (0,3), liczbie 2 punkt (2,0) itd. Nie bëdë definiowaî
podstawowych dziaîaï w takim zbiorze -- moûna to znaleúê w kaûdej
ksiâûce do algebry wyûszej -- nie wnikajâc w szczegóîy podam
tylko, jak wyglâda w takim zbiorze dodawanie oraz potëgowanie.
Przyda sië to w dalszej czëôci artykuîu.

<l> z1+z2=(a1+b1i)+(a2+b2i)=(a1+a2)+(b1+b2)i=A+Bi

<txt>gdzie A=a1+a2 a B=b1+b2. Na pîaszczyúnie to punkt o
wspóîrzëdnych (a1+a2,b1+b2).

<l> z^2=zz=(a^2-b^2)+(2ab)i=A+Bi

<txt>gdzie A=a^2-b^2, B=2ab. Na pîaszczyúnie to punkt o wspóîrzëdnych
(a^2-b^2,2ab).

No, teraz po takim solidnym przygotowaniu teoretycznym moûemy
przejôê do rzeczy. Wyobraúmy sobie ciâg liczb zespolonych
{z0,z1,z2,z3,...}. Przyjmijmy, ûe z0=0, a kaûdy nastëpny
wyraz ciâgu wyraûa sië przez poprzedni w kwadracie plus
pewna staîa zespolona. Czyli zn+1=zn^2+c, gdzie
zn+1 oznacza n+1 element ciâgu, zn -- n-ty wyraz ciâgu (czyli
poprzedni wzglëdem zn+1), a c pewnâ staîâ zespolonâ
speîniajâcâ tu rolë parametru. Dla uîatwienia podam kilka
pierwszych elementów tego ciâgu:

<l> z0=0

z1=c

z2=c^2+c

z3=(c^2+c)^2+c

z4=[(c^2+c)^2+c]^2+c

...

Jako êwiczenie proszë sobie podstawiê za c dowolnâ liczbë
zespolonâ (np. 1+i) i policzyê kilka pierwszych wyrazów ciâgu,
przy czym dodawanie i potëgowanie naleûy tu rozumieê w sensie
dziaîaï na liczbach zespolonych tak, jak to podaîem wczeôniej.
Okazuje sië, ûe dla pewnych wartoôci parametru c ciâg
{z0,z1,z2,z3,...} jest ograniczony na pîaszczyúnie zespolonej, a
dla innych nie. Ograniczonoôê oznacza tu tyle, co mieszczenie sië
w caîoôci wewnâtrz koîa o pewnym promieniu. Moûna tu mówiê o
analogii do geometrii, bo przecieû liczbom zespolonym odpowiadajâ
punkty na pîaszczyúnie. Na przykîad kwadrat, odcinek czy zbiór
skoïczonej iloôci punktów jest figurâ ograniczonâ, bo zawsze
moûna dobraê koîo o takim promieniu, ûe bëdzie ono zawieraîo w
sobie owe zbiory. Ale np. prosta, póîprosta czy pîaszczyzna juû
nie jest zbiorem ograniczonym. Gdybyômy dla kaûdego c rysowali
sobie wszystkie punkty owego ciâgu, to zobaczylibyômy, ûe albo
wszystkie mieszczâ sië wewnâtrz zadanego koîa, albo czëôê wyîazi
poza to koîo. Ale tu pojawia sië pierwszy problem. Trzeba
narysowaê WSZYSTKIE wyrazy ciâgu. Ôwietnie, tyle ûe bëdziemy
czekaê do siódmej nieskoïczonoôci, aby cokolwiek zobaczyê na
ekranie, bo wyrazów ciâgu jest nieskoïczenie wiele.

W praktyce robi sië nieco inaczej. Dla wszystkich punktów ekranu
monitora (a raczej odpowiadajâcych im wartoôci c) liczymy N
pierwszych wyrazów ciâgu (N jest odpowiednio duûe). Nastëpnie
sprawdzamy warunek, czy wszystkie te punkty leûâ wewnâtrz koîa o
zadanym promieniu R, czyli czy zachodzi an^2+bn^2<R dla n=1,2,...,N
-- przy czym zn=an+bni. Jeûeli wszystkie N punktów speînia ten
warunek, to domniemujemy, ûe wszystkie nastëpne punkty teû go
bëdâ speîniaê i rysujemy na ekranie punkt, odpowiadajâcy
wspóîrzëdnym rozwaûanego wîaônie punktu c. Gdy czëôê punktów
wyîazi poza koîo, to nie stawiamy punktu. Potem bierzemy kolejny
punkt ekranu, obliczamy, jakiej wartoôci c on odpowiada, liczymy
N pierwszych elementów ciâgu, sprawdzamy warunek ograniczonoôci
itd., aû wreszcie trafi nas szlag, gdyû metoda ta jest niezwykle
czasochîonna. Napiszë kiedyô, jak przyspieszyê te ûmudne
obliczenia, czyniâc pewne przybliûenia i nie tylko.

No, ale co my tu mamy? Fajny rysunek, prawda? To jest wîaônie
zbiór Mandelbrota. Jest to po prostu zbiór tych wartoôci
parametru c, dla których wyrazy ciâgu {z0,z1,z2,z3...}, okreôlone
zaleûnoôciâ rekurencyjnâ zn+1=zn^2+c, leûâ wewnâtrz koîa o staîym
promieniu. I tu pierwszy kubeî zimnej wody: widaê wyraúnie, ûe
zbiór Mandelbrota jest czarno-biaîy, a nie kolorowy, jakby sië
komuô mogîo wydawaê. Kolorki we fraktalach biorâ sië stâd, ûe
zamiast stawiaê punkt (czarny) lub go nie stawiaê, stawiamy punkt
w kolorze zaleûnym od liczby punktów, mieszczâcych sië w kole.

Czas juû chyba pokazaê, co poûytecznego z tego wynika. Jak widaê,
obliczenia potrzebne do narysowania fraktala sâ wcale pokaúne,
ale od czego mamy komputery. Nadajâ sië one idealnie do tego,
zwîaszcza te o dobrej grafice (Amiga, he, he) i duûej mocy
obliczeniowej (tu gorzej). Niestety, trzeba dysponowaê albo
gumowâ cierpliwoôciâ, albo szybkim komputerem. Bez jednej z tych
dwóch rzeczy zwariujemy. Nie oszukujmy sië, Amiga staje sië
komputerem od 4-6 MB RAM-u, twardego dysku i procesora co
najmniej 030. Zresztâ popatrzmy na PC klo(w)ny -- 486 DX2 to dziô
codziennoôê, a peceta bez twardego ysku jeszcze nie widziaîem...
Jasne, ûe na piëêsetce teû moûna rysowaê w Deluxe Paint i pisaê w
AMOS-ie, ale jeôli chcemy cokolwiek policzyê, odpaliê jakiô
procesor tekstu, raytracer czy program graficzny typu ImageFX lub
ADPro, to sami widzimy, co sië dzieje. Cóû, "jak sië nie ma, co
sië lubi", to teû moûna, ale trzeba mieê nerwy ze stali.

Caîy ten mój monolog przetîumaczony na C przedstawia listing nr
1. Zgodnie z tradycjâ zakîadam jako takie uôwiadomienie w kwestii
programowania w C (przynajmniej takie, ûeby nie narobiê bîëdów
przy przeklepywaniu listingów lub wykryê podstawowe zrobione w
druku, jak to np. zdarzyîo sië w numerze czerwcowym). Oto plik
SCOptions dla kompilatora SAS/C 6.5

<l> MATH=STANDARD

CPU=68020

ERRORREXX

OPTIMIZE

LINK

OPTIMIZERTIME

<txt>przy czym w linië CPU= wpisz typ Twojego procesora.

Przyjrzyjmy sië bliûej programowi. Zdefiniowane wielkoôci da i db
to skoki czëôci rzeczywistej i urojonej parametru c, jakie
robimy, poruszajâc sië o jeden punkt ekranowy. Funkcja paleta()
ustawia paletë ekranu na odcienie szaroôci.  Wygenerowany obrazek
moûna potem wgraê do DPainta i ustawiê sobie paletë po swojemu,
co zresztâ -- jak widaê z ilustracji -- równieû zrobiîem.
Poniewaû obliczenia trwajâ doôê dîugo, umoûliwiîem przerwanie ich
po narysowaniu kaûdej linii.  Wystarczy w tym celu najechaê na
lewy górny punkt ekranu, gdy program skoïczy rysowaê aktualnâ
linië, przerwie pracë.  Uwaûaj, bo dotyczy to kaûdego otwartego w
danym momencie ekranu -- równieû Workbencha. Po wygenerowaniu
obrazka, aby skoïczyê pracë, naleûy zrobiê to samo. I to samo
naleûaîo zrobiê w programie z artykuîu o grawitacji (jak ktoô na
to nie wpadî, to dla niego naprawdë chyba tylko AMOS...).

Ze swojej strony przepraszam tylko za maleïki bîâd, a raczej
niedogodnoôê, we wspomnianym programiku. Dobrze jest, aby pod
koniec programu po kaûdym sprawdzeniu poîoûenia myszki odczekaê
np. sekundë. Inaczej zablokujemy procesor, co spowoduje znaczne
zwolnienie pracy caîego komputera. Moûna sië posîuûyê instrukcjâ
Delay(50), tak jak to zrobiîem tym razem. Po skompilowaniu
program naleûy uruchomiê z CLI, podajâc 5 parametrów: zakres
czëôci rzeczywistej parametru c, zakres czëôci urojonej i N.
Zakresy parametru c najlepiej podawaê "kwadratowe", tzn. o
dîugoôci zakresu czëôci rzeczywistej zbliûonej do dîugoôci czëôci
urojonej, aby uniknâê spîaszczenia lub rozciâgniëcia obrazka. N
to liczba pierwszych wyrazów ciâgu, jaka ma byê obliczana. Im
wiëksze N, tym dokîadniejszy rysunek, ale i dîuûsze oczekiwanie
na wynik obliczeï -- ma to znaczenie przy powiëkszaniu wycinka
fraktala. Przed samym uruchomieniem programu proponujë jeszcze
uruchomiê program GrabIFF, Quick Grab lub uaktywniê odpowiedni
moduî w MagicCX, aby po wygenerowaniu obrazka zgraê go sobie na
dysk.

Spójrzmy na rysunki od 1 do 6. Pierwszy przedstawia caîy zbiór
Mandelbrota, odpowiadajâcy zakresowi Re(c)=<-1.8,1>,
Im(c)=<-1.2,1.2>. Wystarczyîo tu N=100 pierwszych wyrazów ciâgu,
aby otrzymaê wyraúny obraz. Nastëpne obrazki przedstawiajâ
powiëkszenia kolejnych fragmentów brzegu zbioru Mandelbrota aû do
dwustu miliardów razy!!! Zwróê uwagë, ûe w miarë powiëkszania
trzeba zwiëkszaê N w celu uzyskania lepszej dokîadnoôci. Gdybyômy
tego nie zrobili, otrzymalibyômy bardzo zaciemniony, zamazany i
nieczytelny obrazek. Powiëkszaê moûemy teoretycznie w
nieskoïczonoôê, a praktycznie do momentu dojôcia do tak maîych
zakresów parametrów, ûe komputer przestanie je rozróûniaê. Nie
zabezpieczyîem programu przed takâ ewentualnoôciâ.

Jeûeli chodzi o czas generowania, to na narysowanie caîego zbioru
Mandelbrota (rys. 1.) czekaîem niecaîe póî godziny. Na ostatni
(rys. 7.) dane mi byîo czekaê caîy dzieï... Nie jest tragicznie,
ale wesoîo teû nie. Za tak dîugi czas obliczeï odpowiedzialny
jest gîównie algorytm -- bardzo prymitywny, ale za to
najprostszy. Na koniec dobra rada: jeôli chcesz podczas
generowania obrazków robiê sobie coô innego, to z pewnoôciâ
zauwaûysz spowolnionâ reakcjë systemu na wciskanie klawiatury.
Moûna temu zaradziê, manipulujâc opóúnieniem i czëstoôciâ
powtórzeï naciskanych klawiszy w systemowym programiku Input.

Miîej zabawy!

<przyp> Jeûeli podobajâ sië Wam artykuîy zwiâzane z problematykâ
mat-fiz-chem, to dajcie znaê (jeûeli nie -- równieû).  Napiszcie,
czego oczekujecie. Najciekawsze pomysîy na pewno uwzglëdnië.

Wszelkie uwagi moûecie kierowaê na e-mail:
[e-mail]