Rychlé násobení je násobení se složitostí menší než násobení klasické. Snaha o zrychlení algoritmů se zesiluje ruku v ruce s rozvojem počítačů a speciálně snaha o maximální zrychlení násobení je dána potřebami kryptografie, kde je nutné násobit v přijatelném čase ohromná čísla (řádově 10¹⁰⁰). My popíšeme dvě rychlá násobení - Karacubovo násobení a Schönhageovo násobení v modulární aritmetice - založená na důvtipných myšlenkách a poměrně jednoduše popsatelná. Mezi rychlými algoritmy patří k těm nejstarším, ovšem algoritmy ještě rychlejší už jsou příliš technické. Zájemce o násobení přirozených čísel s binárním rozvojem délky n blížící se svou složitostí libovolně blízko až k nejnižší hranici O(n) si dohledá podrobnosti v D. E. Knuth, The Art of Computer Programming volume 2: Seminumerical Algorithms, 3rd ed, Addison-Wesley Boston etc., 1998. Poznamenejme, že jde o jednu z nejrespektovanějších publikací v oboru programování. Donald E. Knuth (na obrázku) je průkopníkem oboru matematické algoritmické analýzy a významnou osobností v mnoha dalších oborech teoretické počítačové vědy.

Karacubovo násobení

Karacubovo násobení vyvrátilo domněnku, že složitost násobení dvou přirozených čísel s binárním rozvojem délky n je O(n²). Tento názor razil ještě v roce 1960 na semináři moskevské univerzity zakladatel teorie složitosti algoritmů Andrej N. Kolmogorov (na obrázku). Semináře se účastnil jeho student Anatolij A. Karacuba, který navrhl a o dva roky později publikoval důvtipný algoritmus s nižší složitostí. Popíšeme algoritmus, který je založen na stejné myšlence jako původní Karacubův, ale je ještě trochu jednodušší. Chceme násobit dvě 2n-bitová čísla U s binárním zápisem u_2n-1...u₁u₀ a V s binárním zápisem v_2n-1...v₁v₀.

• Zapíšeme U, V následujícím způsobem U = 2ⁿU₁ + U₀ a V = 2ⁿV₁ + V₀. Platí tedy, že U₁ má binární zápis u_2n-1...u_n a U₀ má zápis u_n-1...u₁u₀, podobně V₁ má binární zápis v_2n-1...v_n a V₀ má zápis v_n-1...v₁v₀.
• Následující formule redukuje problém na 3 násobení n-bitových čísel, několik sčítání, resp. odečítání a posouvání binární čárky:
  U×V = (2²ⁿ+2ⁿ)U₁V₁+2ⁿ(U₁-U₀)(V₀-V₁)+(2ⁿ+1)U₀V₀.

Ilustrujme Karacubův algoritmus pro U × V, kde U=210 a V=119. Binární zápis U je 11010010 a binární zápis V je 01110111. Není těžké dokázat, že složitost Karacubova násobení je O(n^log₂3). Platí log₂3 je přibližně 1,585, což je číslo menší než 2, a tedy jde skutečně o rychlé násobení podle naší definice.
Adaptací na desítkovou soustavu lze převést násobení 8-místných čísel na násobení čísel 4-místných, které už dobří počtáři zvládnou zpaměti. Kupodivu se nezdá, že by taková metoda byla známa před rokem 1962 a že by ji tedy používali "zázrační počtáři", kteří v minulosti bavili obecenstvo násobením obrovských čísel zpaměti.

Schönhageovo násobení v modulární aritmetice

Schönhageovo násobení v modulární aritmetice sice není rychlejší než Karacubův algoritmus, ale je založeno na odlišných myšlenkách a na neobvyklé reprezentaci čísel, takže je rozhodně zajímavé do jeho tajů proniknout. Jeho základním stavebním kamenem je modulární aritmetika, u jejíhož zrodu stáli čeští vědci Antonín Svoboda (tvůrce prvního československého počítače SAPO a velmi významný průkopník informatiky nejen u nás - o jeho klikatých osudech se dočtete v článku Petra Vysokého 100 let od narození Antonína Svobody a jeho podobu vidíte na obrázku) a Miroslav Valach. Nezávisle na nich přišel se stejnou myšlenkou také L. H. Garner.

Modulární zápis

Dosud jsme se seznámili jen se zápisy přirozených čísel v pozičních soustavách s přirozenou bází (případně jsme připustili záporné cifry). Nyní přijde naprosto odlišný zápis přirozených čísel.
Nechť jsou dána přirozená čísla m₁, m₂, ..., m_r. Pak modulárním zápisem nezáporného celého čísla U nazveme (u₁,u₂,...,u_r,), kde u_i je rovno U mod m_i pro každé i od 1 do r. Připomeňme, že mod k znamená zbytek po celočíselném dělení číslem k a nabývá hodnot od 0 do k-1. (Například 13=3.4+1, a tedy 13 mod 4=1.) Ukažme si na příkladu takovou modulární reprezentaci. Aby takový zápis měl smysl, mělo by být možné původní číslo ze znalosti modulární reprezentace zrekonstruovat. To bez dodatečných podmínek možné není. Všimněme si, že čísla 56 a 26 mají stejný modulární zápis (0,2,1). Naštěstí platí následující tvrzení, které je důsledkem známé Čínské zbytkové věty:
Nechť a,u₁,u₂,...,u_r jsou nezáporná celá čísla a nechť m₁, m₂, ..., m_r jsou přirozená po dvou nesoudělná čísla. Pak existuje právě jedno U, které splňuje

1. a - 1 < U < a + m = a + m₁. m₂. ... . m_r,
2. (u_1,u_2,,...,u_r) je modulární reprezentace U.

Z této věty plyne, že když se omezíme na čísla od 0 do 2.3.5 = 30, pak mezi nimi právě jen číslo 26 má modulární reprezentaci (0,2,1).

Modulární aritmetika

V modulární aritmetice je možné paralelizovat sčítání a násobení. Platí totiž, že pokud U a V jsou přirozená čísla s modulárními reprezentacemi (u₁,u₂,...,u_r) a (v₁,v₂,...,v_r) a obě leží mezi 0 a m = m₁. m₂. ... . m_r, pak

1. U + V má modulární reprezentaci ((u₁+v₁) mod m₁, (u₂+v₂) mod m₂,...,(u_r+v_r) mod m_r),
2. U x V má modulární reprezentaci ((u₁.v₁) mod m₁, (u₂.v₂) mod m₂,...,(u_r.v_r) mod m_r).

Nevýhodou je, že při pohledu na modulární reprezentace nepoznáme, které z čísel je větší. Navíc nepoznáme, zda výsledek operace nevypadl z intervalu 0 až m. Proto potřebujeme rychlou konverzi, která číslům přiřazuje modulární zápis a zejména z modulárního zápisu rychle vyrábí zpět reprezentovaná čísla.

Binární modulární aritmetika

Jak uvidíme, takovou rychlou konverzi poskytuje vhodná volba modulí m₁, m₂, ..., m_r. Následující nápad se zrodil v hlavě A. S. Fraenkela.
Volme modula m_i= 2^e_i -1, kde e₁ < e₂ < ... < e_r jsou po dvou nesoudělná. Nesoudělnost takových modulí je zaručena následující větou:
Nechť e, f jsou přirozená čísla. Pak 2^e -1 a 2^f -1 jsou nesoudělná, právě když e a f jsou nesoudělná

Konverze U na (u₁,u₂,...,u_r)

Zapišme U ve tvaru U = a_tA^t + a_t-1A^t-1 + ... +a₁A + a₀, kde A = 2^e_i. Uvědomme si, že binární zápis a₀ získáme tak, že vezmeme posledních e_i bitů v binárním zápisu U, pro získání a₁ vezmeme předposledních e_i bitů atd. Vlastně jen nasekáme binární zápis U od konce po e_i bitech. Protože A = 1 mod (2^e_i-1), dostaneme u_i = (a_t + a_t-1 + ... + a₀) mod (2^e_i-1).
V desítkové soustavě máme analogii (tzv. casting out nines - vyloučení devítek)
789 mod 9 = 7 + 8 + 9 mod 9 = 6, což skutečně platí, protože 789 = 87.9 + 6. Ilustrujme tento algoritmus opět na příkladu.
Konverze (u₁,u₂,...,u_r) na U

Je o něco složitější. Probíhá ve dvou krocích:

• Nejprve je třeba najít r(r-1)/2 konstant c_ij, indexy i,j nabývají hodnot od 1 do r, i < j a platí c_ijm_i=1 mod m_j.
  K tomu využijeme následující algoritmus.

• Poté položíme U = v_r m_r-1...m₂m₁ +...+ v₃ m₂m₁ + v₂ m₁ + v₁, kde
  v₁ = u₁ mod m₁
  v₂ = (u₂-v₁)c₁₂ mod m₂
  v₃ = ((u₃-v₁)c₁₃-v₂)c₂₃ mod m₃
  ...
  v_r = (((u_r-v₁)c_1r-v₂)c_2r-...)c_r-1r mod m_r
  Snadno se přesvědčíme, že takto spočtené U splňuje
  1. U je nezáporné číslo menší než m,
  2. U mod m_i = u_i pro každé i od 1 do r.
  Ilustrujme i tento algoritmus na příkladu.

Schönhageovo násobení

Nyní máme vše připraveno k tomu, abychom pochopili fungování algoritmu, který Arnold Schönhage v roce 1966 navrhl. Nejprve si všimněme, jak šikovně volí 6 modulí, která budou v jeho algoritmu vystupovat. Pro posloupnost q₀=1 a q_k=3q_k-1-1, tj. q_k=(3^k+1)/2 pro každé k přirozené, jsou modula po dvou nesoudělná. Navíc platí, že při násobení p_k=(18q_k+8)-bitových čísel nedojde k přetečení, tj. zůstaneme mezi 0 a m=m₁. m₂. ... . m₆, protože m je větší než 2^2p_k.
Teď již samotný Schönhageův algoritmus. Chceme násobit přirozená čísla U a V, označme W = U x V. Najdeme nejmenší p_k tak, že násobená čísla jsou nejvýše p_k-bitová. K p_k najdeme příslušná modula. Tento algoritmus převádí úlohu násobit p_k-bitová čísla na násobení p_k-1-bitových čísel. To je podobná myšlenka jako v Karacubově násobení vedoucí ke snížení složitosti. Tentokrát je možné - i když pracné - dokázat, že složitost Schönhageova násobení je O(n^log₃6). Platí log₃6 je přibližně 1,63, což je číslo menší než 2, a tedy jde opět o rychlé násobení podle naší definice.

Úvod - Násobení - Počítačové násobení - Rychlé násobení

Úvod

Násobení

Násobení na prstech

Násobení na papíře

Mechanické pomůcky a tabulky

Počítačové násobení

Dělení

Dělení na papíře

Mechanické pomůcky

Odmocnina

Sčítání

Starověké kultury

Významní matematikové

Aplikace na android ke stažení na Google Play