Tato programátorská rekreace může přinést pocit nezávislosti, že dokážeme dělit bez kalkulátoru, zajímavý vhled do samotných principů aritmetických operací, nebo pocit úspěchu, že jsme dokázali něco optimalizovat na rychlost a spolehlivost. Budeme schopni pokračovat i za desetinnou nebo šestnáctinnou čárku, bez omezení počtu číslic operandů.
V nouzových případech, například vybité baterie, je algoritmus i prakticky použitelný. Možná by byl efektivní i jako algoritmus dělení, pokud programujeme rutiny pro operace nad dekadickými čísly neomezené délky. Kdybych článek napsal o 200 let dříve, kdy se počítalo ručně, asi by mi utrhali ruce.
Abychom pochopili nejen, jak algoritmus dělení funguje, ale hlavně jak se k němu došlo, a jak můžeme efektivní algoritmus na dělení vystavět úplně z ničeho, vrátíme se k základům, tedy praktickým problémům, z kterých lidstvo tyto operace odvodilo.
Modelový praktický problém
Maminka koupila hroznové víno se 133 (dělenec) kuličkami a teď ho bude rozdělovat svým 5 (dělitel) dětičkám. Má požadavek, aby každé dítko dostalo stejně. Tento požadavek je charakteristický pro proces dělení, bez něj by to jen bylo náhodné rozdávání hroznového vína.
Navrhnout základní algoritmus na dělení je hrozně jednoduché. To, čemu říkáme algoritmus dělení, je už jen rychlostní optimalizace tohoto intuitivního primitivního algoritmu.
Základní algoritmus
Maminka se pokusí z keříku otrhat stejný počet kuliček jako je počet dětiček. Pokud se jí to nepovede, skončí. Pokud se jí to povede, otrhané kuličky dětičkám rozdělí, každé dostane jednu. Pak postup (primitivní cyklus) opakuje. Počet kuliček, které jedno dítě na konci bude mít, je výsledek operace dělení. Jeden cyklus primitivního dělení odpovídá zvýšení podílu o 1.
Problém základního algoritmu
Problém algoritmu je, že je sice teoreticky korektní, ale v některých každodenních situacích selhává. Příklad: stavební firma staví dva identické kurty na plážový volejbal. Zavolala do stavebnin, přijela sklápěčka a vyklopila 1 136 636 363 (jednu miliardu sto třicet šest miliónů třista šedesát tři tisíce šest set třicet šest) zrnek písku. Teď je potřeba zrnka písku rozdělit rovnoměrně na oba kurty. Čili stavebník odpočítá tolik zrnek, kolik je kurtů… Za 36 let, 3 dny, 8 hodin, 33 minut a 56 sekund (a co když během toho byla přestupná sekunda?) nepřetržité práce bude mít písek rozdělený mezi oba kurty. Asi vidíte, v čem je problém.
Stavebník je člověk vzdělaný základní školou a tak ví, že připsáním nuly za číslo se toto vynásobí desíti. A tak si práci urychlí: neodpočítá 2 zrnka, ale rovnou 20. A na každý kurt nehází 1 zrnko, ale rovnou 10 naráz.
Platí to i pro větší počet nul. Pokud připíše 6 nul, bude odpočítávat 2 000 000 zrnek naráz, a na každý kurt bude házet po 1 000 000 zrncích. 1 000 000 zrnek si může odpočítat na váhu a uvidí, že váží 4,4 kg. Pak už nemusí počítat, stačí odvažovat.
Je tu ale trochu zádrhel. Postupným ubíráním 2 000 000 zrnek z původního množství 1 136 363 636 zrnek se dostane do situace, že mu zbývá už jen 363 636 zrnek a v této situaci už navážit 2 000 000 zrnek nelze.
Stavebník proto musí snížit počet přidaných nul tak, aby se do zbytku vešel. A pak může dál ubírat. Dělení je proces ubírání.
BCD
Další urychlení spočívá v následujícím: maminka si předpočítá 2-, 4– a 8– násobek počtu dětí. Získá je postupným násobením dvěma. Násobení dvěma udělá tak, že sečte číslo samo se sebou. Napíše si na papír:
5 = 1x počet dětí +5 = 10 = 2x počet dětí +10 == 20 = 4x počet dětí +20 == 40 = 8x počet dětí
Tomuto se říká BCD – Binary Coded Decimal. Součtem číslic 1, 2, 4, 8 (mocnin dvojky) se dá spočítat libovolná číslice 0–9 (dekadická). Funguje to tedy jako binární čísla, proto se tomu říká BINARY coded decimal. Součtem 1-, 2-, 4– a 8– násobků se dá vyrobit 0–9 násobek. U větších dělitelů se tak vyhneme tomu, abychom museli dělitele pokaždé zdlouhavě a namáhavě násobit nějakou číslicí, jako ve školním algoritmu dělení.
Maminka začne číslem 133. Má paletu 4 čísel, které může odečítat: 5 (podíl 1), 10 (podíl 2), 20 (podíl 4) a 40 (podíl 8). Může i přidávat nuly – za číslo z palety i za odpovídající podíl je ale potřeba přidat stejný počet nul, jinak vznikne špatný výsledek! Aby se jí to do 133 ještě vešlo, zvolí číslo 10 (odpovídá podílu 2) a přidá jednu nulu, takže bude mít 100 (odpovídá podílu 20). Doprava si napíše 20, jako že odsimulovala 20 primitivních cyklů dělení, nebo přihodila 20 k podílu. Dále postupuje analogicky:
133 20 -100 === 33 -20 4 == 13 -10 2 == 3
Zbylo jí 3 a dál už to jde jenom desetinnými čísly. Sečte počty odsimulovaných primitivních cyklů vpravo: 20+4+2=26. Vyšlo jí, že 133/5=26 a zbytek 3. Pokud
by chtěla dělit i na desetinná čísla, šlo by to takto:
133, 20, -100, === 33, -20, 4, == 13, -10, 2, ==== 3,0 -2,0 0,4 === 1,0 0,2
Vyšlo jí, že 133/5=20+4+2+0,4+0,2=26,6
Desetinu primitivního dělícího cyklu by mohla realizovat tak, že by kuličky rozřízla na 10 dílků a dětem pak rozpočítala tyto desetinky (pokud by si chtěla vyloženě utrhovat od úst a nechtěla by ani ty 3 kuličky sama sníst).
Dělení hexadecimální
Vytiskneme si odečítací tabulku na papír a můžeme už dělit, zbytek algoritmu je stejný.
Odčítání: ========= 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1F 1E 1D 1C 1B 1A 19 18 17 16 15 14 13 12 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 A B C D E F 1 0 1F 1E 1D 1C 1B 1A 19 18 17 16 15 14 13 12 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 1 2 3 4 5 6 7 8 9 A B C D E F 2 1 0 1F 1E 1D 1C 1B 1A 19 18 17 16 15 14 13 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 1 2 3 4 5 6 7 8 9 A B C D E F 3 2 1 0 1F 1E 1D 1C 1B 1A 19 18 17 16 15 14 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 0 1 2 3 4 5 6 7 8 9 A B C D E F 4 3 2 1 0 1F 1E 1D 1C 1B 1A 19 18 17 16 15 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 0 1 2 3 4 5 6 7 8 9 A B C D E F 5 4 3 2 1 0 1F 1E 1D 1C 1B 1A 19 18 17 16 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 0 1 2 3 4 5 6 7 8 9 A B C D E F 6 5 4 3 2 1 0 1F 1E 1D 1C 1B 1A 19 18 17 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 0 1 2 3 4 5 6 7 8 9 A B C D E F 7 6 5 4 3 2 1 0 1F 1E 1D 1C 1B 1A 19 18 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 0 1 2 3 4 5 6 7 8 9 A B C D E F 8 7 6 5 4 3 2 1 0 1F 1E 1D 1C 1B 1A 19 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 0 1 2 3 4 5 6 7 8 9 A B C D E F 9 8 7 6 5 4 3 2 1 0 1F 1E 1D 1C 1B 1A A A A A A A A A A A A A A A A A 0 1 2 3 4 5 6 7 8 9 A B C D E F A 9 8 7 6 5 4 3 2 1 0 1F 1E 1D 1C 1B B B B B B B B B B B B B B B B B 0 1 2 3 4 5 6 7 8 9 A B C D E F B A 9 8 7 6 5 4 3 2 1 0 1F 1E 1D 1C C C C C C C C C C C C C C C C C 0 1 2 3 4 5 6 7 8 9 A B C D E F C B A 9 8 7 6 5 4 3 2 1 0 1F 1E 1D D D D D D D D D D D D D D D D D 0 1 2 3 4 5 6 7 8 9 A B C D E F D C B A 9 8 7 6 5 4 3 2 1 0 1F 1E E E E E E E E E E E E E E E E E 0 1 2 3 4 5 6 7 8 9 A B C D E F E D C B A 9 8 7 6 5 4 3 2 1 0 1F F F F F F F F F F F F F F F F F 0 1 2 3 4 5 6 7 8 9 A B C D E F F E D C B A 9 8 7 6 5 4 3 2 1 0 Násobení dvěma: =============== 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 2 4 6 8 A C E 10 12 14 16 18 1A 1C 1E
Cool by mi přišlo zadrátovat hexadecimální odčítačku přímo do analogového „FPGA“ mozku. Vstupy nejsou na krajích tabulky, ale v každé vertikální trojici je nahoře menšenec, uprostřed menšitel a vespod rozdíl. To je proto, že neurony mají lokální pole, tzv. receptive field, z kterého integrují informaci. Teoreticky se tato tabulka častým používáním zapíše do mozku spíše než ta v klasickém školním učení.
Také se předejde nutnosti sledovat řádky a sloupce a chybě, když se přeskočí na vedlejší řádek nebo sloupec.
Odhaduji, že pro kvalitní funkci bude potřeba každé políčko tabulky procvičit tak stokrát, celkem tedy odečíst 25 600 hexadecimálních míst. Pokud budeme sčítat 1 místo za 2 sekundy, bude to trvat 14 hodin nepřetržité práce.
Při odčítání budeme vyšší číslici menšence (pozice šestnáctek) psát o řádek níž, abychom pak před všechny takové číslice mohli napsat znamínko mínus a odečtení provést ještě jednou. Tím předejdeme duševně namáhavému udržování si přenosů v paměti. Je tak jedno jestli půjdeme zprava, zleva, nebo odečteme nejdřív číslice na kraji, pak si půjdeme udělat kafe a po kafíčku vyplníme číslice uprostřed. Naše činnost je bezstavová. Příklad, který jsem skutečně spočítal ručně:
CCCE5 C4BCBDE8362527C3 -1DD71 -29CD05F2A4D61BD8 ------ ---------------- =BFF74 =ABFFB8F6925F1CFB -11 -111 1 1 11 111 ------ ----------------- =AEF74 =9AEFB7F5914F0BEB
Tak a teď abych nekázal vodu a nepil víno, tak skutečně ručně vydělím 2 čísla z /dev/random. Použiji bloky mezer a REPLACE mód Vim k pohodlnému vyplňování číslic:
1F4702:E556
-1CAAC0 =20,
====== 1x= E556
=03AD42 ====
- 111 2x= 1CAAC
====== =====
= 29C42 28448
- 1CAAC = 2, +1111
===== =====
= 1D2A6 4x= 39558
- 1 11 =====
===== 62AA0
= D196 +1 1
- 72AB,0 = ,8 =====
==== 8x= 72AB0
= 6FFB,0
- 111
====
= 5EEB,0
- 3955,8 = ,4
======
= 2596,8
- 1
======
= 2595,8
- 1CAA,C = ,2
======
= 19FB,C
- 1111
======
= 8EA,C
- 72A,B0 = ,08
======
= 1C0,10
- E5,56 = ,01
======
= 1EB,CA
- 111 1
======
= DA,BA
- 72,AB0= ,008
====
Výsledek: 22,E98
Kontrola programem bc:
$ bc -l [...] obase=16 ibase=16 1F4702/E556 22.E9F4283870F3C3C1A
Vidíme, že výsledek je správně. Náš výsledek má pouze omezenou přesnost na 4 hexadecimální číslice a 1 bit. Kdybychom počítali déle, vyjde větší přesnost.
Program bc odčítá chybně
A co na hexadecimální odčítání použít program bc? To bohužel fungovat nebude. Program bc tiše a zákeřně odčítá chybně:
pi@karel:~ 2021-01-02 04:05:04 $ bc -l bc 1.07.1 Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006, 2008, 2012-2017 Free Software Foundation, Inc. This is free software with ABSOLUTELY NO WARRANTY. For details type `warranty'. obase=16 ibase=16 1.0-0.1 1.0 1.00-0.10 .F0 1.000-0.100 .F02
- 1.0–0.1 má být .F, nikoliv 1.0
- 1.000–0.100 má být .F, nikoliv .F02
Pochopení principů těchto spíše rekreačních algoritmů nám ale okamžitě ukazuje cesty optimalizace algoritmů dělení velkých binárních čísel uložených jako obyčejné bajty v paměti. Analogicky se dá algoritmus rozšířit na duocentehexaquinquagesimální (dokážete vyslovit timoxeline barbebutenol?) čísla – se základem 256. Pokud dělíme velké množství dělenců stejným dělitelem, můžeme si vytvořit tabulku násobků dělitele 0–255. V tabulce pak vyhledáme vhodný násobek binárním vyhledáváním. Nebudeme muset porovnávat celou délku čísel, ale pouze horní bajty, což nám může běh urychlit.
V roce 1450 pokud člověk chtěl studovat násobení a dělení, musel na univerzitu do Itálie. Na německé univerzitě se dalo studovat pouze sčítání a odčítání.
Při psaní tohoto článku jsem si vzpomněl na knihu Bity do bytu, na které jsem vyrůstal spolu s osobním mikropočítačem Didaktik Gama.
ČLÁNKY DO MAILU