skočiť na obsah skočiť na menu

Sierpinského trojuholník 41B

Rozprávanie o Pascalovom a Sierpinskeho trojuholníku, fraktáloch, Assembleri a o tom ako som to všetko natlačil do 41 bajtov.

Pascalov trojuholník

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Tento trojuholník zostrojíme tak, že na začiatok napíšeme do prvého riadku jednotku. Do druhého riadku dve jednotky. Do tretieho riadku budeme písať čísla, ktoré sú súčtom dvoch čísel v riadku nad týmto číslom. Takto môžeme pokračovať až do nekonečna.

Pascalov trojuholník je matematicky vcelku zaujímavá vec pretože čísla v riadkoch sú koeficienty členov polynómu, ktorý vznikne roznásobením výrazu (a + b)n kde n je číslo riadku + 1.

Napríklad pre (a + b)3 bude n = 3 a tak budeme hľadať koeficienty v 4. riadku Pascalovho trojuholníka, ktoré sú 1, 3, 3, 1. A naozaj (a + b)3 = 1a3 + 3a2b + 3ab2 + 1b3.

Sierpinského trojuholník

1 1 1 1 1
1 0 1 0
1 1 0
1 0
1

Teraz si predstavme, že si Pascalov trojuholník prepíšeme tak, že tam kde sú párne čísla dáme 0 a tam kde sú nepárne dáme 1. Teraz tento trojuholník ešte prekreslíme tak, že jednotky na ľavej strane budú na osi y a jednotky na pravej strane trojuholníka budú na osi x.

Trojuholník teda tvoríme tak, že číslo, ktoré chceme získať je súčtom čísla nalavo od neho a čísla nad ním. Samozrejme uvažujeme iba čísla 0 a 1 — pracujeme v binárnej sústave. Čiže 1 + 1 = 0.

Sierpinského trojuholník

Teraz už len stačí všade tam kde je 1 nakresliť bod a kde je 0 bod nakresliť inou farbou. Ak toto urobíme pre na dostatočne veľkej ploche dostaneme zaujímavý obrázok.

Ide o jednoduchý prípad fraktálu. Čiže útvaru, ktorého nejaká časť sa podobá na útvar celý. Existujú samozrejme aj komplexnejšie fraktály a medzi tie najznámejšie patrí určite Mandelbrotova množina a Pytagorov strom. Ale to je už iné rozprávanie.

Assembler

Až teraz sa dostáveme sa ku koreňu veci. Zaumienil som ti totiž naprogramovať program, ktorý vykreslí Sierpinského trojuholník na celú obrazovku. V mojom prípade 640x480 bodov. Na tomto samotnom by nebolo nič zvláštne a tak som si povedal, že ten program musí byť čo najkratší.

Prvý pokus mal niečo cez 60 bajtov ale za pol hodinku som to skresal na 54. O deň neskôr ma napadla finta využívajúca výpočet z predchádzajúceho kroku a tak som sa dostal pod hranicu 50 bajtov. Nakoniec mi hvge poradil kratší spôsob ukončenia programu, ešte som to trochu odladil a tak som sa dostal na magickú hranicu 41 bajtov.

Tu je tých 41 bajtov (sierp3.com), na ktoré som tak nesmierne hrdý:

B0 11 CD 10 BA E0 01 B9 7F 02 4A B0 01 E9 08 00 FE C4 42 CD 10 4A 30 D8 B4 0C 88 C3 CD 10 E2 F0 85 D2 75 E3 30 E4 CD 16 C3

Pokiaľ by niekoho zaujímal kompletný zdroják tak si ho môže v kľude stiahnuť. Kompilovať ho však bude treba cez NASM.

(1. január 2004)