Obsah
1. Fraktály v signaturách a další hacky
2. Signatury psané v céčku
2.1 Mandelbrotova množina
2.2 Juliova množina
2.3 Sierpinského trojúhelník
3. Signatury v PostScriptu
3.1 L-systémy
3.2 Mandelbrotova množina
3.3 Dynamické systémy
4. Fraktály v Basicu
4.1 Mandelbrotova množina vykreslená v QBasicu
4.2 Bifurkační diagram vykreslený v QBasicu
5. Obsah dalšího pokračování tohoto seriálu
1. Fraktály v signaturách a další hacky
Algoritmy pro generování fraktálů různých typů se poměrně často objevují i v takzvaných signaturách. Signaturou je myšlen krátký programový kód o délce dvou až pěti řádků (délka řádku je typicky 60, 72, 79 či 80 znaků), který vykonává nějakou zajímavou funkci (podle netiquetty by měly mít signatury maximálně čtyři řádky kratší než 80 znaků). Vzhledem k tomu, že se do tak malého množství znaků musí směstnat mnohdy složitý program, jsou signatury většinou psány velmi zhuštěně a krypticky (někteří lidé si na nečitelnosti signatur zakládají). Mnohé signatury jejich autoři kvůli jejich komplikovanosti nominovali do IOCCC, neboli International Obfuscated C Code Contest (http://www.ioccc.org/). Že se v signaturách nachází i různé těžko pochopitelné „perly“, dokazuje následující dvouřádkový program o délce pouhých 160 znaků, který po svém překladu a spuštění vypíše hodnotu známého čísla π na 800 desetinných míst:
int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c
-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);} Mezi oblíbené signatury patří programy, které po svém spuštění vypíšou kopii svého zdrojového kódu (self printings, quine – http://en.wikipedia.org/wiki/Quine_%28computing%29), programy pro výpočet prvočísel apod. Další netradiční signatura obsahuje takzvaný polygot, tj. zápis kódu, který je možné přeložit nebo interpretovat více překladači/interpretery (http://ideology.com.au/polyglot/). Čím rozdílnější je daná dvojice programovacích jazyků, tím zajímavější a na pochopení obtížnější je i vytvořená signatura. Zde uvedený polygot představuje současně (smysluplný) Céčkový a Cobolovský program:
char *o, *c="%.9s%.7s%.7s\n"; extern void printf(char*, ...); int main(int d,
char**z){int b,g,l,n;d=d/d;l=*(c+d+d)-*(c+d);g=*c-d++-l--;n=d*d;b=l+n++;d-=d;
o = " DISPLAY'tmdg@tmdg';,,;'.co.uk '*>"+g++;printf(c,o-++b,o+l,o);l = ~++n;
o = " DISPLAY'http://www.tmdg.co.uk/ ' *>"+g;printf(c,o-++b,o+l,o);exit(d);} Mnoho signatur uvedených v následujících kapitolách jsem získal na stránce Charlie Gibbse, jehož stránky získaly ocenění Geek Site of the Day.
2. Signatury psané v céčku
Pravděpodobně největší množství „programových“ signatur bylo vytvořeno v programovacím jazyku C. Není divu, protože se jedná o jazyk vybavený velkým množstvím operátorů, sevřenou syntaxí a také je možné v některých případech porušit normu ANSI C (či ISO C) a celý program tak o několik znaků zkrátit, například neuvedením návratového typu funkce main, příkazu return na konci této funkce apod. Většinou se také nevkládají ani hlavičky funkcí standardní céčkové knihovny, i když jsou tyto funkce v programech použity. Z těchto důvodů může být překlad dále uvedených programů problematický, většina překladačů vypíše varovná hlášení (warnings) a některé překladače dokonce programy ani nepřeloží (typicky se jedná o překladače C++, které se pouze tváří jako překladače C).
2.1 Mandelbrotova množina
Nejvíce céčkových „fraktálních“ signatur vykresluje po svém spuštění na konzoli Mandelbrotovu množinu, protože se jedná o výpočet poměrně jednoduchý, snadno zkrátitelný na minimální velikost a přitom generující zajímavé a známé obrázky. Tyto programy se odlišují svou složitostí, použitým „rozlišením“ (typicky 80×24, 80×25 a 80×50 znaků) a také způsobem zvýraznění počtu iterací. Následující tři signatury pochází od Bernharda Muenzera:
main(){char*c=" _.+=#\n)rezneuM drahnreB(xx.xxx@xxx";int x,t,y;float a,
b,d;for(y=0;y<25;y++){for(x=0;x<80;x++){t=b=d=0;do{a=b*b-d*d-2.1+.035*x
;d=2*b*d+.088*y-1.1;b=a;t++;}while(t<32&&b*b+d*d<4);putchar(c[x>79?6:y>
23&&x<28?34-x:t>31?0:t>>4?5:t>>3?4:t>>2?3:t>>1?2:1]);}}} /*xxx@xxx.xx*/ int m,u,e;float g,s,f;char*c=" _.+=#\n)rezneuM drahnreB(xxxxxx@xxx";ma\
in(){for(e=0;e<25;e++){for(m=0;m<81;m++){u=s=f=0;do{g=s*s-f*f-2.1+.035*
m;f=2*s*f+.088*e-1.1;s=g;u++;}while(u<32&&s*s+f*f<4);putchar(c[m>79?6:e
>23&&m<28?34-m:u>31?0:u>>4?5:u>>3?4:u>>2?3:u>>1?2:1]);}}}/*xxx@xxx.xx*/ Třířádková verze Mandelbrotovy množiny od Bernharda Muenzera je sice novější a kratší, ale vykresluje množinu poněkud pokřivenou, protože podmínka pro ukončení výpočtu každého řádku musela být zjednodušena.
int m,u,e;float g,s,f;char*_=")xx.xxx@xxx(rezneuM drahnreB\n";main(){for(
;e<1944;){u=s=f=0;do{g=s*s-f*f-2.1+.035*(m=e%81);f=2*s*f+e/81*.088-1.1;s
=g;}while(++u<19&&g*s+f*f<4);putchar(_[++e>1863&&m<28?27-m:m>79?28:u]);}} Další podobná verze pochází od Wei-Hwa Huanga:
/* xxxxxx@xxx.xxxxxxx.xxx (Wei-Hwa Huang) */
int m,u,e=0;float l,_,I;main() {for(;e<1863; putchar((++e>924&&952>
e?60-m:u) ["\n ude.hcetlac.occ@gnauhw ]"])) for(u=_=l=0;(m=e%81)
<80&&I*l+_*_ <6&&25>++u;_=2*l*_+e/81*.09-1,l=I)I=l*l-_*_-2+.035*m;} Mandelbrotova množina od Marko Aaltoa využívá pro vykreslování řídicí kódy terminálu, nefunguje tedy korektně například v konzoli operačních systémů MS-Windows:
/* xxxxx.xxxxx@xxxxxxxx.xx | http://www.helsinki.fi/~maaalto/ */
main(){char h[2001]=" Ma+\x1b[H",*k,c;float z=20,D,a,i,s,y;for(;k=h+7,z*=
8,z>8e-4;puts(h))for(s=.119+z;(k-h-7)%80<1?y=1.4+z,s-=z/15:k-h-1768;y-=z
/40,*k++=h[c/4&3])for(c=a=D=0;--c&&a*a+D*D<4;a=a*a-D*D-y,D=2*i*D+s)i=a;} Carson Cheung vytvořil signaturu pro generování Mandelbrotovy množiny, jejíž obraz je složený z ASCII znaků „World!“.
float o=0.075,h=1.5,T,r,O,l,I;int _,L=80,s=3200;main(){for(;s%L||
(h-=o,T= -2),s;4 -(r=O*O)<(l=I*I)|++ _==L&&write(1,(--s%L?_<L?--_
%6:6:7)+"World! \n",1)&&(O=I=l=_=r=0,T+=o /2))O=I*2*O+h,I=l+T-r;} Variantu Mandelbrotovy množiny od E. B. van Koperena se mi nepodařilo korektně spustit, chyba se pravděpodobně nachází v příkazu pro přechod na nový řádek:
/* Try me and stagger. With x size as parameter! y size=auto scaling!*/float R,
y=1.5,x,r,A,P,B;int u,h=80,n=80,s;main(c,v)int c;char **v;{s=(c>1?(h=atoi(v[1]
)):h)*h/2;for(R=6./h;s%h||(y-=R,x=-2),s;4<(P=B*B)+(r=A*A)|++u==n&&putchar(*(((
--s%h)?(u<n?--u%6:6):7)+"World!\n"))&&(A=B=P=u=r=0,x+=R/2))A=B*2*A+y,B=P+x-r;} Mandelbrotova množina vykreslovaná programem Davida Johnstona:
float l,I,Q,_,o;int E;main(){I=1.125;while(I>=-1.225){for(l=
-2;l<=1;l+=3/79.0){Q=_=0;for(E=127;Q*Q+_*_<4.0&&--E>32;){o=Q
;Q=Q*Q-_*_+l;_=2*o*_+I;}putchar(E);}putchar(10);I-=9/88.0;}} Velmi zajímavá pouze dvouřádková verze, celkově se jedná o jeden z nejkratších kódů pro vytvoření Mandelbrotovy množiny:
main(c){float t,x,y,b=-2,a=b;for(;b-=a>2?.1/(a=-2):0,b<2;putchar(30+
c),a+=.0503)for(x=y=c=0;++c<90&x*x+y*y<4;y=2*x*y+b,x=t)t=x*x-y*y+a;} Varianta Laurenta Demaillyho (všimněte si zpětně zapsané e-mailové adresy):
main(){char x,y=-1,t,n,*c="-=+X# \nrf.mpsbo.toylph@ld";while(++y<25)
{for(x=0;x<80;){float a,b,d,i=2.2/25*y-1.1,r=2.8/80*x++-2.1;t=b=d=0;do{
a=b*b-d*d+r;d=2*b*d+i;b=a;}while(++t<32&&b*b+d*d<4);for(n=0;t&~1;t/=2,
n++);putchar(c[x>79?6:y>23&&x<19?25-x:n]);}}} Poněkud netradičním způsobem vykreslená Mandelbrotova množina od Jay R. Hilla (odborníka na fraktály a dynamické systémy, http://www.geocities.com/CapeCanaveral/Lab/3825/), ve které se zvýrazní i vnitřní oblasti s periodou 1 a 2:
int main(){float g,s,f,r,i;char*_="/,;<mhl/brnoAmmhik<mmhI!/S!x`K\n";int m,u,e
=0;_[30]++;for(;e<3919;){u=(256*(s=(r=.0325*(m=e%80)-2)*r+(i=.047*(e/80)-1.128
)*i)-96)*s+32*r<3?22:16+32*r+16*s<1?29:0;if(u==(s=f=0))do g=s*s-f*f+r;while((f
=2*s*f+i)*f+(s=g)*g<4&&++u<25);putchar(_[++e>3840&&m<30?29-m:m>78?30:u]^1);}} Existuje i kratší verze předchozího programu; zajímavé je především použití znaků „,“ a „-“, které navozují dojem plasticity:
main(){int f,g,h=0;float a,b,c,d,e;for(;h<3920;putchar("!/-,;<:lnb/bh`r\
/ylqbAmmhI/S/x`K\013"[++h>3840&&g<25?31-g:g>79?31:f]^1))if((f=(256*(c=(d
=(g=1+h%80)/31.-2)*d+(e=.047*(h/80-24))*e)-96)*c+32*d<3?24:16+32*d+16*c<
1?30:0)==0)for(a=d,b=c=0;(b=2*b*c+e)*b+(c=a)*a<=4&&++f<26;a=d-b*b+c*c);} Mandelbrotovy množiny vykreslované signaturami Andrewa Garrarda:
/* o._.o (C) 1996 Andrew Garrard, xxxxxxxxxx@xxxxxxx.xxxxx.xx.xx o~\_/~o */
/* ((^)) */main(c){float x,y=2,X,Y,Z;for(;(x=-2)<(y-=.1);puts(""/* (/\ /\) */
/* O)_(O */ ))for(;(X=x+=.05)<2;c=printf("%c"," .-:|O8M#"[c])) /* (\@o@/) */
/* O/ \O */for(Y=y;X*X+Y*Y<4&&c++<8;Z=x+X*X-Y*Y,Y=y+2*X*Y,X=Z);}/* ~~~ ~~~ */ /* /)_(\ */int main(void) {float x,y=2,X, /* Yet m f */
/* (/. .\) */Y,_,i;int c;for(;(y-=.1)>-2;){ /* o a */
/* \(T)/ */for(x=-2;(x+=.1)<2;){X=x;Y=y;c /* r . c */
/* () () */=0;while((X*X+Y*Y)<=4&&c++<7){ /* f e g t */
/* ()-() */_=x+X*X-Y*Y;i=2*X*Y+y;X=_;Y=i; /* r i o */
/* Andrew */}printf("%c",*(" .-:|O8M#"+c)) /* o s r */
/* Garrard */;}printf("\n");}} /* fluppeteer m the y */ Program pro generování Mandelbrotovy množiny do souboru typu PGM (Portable GrayMap) od Roberta Harleye. Výstup z tohoto programu je zapotřebí přesměrovat do souboru s koncovkou .pgm:
float x,y=1,s=1./128,X,Y,V;main(i){for(puts("P5 257 127 63");X=Y=0,x?/*Rob H.*/
x+=s,1:(x=-2,y-=s);putchar(i))for(i=64;--i&&X*X+(V=Y*Y)<4;X=X*X-V+x)Y=2*X*Y+y;} V signatuře Johna Holdera je pro výstup použita funkce write():
float o=0.075,h=1.5,T,r,O,l,I;int _,L=80,s=3200;main(){for(;s%L||
(h-=o,T= -2),s;4 -(r=O*O)<(l=I*I)|++ _==L&&write(1,(--s%L?_<L?--_
%6:6:7)+"Mandel \n",1)&&(O=I=l=_=r=0,T+=o /2))O=I*2*O+h,I=l+T-r;}
/* xxxxxxx@xxxx.xxx - UNIX specialist, Paranet, Inc, Denver,CO */ Signatura pro vykreslení Mandelbrotovy množiny (spolu s ASCII artem), jejímž autorem je Mark VandeWettering:
/* __ __ __ ____ __*/ float e,a,b,c,d;main(i){for(;b<4;b+=.1){for(a=0;
/*| \/ |\ \ / /\ \ / /*/ a<4;a+=.06){c=d=0;for(i=99;--i&&c*c+d*d<4;)e=c*c
/*| |\/| | \ V / \ \/\/ / */ -d*d+a-2,d=2*c*d+b-2,c=e;putchar("X =."[i&3]);}
/*|_| |_ark\_/ande\_/\_/ettering <xxxxx@xxxxxxxxxxxxxxx.xxx> */ puts("");}} Následující signaturu jsem používal v době mého působení na FIT VUT v Brně. Jediná celočíselná proměnná, která se v tomto programu nachází, se jmenuje _ a pro zkrácení programu je deklarována jako první argument funkce main(), tj. na místě argumentu argc. I při zavolání programu s nějakými parametry (tj. argc>1) se však nic nestane, protože je tato proměnná ve výrazu P=a=_=0 nastavena na nulovou hodnotu.
main(_){float P,a,v,e,l=-1.5;for(;l<1.439;l+=.06)for(e=-2;e<1.94;e+=
.05){P=a=_=0;while(P*P+(v=a*a)<4&&_++<13)a=2*P*a+l,P=P*P-v+e;putchar
(" .,`-:;+=:..: H\n"[e>-1.96?_:15]);}puts("\nPavel Tisnovsky");}
2.2 Juliova množina
Výpočet Juliovy množiny se provádí prakticky stejným způsobem jako výpočet množiny Mandelbrotovy, pouze je nutné zajistit inicializaci komplexní konstanty c. Zajímavým způsobem tento problém vyřešil Andrew Garrard (tento autor mimochodem přispíval i do IOCCC), jehož verze Juliovy množiny je závislá na čase spuštění aplikace – viz použití funkcí sin(), cos() a time():
/* o._.o Andrew Garrard - xxxxxxtxxx@xxxxxxx.xxxxx.xx.xx */#include <time.h>
/* ((^)) */main(c){float x,y=2,X,Y,Z,q,t;q=sin(time(0))*1.3;t=sqrt(1.69-q*q);
/* O)_(O */for(;(x=-2)<(y-=.1);puts(""))for(;Y=y,(X=x+=.05)<2;c=printf("%c",c
/* O/ \O */[" .-:|O8H#"]))for(;X*X+Y*Y<4&&++c<8;Z=q+X*X-Y*Y,Y=2*X*Y+t,X=Z);}
2.3 Sierpinského trojúhelník
I známý Sierpinského trojúhelník (někdy označovaný názvem Sierpinského kobereček, Sierpinského krajky atd.), se kterým jsme se seznámili při popisu L-systémů a IFS, je možné generovat velmi krátkým programem, což dokazuje následující signatura:
char c[160],z;main(x,d){for/*/ Brendan McKeon /*/(x=159;x--
;c[x]=32);c[79]=z;c[39]=88/*/ xxxxxxx@xxxx.xxx.xx /*/;for(d=31;x
=78,puts(c+z),d--;z=80-z)/*/ http://alf2.tcd.ie/~bmckeon /*/for(;--x;c[x
+80-z]=88-56*!(c[z-!0+x]/*/ 4th Yr. 'Comp Sci' 'Student'/*/-c[z+x+1]));}
3. Signatury v PostScriptu
Mnoho programových signatur pro generování fraktálů se objevuje také ve formě PostScriptových programů. PostScript jako jazyk pro popis tiskové stránky je současně i plnohodnotným programovacím jazykem postaveným na Forthu (viz seriál o tomto programovacím jazyce, který vyšel na Rootu minulý rok). Níže uvedené programy je možné zobrazit například pomocí aplikací GhostScript a GhostView, nebo je lze poslat na PostScriptovou tiskárnu (to ovšem například u generátorů fraktálů nedoporučuji, zejména u síťových školních či podnikových tiskáren :-). Převod na program v PostScriptu je jednoduchý – copy and paste do souboru s koncovkou .ps.
3.1 L-systémy
Fraktální keř vytvořený pomocí L-systému. Zde se ukazuje mocnost jazyka PostScript: samotný operátor def, který slouží pro vytváření nových funkcí, je možné uložit do jiné funkce (v tomto případě d), která se pak chová jako makro.
%! -Markku Rossi
/d{def}def/t{translate}d /r{rotate}d /F{0 0 moveto 0 10 rlineto stroke 0 10
t }d/P{22 r}d/M{-22 r}d/S{gsave}d/R{grestore}d 240 90 t/E{dup 1 eq{F}{dup 1
sub E E M S M E P E P E R P S P E M E M E R pop} ifelse} d 5 E pop showpage
3.2 Mandelbrotova množina
Mandelbrotova množina v 294 bytech zdrojového kódu:
/D{def}def /d{.00017 add D}D /C{2 copy dup mul exch dup mul}D /g 150 string
D /y .29 D 150 150 8[.4 0 0 .4 -45 -90]{/x -1.2 D 0 1 149{x y /n 300 D{/n n
5 sub D C exch sub x add 3 1 roll 2 mul mul y add C add 4 gt n 5 eq or{exit
}if}loop pop pop g exch n put /x x d}for /y y d g}image showpage
3.3 Dynamické systémy
Fraktální dynamický systém od Aluna Jonese:
/d{def}def/a{add}d/s{sub}d/u{usertime}d % Alun Jones, IBS, UW Aberystwyth
/x 0 d/y 0 d 9 9 scale 35 47 translate/b u d .1 setlinewidth{u b s 6e4 gt
{exit}if/x x 4 a d/v 1 x s d/x y 2 x mul 3 s abs sqrt x 0 lt{neg}if a d/y
v d x y moveto .1 0 rlineto stroke}loop showpage% You may need %!PS-Adobe Další fraktální dynamický systém:
/d{def}def/a{add}d/s{sub}d/r{rand 99 mod 99 div}d/u{usertime}d/x 0 d/y 0 d 320
430 translate 9 9 scale/n -1 d/b u d .1 setlinewidth{/n n 1 a d n 999 mod 0 eq
{r r r setrgbcolor u b s 6e4 gt{exit}if}if/x x 4 a d/v 1 x s d/x y 2 x mul 3 s
abs sqrt x 0 lt{neg}if a d/y v d x y moveto 0.1 0 rlineto stroke}loop showpage IFS systém od Andrewa C. Bulhaka:
/d/def/s/scale/u/dup/f/forall{load def}{loop}stopped pop/r{u 1 lt{-1 0 moveto 1
1 lineto stroke}{[[(ha_a0\211)(db\\h\(~)(eVhdOj)(jd_dbd)(dh\\bT\200)(f_ab^\211)
(c]ffe\201)(`@h`x\200)(cZhd#h)(hb^d0v)(`Lh`8t)(eVhd\223~)(gj^a\230j)(h_ab\210a)
(gd^c\211\205)]{[exch{96 sub}f]}f]{gsave 1 64 div u s concat u 1 sub r grestore
}f}ifelse pop}d 240 u s 1.25 1 translate 4 r showpage% -
4. Fraktály v Basicu
Basic se pro psaní signatur a dalších krátkých kryptických programů moc nehodí, protože má poměrně chudou sémantiku příkazů, dlouhé názvy příkazů (ukončení smyčky typu for klíčovým slovem next místo závorky, slovo then apod.) a některé interpretery automaticky vkládají mezi jednotlivé operandy mezery. To je případ i známého interpreteru QBasic, ve kterém jsou napsány následující dva ukázkové programy. Mezi jediné výhody patří v případě QBasicu to, že se dá velmi jednoduše nastavit grafický režim a vykreslit bod, úsečku či další jednoduchý geometrický tvar. Další výhodou je (alespoň při psaní signatur), že se nemusí proměnné předem deklarovat, což zápis poněkud zkracuje.
4.1 Mandelbrotova množina vykreslená v QBasicu
První ukázkový Basicový program je velmi jednoduchý. Nejprve se nastaví známý grafický režim VGA s rozlišením 320×200 pixelů a 256 barvami. Potom se přímočarým způsobem vypočtou barvy bodů podle iteračního vztahu pro Mandelbrotovu množinu. Vykreslení bodů je provedeno příkazem PSET(). Kvůli zkrácení kódu jsem nepoužil celočíselné datové typy a u příkazů NEXT není uveden název řídicí proměnné (není to striktně vyžadováno). Celý program by bylo možné zkrátit vynecháním přebytečných mezer, neboť si je interpreter při prvním načtení programu doplní automaticky.
SCREEN 13: y = -1.5: FOR j = 0 TO 200: x = -2: FOR i = 0 TO 320: a = 0: b = 0
FOR k = 1 TO 256: c = a * a: d = b * b: b = 2 * a * b + y: IF c + d > 4 THEN EXIT FOR
a = c - d + x: NEXT: PSET (i, j), k: x = x + .0125: NEXT: y = y + .015: NEXT 4.2 Bifurkační diagram vykreslený v QBasicu
Ve druhém Basicovém programu je nejprve nastaven grafický režim VGA 640×480 pixelů se šestnácti barvami. V tomto rozlišení je posléze vykreslen bifurkační diagram, jehož významem pro prakticky všechny dynamické procesy jsme se zabývali v prvních částech tohoto seriálu. V programu je využito jednoduchého filtrování hodnot pro hodnotu počitadla iterací menšího než 10 – tímto jednoduchým způsobem bylo dosaženo ustálení počítaných hodnot a prvotní „chaos“ se nezobrazuje.
SCREEN 12: FOR x = 10 TO 620: p = .5
g = (x + 120) / 200!: FOR y = 0 TO 100
IF (y > 10) THEN PSET (x, 100 + 240! * p)
p = g * p * (1! - p): NEXT y: NEXT x Některé další Basicovské programy, určené především pro tvorbu orbitů dynamických systémů, budou uvedeny příště.
5. Obsah dalšího pokračování tohoto seriálu
V následujícím pokračování seriálu o fraktálech si ukážeme některé signatury pro generování fraktálů, které jsou vytvořeny v dalších oblíbených programovacích jazycích, zejména Perlu, Pythonu, Lispu a dokonce ve Vimu. Také si ukážeme některé krátké programy pro vytváření fraktálů, které jsou napsané v assembleru.
