Klasické násobení označuje násobení dvou přirozených čísel zadaných pomocí zápisů v bázi b, kde b je přirozené číslo větší nebo rovno 2. Binární zápis (b = 2) a desítkový zápis (b = 10) jsou speciální případy zápisu čísel v bázi b s ciframi 0, 1, ..., b-1.

Soustava s přirozeným základem

Každé přirozené číslo n lze právě jedním způsobem vyjádřit ve tvaru: kde koeficienty a_k, a_k-1, ..., a₁, a₀ nabývají hodnot 0, 1, ..., b-1. Řetězci a_k a_k-1 ... a₁ a₀ říkáme zápis čísla n v soustavě se základem b. Připomeňme, že takový zápis se získá hladovým algoritmem:

• Chceme-li najít zápis čísla n v bázi b, podíváme se, jakou nejvyšší mocninu b^k číslo n obsahuje a kolikrát ji obsahuje. To bude koeficient a_k, který je jistě menší než b.
• Poté od n odečteme a_kb^k a pro získaný rozdíl opět najdeme největší mocninu b^j, kterou obsahuje, a jako a_j označíme počet výskytů b^j v rozdílu.
• Všechny koeficienty mezi a_j a a_k (pokud nějaké takové jsou, tj. pokud je j menší než k-1) jsou nulové. Analogicky pokračujeme dále.

Popišme nejprve algoritmus klasického násobení tak, jak by jej provedl počítač, a poté jej porovnejme s algoritmem "tužky a papíru".

Algoritmus M (multiplication)

Násobíme přirozená čísla U,V, kde u_n-1 ... u₁u₀ je zápis U v bázi b a v_m-1 ... v₁v₀ je zápis V v bázi b. Označme W = U × V. Snadno si rozmyslíme, že délka zápisu W v bázi b bude maximálně m+n. Označme w_m+n-1 ... w₁w₀ zápis W.

1. Inicializace W a i , j   Polož w_n-1 = ... = w₁ = w₀ = 0 a i = 0 a j = 0.
2. Násobení nulou   Pokud v_j = 0, pak polož w_i+j = 0 a jdi na krok 6.
3. Inicializace i   Polož i = 0, k = 0.
4. Násob a sečti   Polož t = u_i × v_j + w_i+j + k. Pak polož w_i+j = t mod b a k = [t/b], kde [x] je největší celé číslo, které je menší nebo rovno x a t mod b = t-b[t/b] (zbytek po celočíselném dělení).
5. Cyklus na i   Polož i:= i + 1. Pokud i < n, jdi na krok 4. Jinak polož w_i+j = k.
6. Cyklus na j   Polož j := j + 1. Pokud j < m, jdi na krok 2. Jinak konec.

Ilustrujme algoritmus M pro b = 10 a W = U × V, kde U=914=u₂u₁u₀ a V=84=u₁u₀.
Algoritmus M versus násobení na papíře

Při násobení na papíře tvoříme částečné součiny, které příslušně posunuté vlevo sepisujeme pod sebe a na závěr vysčítáme. Na počítači je výhodnější provádět násobení a sčítání současně - tak postupuje algoritmus M. Není těžké si rozmyslet, že t nabývá hodnot 0, 1, ..., b²-1 a přenos (carry) k nabývá hodnot 0, 1, ..., b-1, proto víme, jak velké registry potřebujeme pro implementaci. Počítače navíc pracují s bází 2, krok 2 tedy ušetří práci, nastává průměrně v polovině případů. (Už z předchozí sekce víme, že v binární soustavě je rychlost násobení úměrná počtu nul v binárním zápisu násobitele.) Nevýhodou klasického algoritmu je jeho pomalost. Už pro m = n = 4 je možné násobit U × V rychleji.

Složitost algoritmu M pro bázi b = 2

Definujme nejprve elementární operace:

1. součet a rozdíl 1-bitových čísel a případně přenos,
2. součin dvou 1-bitových čísel s 2-bitovým výsledkem,
3. celočíselné dělení 2-bitového čísla 1-bitovým za předpokladu, že kvocient i zbytek výsledku jsou 1-bitové.

Počet takových operací udává složitost algoritmu. V případě algoritmu M lze dokázat, že složitost násobení čísel s délkami binárních rozvojů m a n je O(m.n), tj. existuje konstanta K>0 taková, že pro libovolná dvě přirozená čísla je složitost jejich násobení algoritmem M menší než K.m.n, kde m a n jsou délky jejich binárních rozvojů.

Úvod - Násobení - Počítačové násobení - Klasické 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