N´asob´ıme chytˇre? ˇ ek Skarda, ˇ L’ubom´ıra Balkov´ a, Praha, Cenˇ Uniˇcov
Aˇckoliv se na z´akladn´ıch ˇskol´ach uˇc´ıme vˇsichni stejn´e algoritmy pro sˇc´ıt´an´ı, odˇc´ıt´an´ı, n´asoben´ı a dˇelen´ı s tuˇzkou a pap´ırem, je takov´ ych algoritm˚ u velk´e mnoˇzstv´ı a kaˇzd´ y z nich m´a sv´e v´ yhody a nev´ yhody. Existuje tak´e cel´a ˇrada mechanick´ ych pom˚ ucek, kter´ ymi si lid´e oded´avna v´ ypoˇcty ulehˇcuj´ı. V dneˇsn´ı dobˇe je takovou hlavn´ı pom˚ uckou poˇc´ıtaˇc. I v tomto pˇr´ıpadˇe plat´ı, ˇze kromˇe algoritm˚ u, kter´e pouˇz´ıv´a PC k prov´adˇen´ı aritmetick´ ych operac´ı, existuje cel´a ˇrada algoritm˚ u, kter´e se mohou hodit napˇr´ıklad ve chv´ıli, kdy je hlavn´ı u ´lohou n´asobit obrovsk´a ˇc´ısla nebo kdy m´ame k dispozici poˇc´ıtaˇce zapojen´e do s´ıt´ı a s v´ yhodou vyuˇzijeme paraleln´ı algoritmy. V tomto ˇcl´anku poskytneme pˇrehled v´ıce i m´enˇe zn´am´ ych algoritm˚ u pro n´asoben´ı, a to od tˇech nejstarˇs´ıch, kter´e urychluj´ı n´asoben´ı zpamˇeti a s tuˇzkou a pap´ırem, pˇres mechanismy v´ ypoˇcetn´ıch pom˚ ucek aˇz po rychl´e algoritmy nejmodernˇejˇs´ıch poˇc´ıtaˇc˚ u. 1. N´ asob´ıme chytˇ re? M´ame-li za u ´kol vyn´asobit dvˇe pˇrirozen´a ˇc´ısla a k dispozici tuˇzku a pap´ır, vˇetˇsina z n´as pouˇzije algoritmus, kter´ y jsme se uˇcili na z´akladn´ı ˇskole:
2 2
4 5 4 5 9
× 1 3 4
7 3 1 1
Existuje ale cel´a ˇrada alternativ. Egyptsk´e a rusk´e n´ asoben´ı je zaloˇzeno na bin´arn´ım rozvoji n´asobence. Cauchyovo komplement´ arn´ı n´ asoben´ı vyuˇz´ıv´a z´apis ˇc´ısel pomoc´ı ˇ ınsk´e n´ z´aporn´ ych cifer. C´ asoben´ı je grafick´e, a tedy pro ˇz´aky s odporem k matematice moˇzn´a nejpˇr´ıvˇetivˇejˇs´ı. Zjednoduˇsen´ı n´asoben´ı velk´ ych ˇc´ısel pˇrinesly tabulky kvadr´ at˚ u a Napierovy kosti, vyn´ alez Johna Napiera, otce logaritmu. Kromˇe algoritm˚ u, kter´e urychluj´ı n´asoben´ı zpamˇeti a na pap´ıˇre, si tak´e uk´aˇzeme efektivn´ı algoritmy pro poˇc´ıtaˇcov´e n´asoben´ı. Pˇri n´asoben´ı velk´ ych ˇc´ısel se vyplat´ı zapsat ˇc´ısla v tzv. redundantn´ı bin´ arn´ı soustavˇe, kde je dovolena kromˇe cifer 0 a 1 i cifra −1. Modern´ı ´eru n´asoben´ı velk´ ych ˇc´ısel odstartoval ale zejm´ena Karacub˚ uv algoritmus, kter´ y takt´eˇz v kr´atkosti pˇredstav´ıme.
ˇ ´ , Ph.D., Katedra matematiky FJFI CVUT Ing. L’ubom´ıra Balkova v Praze, Trojanova 13, ˇ ˇ ˇ 120 00 Praha 2, e-mail:
[email protected], Cen ek Skarda, Gymn´ azium Uniˇcov, Gymnazijn´ı 257, 783 91 Uniˇcov, e-mail:
[email protected]
1
2. N´ asoben´ı zpamˇ eti N´asoben´ı na prstech pan´ı uˇcitelky na z´akladn´ı ˇskole nevid´ı r´ady. Chtˇej´ı n´as totiˇz nauˇcit n´asobit do 10 kr´at 10 zpamˇeti jako kdyˇz biˇcem mrsk´a“. Pˇresto je pouˇzit´ı ” prst˚ u pˇrirozen´ ym zjednoduˇsen´ım, kter´ ym si lid´e pom´ahaj´ı pˇri v´ ypoˇctech oded´avna. Stˇredovˇec´ı obchodn´ıci s oblibou vyuˇz´ıvali tzv. cik´ anskou n´ asobilku, kter´a umoˇzn ˇuje n´asobit pomoc´ı prst˚ u do 9 kr´at 9 (se znalost´ı pouh´e n´asobilky do 5 kr´at 5). Princip cik´ ansk´e n´asobilky pochop´ıte z obr´azku 1. Pokud chceme n´asobit 8 kr´at 7, zept´ame se:
Obr. 1. 1. Cik´ ansk´ a n´ asobilka pro v´ ypoˇcet 8 × 7
2. V´ ypoˇcet 14 × 9 pomoc´ı prst˚ u
Osm a kolik je deset?“ A dva.“ Skrˇc´ıme dva prsty na prvn´ı ruce (c = 2). To sam´e ” ” udˇel´ame s ˇc´ıslem sedm. Schov´ame tedy tˇri prsty na druh´e ruce (d = 3). Na pozici des´ıtek nap´ıˇseme souˇcet vztyˇcen´ ych prst˚ u (a + b = 3 + 2 = 5) a na pozici jednotek nap´ıˇseme souˇcin skrˇcen´ ych prst˚ u (c × d = 2 × 3 = 6). A obdrˇz´ıme spr´avn´ y v´ ysledek 56. Bystr´ y ˇcten´aˇr si snadno rozmysl´ı, ˇze algoritmus je pouˇziteln´ y jen k n´asoben´ı ˇc´ısel, kter´a jsou obˇe vˇetˇs´ı nebo rovna 5, a ˇze funguje d´ıky n´asleduj´ıc´ım rovnostem (10 − c)(10 − d)
= = =
100 − (c + d)10 + cd, 10(10 − c − d) + cd, 10(a + b) + cd.
(1)
Moˇzn´a uˇz ˇcten´aˇr postˇrehl, ˇze pˇri n´asoben´ı nˇekter´ ych ˇc´ısel naraz´ıme na u ´skal´ı. Napˇr´ıklad pˇri n´asoben´ı 7 × 6 je c × d = 3 × 4 = 12, coˇz je v´ıce neˇz 10. V takov´em pˇr´ıpadˇe na m´ıstˇe jednotek nech´ame ˇc´ıslo 2 a 1 pˇreneseme k des´ıtk´am. .. . 3. Poˇ c´ıtaˇ cov´ e n´ asoben´ı N´asoben´ı v bin´arn´ı soustavˇe a redundantn´ı bin´arn´ı soustavˇe nen´ı pro ˇclovˇeka bˇeˇzn´e. Lid´e totiˇz d´ıky deseti prst˚ um prov´adˇej´ı v´ ypoˇcty v soustavˇe des´ıtkov´e, tj. ˇc´ısla zapisuj´ı pomoc´ı mocnin des´ıtky a cifer od 0 do 9. Se soustavou bin´arn´ı ovˇsem pracuje valn´a 2
vˇetˇsina poˇc´ıtaˇc˚ u. Kaˇzd´e pˇrirozen´e ˇc´ıslo n lze pr´avˇe jedn´ım zp˚ usobem vyj´adˇrit ve tvaru: n = ak 2k + ak−1 2k−1 + · · · + a1 21 + a0 20 , kde koeficienty ak , ak−1 , . . . , a1 , a0 nab´ yvaj´ı ˇ ezci ak ak−1 . . . a1 a0 ˇr´ık´ame bin´arn´ı z´apis ˇc´ısla n. hodnot nula nebo jedna a ak = 1. Retˇ Pˇripomeˇ nme, ˇze bin´arn´ı z´apis se z´ısk´a hladov´ ym algoritmem, viz kap. 3.1. o egyptsk´em n´asoben´ı. Napˇr´ıklad 13 = 23 + 22 + 20 , proto 13 m´a v bin´arn´ı soustavˇe z´apis 1101. N´asoben´ı v bin´arn´ı soustavˇe je velmi podobn´e n´am zn´am´emu klasick´emu n´asoben´ı v des´ıtkov´e soustavˇe. Napˇr´ıklad ˇc´ıslo 11 s bin´arn´ım z´apisem 1011 a ˇc´ıslo 5 s bin´arn´ım z´apisem 101 se vyn´asob´ı n´asleduj´ıc´ım zp˚ usobem. 1 0 1 1 × 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 V´ ysledek je 32 + 16 + 4 + 2 + 1 = 55. Vˇsimnˇete si, ˇze rychlost n´asoben´ı odpov´ıd´a poˇctu jedniˇcek v bin´arn´ım z´apisu n´asobitele (v naˇsem pˇr´ıpadˇe jsou dvˇe jedniˇcky v bin´arn´ım z´apisu 5), pr´avˇe tolik sˇc´ıt´an´ı (n + k − 1)-bitov´ ych ˇc´ısel, kde n je poˇcet bit˚ u n´asobence a k poˇcet bit˚ u n´asobitele, totiˇz mus´ıme prov´est. 3.1. Redundantn´ı bin´ arn´ı soustava Pˇripust’me nyn´ı v bin´arn´ı soustavˇe cifry −1, 0 a 1. Z´apisy ˇc´ısel uˇz nejsou jedin´e moˇzn´e, soustava je redundantn´ı. Napˇr´ıklad 15 = 8 + 4 + 2 + 1 a tak´e 15 = 16 − 1, tedy jak 1111, tak i 10001 jsou z´apisy 15 v redundantn´ı bin´arn´ı soustavˇe. Vyberme z´apis s maxim´aln´ım poˇctem nul. K tomu staˇc´ı aplikovat n´asleduj´ıc´ı pˇrepisovac´ı pravidla, dokud je co pˇrepisovat: 01111 → 10001, 01111 → 10001, 11 → 01, 11 → 01. Zat´ımco pr˚ umˇern´ y poˇcet nul ve standardn´ım bin´arn´ım z´apisu je 1/2, v redundantn´ım bin´arn´ım z´apisu s maxim´aln´ım moˇzn´ ym poˇctem nul jsou to 2/3. Jelikoˇz je rychlost n´asoben´ı u ´mˇern´a poˇctu nul, je jasn´e, ˇze redundantn´ı bin´arn´ı soustava je pro n´asoben´ı velk´ ych ˇc´ısel v´ yhodnˇejˇs´ı. Poznamenejme jeˇstˇe, ˇze n´asob´ıme analogicky jako v klasick´e bin´arn´ı soustavˇe. Pouze u znam´enek d´av´ame pozor: pˇri n´asoben´ı cifer stejn´eho znam´enka m´a v´ ysledek znam´enko plus, pˇri n´asoben´ı cifer opaˇcn´eho znam´enka m´a v´ ysledek znam´enko m´ınus. Tedy napˇr´ıklad n´asoben´ı 11 a 5 probˇehne n´asledovnˇe: 1
0 ×
1 0 1 0
1 1
0 1 0 0 0 1
0 1 0
1
1 0 0 0 1
1
0 0
1 0
0 1
V´ ysledek je tedy 64 − 8 − 1 = 55. 3
3.2. Rychl´ e n´ asoben´ı Rychl´e n´asoben´ı je n´asoben´ı se sloˇzitost´ı menˇs´ı, neˇz m´a n´asoben´ı klasick´e, jehoˇz sloˇzitost je O(n2 ), kde n je d´elka bin´arn´ıho z´apisu vˇetˇs´ıho ˇc´ısla z n´asobence a n´asobitele. Znamen´a to existenci takov´e konstanty C > 0, ˇze pro vyn´asoben´ı dvou ˇc´ısel s d´elkou bin´arn´ıho z´apisu maxim´alnˇe n je potˇreba prov´est maxim´alnˇe C · n2 bin´arn´ıch operac´ı. Snaha o zrychlen´ı algoritm˚ u se zesiluje ruku v ruce s rozvojem poˇc´ıtaˇc˚ u a speci´alnˇe snaha o maxim´aln´ı zrychlen´ı n´asoben´ı je d´ana potˇrebami kryptografie, kde je nutn´e n´asobit v pˇrijateln´em ˇcase ohromn´a ˇc´ısla (ˇr´adovˇe 10100 ). My zde pop´ıˇseme jedin´e z rychl´ ych n´asoben´ı – Karacubovo n´ asoben´ı zaloˇzen´e na d˚ uvtipn´e myˇslence a pomˇernˇe jednoduˇse vysvˇetliteln´e. Mezi rychl´ ymi algoritmy patˇr´ı k tˇem nejstarˇs´ım, ovˇsem algoritmy jeˇstˇe rychlejˇs´ı uˇz jsou pˇr´ıliˇs technick´e. Z´ajemce o n´asoben´ı pˇrirozen´ ych ˇc´ısel s bin´arn´ım rozvojem d´elky n bl´ıˇz´ıc´ı se svou sloˇzitost´ı libovolnˇe bl´ızko aˇz k nejniˇzˇs´ı hranici O(n) si dohled´a podrobnosti v knize [4]. Poznamenejme, ˇze jde o jednu z nejrespektovanˇejˇs´ıch publikac´ı v oboru programov´an´ı. Jej´ı autor Donald E. Knuth je pr˚ ukopn´ıkem oboru matematick´e anal´ yzy algoritm˚ u a v´ yznamnou osobnost´ı v mnoha dalˇs´ıch oborech teoretick´e poˇc´ıtaˇcov´e vˇedy. Karacubovo n´asoben´ı vyvr´atilo domnˇenku, ˇze sloˇzitost n´asoben´ı dvou pˇrirozen´ ych ˇc´ısel s bin´arn´ım rozvojem d´elky n je O(n2 ). Tento n´azor razil jeˇstˇe v roce 1960 na semin´aˇri moskevsk´e univerzity zakladatel teorie sloˇzitosti algoritm˚ u Andrej N. Kolmogorov. Semin´aˇre se u ´ˇcastnil i jeho student Anatolij A. Karacuba, kter´ y navrhl d˚ uvtipn´ y algoritmus s niˇzˇs´ı sloˇzitost´ı [2, 3]. Pop´ıˇseme algoritmus, kter´ y je zaloˇzen na stejn´e myˇslence jako p˚ uvodn´ı Karacub˚ uv, ale je jeˇstˇe trochu jednoduˇsˇs´ı. Chceme n´asobit dvˇe 2n-bitov´a ˇc´ısla U s bin´arn´ım z´apisem u2n−1 . . . u1 u0 a V s bin´arn´ım z´apisem v2n−1 . . . v1 v0 . Zap´ıˇseme U, V n´asleduj´ıc´ım zp˚ usobem U = 2n U1 + U0 a V = 2n V1 + V0 . Plat´ı tedy, ˇze U1 m´a bin´arn´ı z´apis u2n−1 . . . un a U0 m´a z´apis un−1 . . . u1 u0 , podobnˇe V1 m´a bin´arn´ı z´apis v2n−1 . . . vn a V0 m´a z´apis vn−1 . . . v1 v0 . N´asleduj´ıc´ı formule redukuje probl´em na 3 n´asoben´ı n-bitov´ ych ˇc´ısel, nˇekolik sˇc´ıt´an´ı, resp. odeˇc´ıt´an´ı a posouv´an´ı bin´arn´ı ˇc´arky: U × V = (22n + 2n )U1 V1 + 2n (U1 − U0 )(V0 − V1 ) + (2n + 1)U0 V0 . Ilustrujme Karacub˚ uv algoritmus pro U × V , kde U = 210 a V = 119. Bin´arn´ı z´apis U je 11010010 a bin´arn´ı z´apis V je 01110111. 210 = U = 24 U1 + U0 = 24 · 13 + 2, 119 = V = 24 V1 + V0 = 24 · 7 + 7, kde U1 = 13 m´a bin´arn´ı z´apis 1101 a U0 = 2 m´a bin´arn´ı z´apis 0010, V1 = V0 = 7 maj´ı z´apis 0111. Nyn´ı urˇc´ıme 3 souˇciny nejv´ yˇse 4-bitov´ ych ˇc´ısel: U1 V1 , (U1 − U0 )(V0 − V1 ), U0 V0 . V tomto konkr´etn´ım pˇr´ıpadˇe je V0 = V1 , a tedy prostˇredn´ı souˇcin je nulov´ y.
U1 V1 : 1
1 0
1 1 1
1 × 1 1 0 1
1 1 1 0 1 0
0 1 0 1
1 1 1
1
1
U0 V0 : 1
4
1 × 1
1 1 1
1 0 0
Na z´avˇer zb´ yv´a prov´est n´asoben´ı 28 a 24 , coˇz je vlastnˇe pˇrips´an´ı 8, respektive 4 nul na konec bin´arn´ıho z´apisu p˚ uvodn´ıho ˇc´ısla, a sˇc´ıt´an´ı. U × V = 28 U1 V1 + 24 U1 V1 + 24 U0 V0 + U0 V0 . 1
0
1
1
0 1
1 0
1 1
0 1 1
0 0 1
0 1 1
0 1 0
1
1
0
0
0
0
1
1
0
0
1
U ×V :
0 0 0 1 1
0 0 0 1 1
0 0 0 1 1
0 0 0 0 0
Po konverzi do des´ıtkov´e soustavy m´ame spr´avn´ y v´ ysledek 210 × 119 = 214 + 213 + 28 + 27 + 24 + 23 + 22 + 21 = 24 990. ˇ ıslo log2 3 je Nen´ı tˇeˇzk´e dok´azat, ˇze sloˇzitost Karacubova n´asoben´ı je O(nlog2 3 ). C´ pˇribliˇznˇe rovno 1, 585, coˇz je ˇc´ıslo menˇs´ı neˇz 2, a tedy jde skuteˇcnˇe o rychl´e n´asoben´ı podle naˇs´ı definice. Adaptac´ı na des´ıtkovou soustavu lze pˇrev´est n´asoben´ı 8-m´ıstn´ ych ˇc´ısel na n´asoben´ı ˇc´ısel 4-m´ıstn´ ych, kter´e uˇz dobˇr´ı poˇct´aˇri zvl´adnou zpamˇeti. Nezd´a se vˇsak, ˇze by takovou metodu pouˇz´ıvali z´azraˇcn´ı poˇct´aˇri“, kteˇr´ı v minulosti bavili ” obecenstvo n´asoben´ım obrovsk´ ych ˇc´ısel zpamˇeti. Poznamenejme pro u ´plnost, ˇze nejrychlejˇs´ım v praxi pouˇz´ıvan´ ym algoritmem je Sch¨onhage˚ uv–Strassen˚ uv algoritmus se sloˇzitost´ı O(n log n log log n) z roku 1971, ale existuj´ı i algoritmy, kter´e jsou asymptoticky jeˇstˇe rychlejˇs´ı (napˇr. F¨ urer˚ uv algoritmus z roku 2007 nebo algoritmus autor˚ u De, Saha, Kurur a Saptharishi z roku 2008). 4. Z´ avˇ er C´ılem tohoto ˇcl´anku bylo uk´azat, ˇze algoritm˚ u n´asoben´ı existuje cel´a ˇrada a ˇze ty z nich, kter´e se vˇsichni uˇc´ıme na z´akladn´ıch ˇskol´ach, nejsou obˇcas nejv´ yhodnˇejˇs´ı. Autoˇri z´aroveˇ n vytvoˇrili www str´anku http://bimbo.fjfi.cvut.cz/∼ soc, kter´a nejr˚ uznˇejˇs´ı algoritmy srozumitelnˇe popisuje a ilustruje na pˇr´ıkladech ˇci pomoc´ı program˚ u. Podˇ ekov´ an´ı. Autoˇri dˇekuj´ı za cenn´e pˇripom´ınky RNDr. Pavle Pavl´ıkov´e, Ph.D., a doc. RNDr. Martinu Klazarovi, Dr. Literatura ˇ, A. P.: Dˇejiny matematiky ve stˇredovˇeku, 1.vyd´ [1] Juˇskevic an´ı. Academia, Praha, 1978. [2] Karacuba, A. A., Ofman, Yu.: Multiplication of many-digital numbers by automatic computers (v ruˇstinˇe). Proc. USSR Acad. Sci. 145 (1962), 293–294. [3] Karacuba, A. A.: The complexity of computation (v angliˇctinˇe). Proc. Steklov Inst. Math. 211 (1995), 169–183. [4] Knuth, D. E.: The art of computer programming volume 2: Seminumerical algorithms, 3rd ed. Addison-Wesley, Boston, 1998. ˇ ˇ´ıˇ ´ , A.: Proch´ [5] Kr zek, M., Solcov a azky Prahou matematickou, fyzik´ aln´ı a astronomickou (3. ˇc´ ast). PMFA 55 (3) (2010), 215–230.
5
ˇ Ako r´ ´ , S.: [6] Porubsky ychlo vieme a moˇzeme n´ asobit’. Sborn´ık 30. mezin´ arodn´ı konference Historie matematiky, J. Beˇcv´ aˇr, M. Beˇcv´ aˇrov´ a, (eds), Matfyzpress, Praha, 2009. ´ korova ´ , I.: N´ [7] Sy asoben´ı ve stˇredovˇek´e Indii. Sborn´ık 29. mezin´ arodn´ı konference Historie matematiky, J. Beˇcv´ aˇr, M. Beˇcv´ aˇrov´ a, (eds), Matfyzpress, Praha, 2008. ´ , H.: Staroegyptsk´ [8] Vymazalova a matematika. Dˇejiny matematiky, svazek 31, Praha, 2006. [9] Biografie ˇcesk´ ych matematik˚ u, inserv.math.muni.cz/biografie
6
