Algoritmus násobení - Multiplication algorithm

Algoritmus násobení je algoritmus (nebo metoda) se množí dvou čísel. V závislosti na velikosti čísel se používají různé algoritmy. Efektivní multiplikační algoritmy existují od příchodu desítkové soustavy.

Metoda mřížky

Metoda mřížka (nebo metoda box) je úvodní metoda pro více číslice násobení, který je často učil žáky na základní škole nebo základní škole . Je to standardní součást národních osnov matematiky pro základní školy v Anglii a Walesu od konce devadesátých let.

Oba faktory jsou rozděleny („rozděleny“) na stovky, desítky a jednotkové části a produkty těchto částí jsou poté explicitně vypočítány v relativně jednoduché fázi pouze pro násobení, než jsou tyto příspěvky poté sečteny, aby poskytly konečnou odpověď. samostatná fáze přidávání.

Výpočet 34 × 13 lze například vypočítat pomocí mřížky:

  300
   40
   90
 + 12
 ————
  442

následuje sčítání k získání 442, buď v jediném součtu (viz vpravo), nebo vytvořením součtů po řádcích (300 + 40) + (90 + 12) = 340 + 102 = 442.

Tento přístup k výpočtu (i když ne nutně s explicitním uspořádáním mřížky) je také známý jako algoritmus dílčích produktů . Jeho podstatou je výpočet jednoduchých násobení odděleně, přičemž veškeré sčítání je ponecháno na konečné fázi shromažďování.

Metodu mřížky lze v zásadě použít na faktory jakékoli velikosti, i když se počet dílčích produktů stává těžkopádným, jak se počet číslic zvyšuje. Přesto je považována za užitečně explicitní metodu k zavedení myšlenky víceciferného násobení; a v době, kdy se většina multiplikačních výpočtů provádí pomocí kalkulačky nebo tabulky, to může být v praxi jediný multiplikační algoritmus, který někteří studenti někdy budou potřebovat.

Dlouhé násobení

Pokud je použit poziční číselný systém , přirozený způsob násobení čísel se ve školách vyučuje jako dlouhé násobení , někdy nazývané násobení na základní škole , někdy nazývané standardní algoritmus : vynásobte násobenec a každou číslici násobiče a poté sečtěte všechny řádné posunuté výsledky. Vyžaduje uložení multiplikační tabulky do paměti pro jednociferné číslo.

Toto je obvyklý algoritmus pro násobení větších čísel ručně v základně 10. Počítače zpočátku používaly velmi podobný posun a přidaly algoritmus v základně 2, ale moderní procesory optimalizovaly obvody pro rychlé násobení pomocí efektivnějších algoritmů za cenu složitějších realizace hardwaru. Osoba, která dělá dlouhé násobení na papír, si všechny produkty zapíše a pak je sečte; uživatel počítadla počítá produkty, jakmile je každý vypočítán.

Příklad

Tento příklad používá dlouhé násobení k vynásobení 23 958 233 (multiplikand) 5 830 (multiplikátor) a pro výsledek (produkt) přijde na 139 676 498 390.

      23958233
×         5830
———————————————
      00000000 ( =      23,958,233 ×     0)
     71874699  ( =      23,958,233 ×    30)
   191665864   ( =      23,958,233 ×   800)
+ 119791165    ( =      23,958,233 × 5,000)
———————————————
  139676498390 ( = 139,676,498,390        )

Níže uvedený pseudokód popisuje proces výše uvedeného násobení. Udržuje pouze jeden řádek pro udržení součtu, který se nakonec stane výsledkem. Všimněte si toho, že operátor '+=' se používá k označení součtu existující hodnoty a uložení operace (podobné jazykům, jako je Java a C) kvůli kompaktnosti.

multiply(a[1..p], b[1..q], base)                            // Operands containing rightmost digits at index 1
  product = [1..p+q]                                        // Allocate space for result
  for b_i = 1 to q                                          // for all digits in b
    carry = 0
    for a_i = 1 to p                                        // for all digits in a
      product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
      carry = product[a_i + b_i - 1] / base
      product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
    product[b_i + p] = carry                               // last digit comes from final carry
  return product

Optimalizace složitosti prostoru

Nechť n je celkový počet číslic ve dvou vstupních čísly v základně D . Pokud musí být výsledek uložen v paměti, pak je složitost prostoru triviálně Θ ( n ). V některých aplikacích však nemusí být celý výsledek uchováván v paměti a místo toho lze číslice výsledku streamovat při jejich výpočtu (například do systémové konzoly nebo souboru). V těchto scénářích má dlouhé násobení tu výhodu, že ho lze snadno formulovat jako algoritmus logovacího prostoru ; tj. algoritmus, který potřebuje pouze pracovní prostor úměrný logaritmu počtu číslic na vstupu ( Θ (log  n )). Toto je dvojnásobný logaritmus vynásobených čísel (log log  N ). Všimněte si, že samotné operandy je stále nutné uchovávat v paměti a jejich Θ ( n ) prostor není v této analýze zohledněn.

Metoda je založena na pozorování, že každou číslici výsledku lze vypočítat zprava doleva, pouze s vědomím přenosu z předchozího kroku. Nechť a _i a b _i je i -tou číslicí operandu, přičemž a a b je vlevo vyplněno nulami, aby měla délku n , r _i je i -tou číslicí výsledku a c _i je přenosem generovaným pro r _i (i = 1 je ta správná číslice) potom

${\ Displaystyle {\ begin {aligned} r_ {i} & = \ left (c_ {i-1}+\ sum _ {j+k = i+1} a_ {j} b_ {k} \ right) \ mod D \\ c_ {i} & = \ left \ lfloor (c_ {i-1}+\ sum _ {j+k = i} a_ {j} b_ {k})/D \ right \ rfloor \\ c_ { 0} & = 0 \ end {aligned}}}$

nebo

${\ Displaystyle c_ {i} = \ left (\ sum _ {m = 0}^{i-2} \ sum _ {j+k = im} a_ {j} b_ {k} \ right)/D.}$

Jednoduchý induktivní argument ukazuje, že carry nemůže nikdy překročit n a celkový součet pro r _i nemůže nikdy překročit D * n : carry do prvního sloupce je nula a pro všechny ostatní sloupce je ve sloupci nejvýše n číslic , a nést nejvýše n z předchozího sloupce (podle indukční hypotézy). Součet je maximálně D * n a přenos do dalšího sloupce je maximálně D * n / D nebo n . Obě tyto hodnoty tedy lze uložit do O (log n ) číslic.

V pseudokódu je algoritmus log-space:

multiply(a[1..p], b[1..q], base)                  // Operands containing rightmost digits at index 1
    tot = 0
    for ri = 1 to p + q - 1                       // For each digit of result
        for bi = MAX(1, ri - p + 1) to MIN(ri, q) // Digits from b that need to be considered
            ai = ri − bi + 1                      // Digits from a follow "symmetry"
            tot = tot + (a[ai] * b[bi])
        product[ri] = tot mod base
        tot = floor(tot / base)
    product[p+q] = tot mod base                   // Last digit of the result comes from last carry
    return product

Využití v počítačích

Některé čipy implementují dlouhé násobení, v hardwaru nebo v mikrokódu , pro různá celočíselná a plovoucí desetinná čárky slov. V aritmetice s libovolnou přesností je běžné používat pro násobení relativně malých čísel dlouhé násobení se základnou nastavenou na 2 ^w , kde w je počet bitů ve slově.

Chcete -li pomocí této metody vynásobit dvě čísla n číslicemi, potřebujete přibližně n ² operací. Formálněji: pomocí metriky přirozené velikosti počtu číslic je časová složitost vynásobení dvou n -ciferných čísel pomocí dlouhého násobení Θ ( n ² ).

Při implementaci v softwaru musí dlouhé multiplikační algoritmy řešit přetečení během přidávání, což může být drahé. Typickým řešením je reprezentovat číslo na malé základně b tak , že například 8 b je reprezentovatelné celé číslo stroje. Než dojde k přetečení, lze provést několik přidávání. Když je číslo příliš velké, přidáme jeho část do výsledku, nebo přeneseme a namapujeme zbývající část zpět na číslo, které je menší než b . Tento proces se nazývá normalizace . Richard Brent použil tento přístup ve svém balíčku Fortran, MP.

Násobení mříže

Nejprve nastavte mřížku označením řádků a sloupců čísly, která chcete znásobit. Poté vyplňte políčka desítkami číslic v horních trojúhelnících a číslicemi jednotek ve spodní části.

Nakonec sečtěte podél diagonálních traktů a noste podle potřeby, abyste dostali odpověď

Násobení mřížkou nebo sítem je algoritmicky ekvivalentní dlouhému násobení. Vyžaduje přípravu mřížky (mřížky nakreslené na papíře), která vede výpočet a odděluje všechna násobení od přírůstků . To bylo představeno do Evropy v 1202 v Fibonacci je Liber Abaci . Fibonacci popsal operaci jako mentální, přičemž pravou a levou rukou prováděl průběžné výpočty. Matrakçı Nasuh představil 6 různých variant této metody v této knize ze 16. století Umdet-ul Hisab. To bylo široce používáno v enderunských školách po celé Osmanské říši. Napierovy kosti nebo Napierovy pruty také používaly tuto metodu, jak ji zveřejnil Napier v roce 1617, rok jeho smrti.

Jak je ukázáno v příkladu, multiplikátor a multiplikátor jsou zapsány nad a napravo od mřížky nebo síta. Nachází se v „aritmetice“ Muhammada ibna Musa al-Khwarizmiho , jednoho ze zdrojů Leonarda, které zmínil Sigler, autor „Fibonacciho Liber Abaci“, 2002.

• Během fáze násobení je mřížka vyplněna dvoucifernými součiny odpovídajících číslic označujících každý řádek a sloupec: desítka číslic jde do levého horního rohu.
• Během fáze sčítání je mřížka sečtena na úhlopříčkách.
• Konečně, pokud je nutná fáze přenosu, odpověď, jak je znázorněna na levé a spodní straně mřížky, se převede na normální formu přenesením deseti číslic jako dlouhého sčítání nebo násobení.

Příklad

Obrázky vpravo ukazují, jak vypočítat 345 × 12 pomocí mřížkového násobení. Jako komplikovanější příklad zvažte následující obrázek zobrazující výpočet 23 958 233 vynásobený 5 830 (multiplikátor); výsledek je 139 676 498 390. Všimněte si, že 23 958 233 je podél horní části mříže a 5 830 je po pravé straně. Produkty vyplňují mřížku a součet těchto produktů (na diagonále) je podél levé a spodní strany. Poté se tyto částky sečtou, jak je ukázáno.

     2   3   9   5   8   2   3   3
   +---+---+---+---+---+---+---+---+-
   |1 /|1 /|4 /|2 /|4 /|1 /|1 /|1 /|
   | / | / | / | / | / | / | / | / | 5
 01|/ 0|/ 5|/ 5|/ 5|/ 0|/ 0|/ 5|/ 5|
   +---+---+---+---+---+---+---+---+-
   |1 /|2 /|7 /|4 /|6 /|1 /|2 /|2 /|
   | / | / | / | / | / | / | / | / | 8
 02|/ 6|/ 4|/ 2|/ 0|/ 4|/ 6|/ 4|/ 4|
   +---+---+---+---+---+---+---+---+-
   |0 /|0 /|2 /|1 /|2 /|0 /|0 /|0 /|
   | / | / | / | / | / | / | / | / | 3
 17|/ 6|/ 9|/ 7|/ 5|/ 4|/ 6|/ 9|/ 9|
   +---+---+---+---+---+---+---+---+-
   |0 /|0 /|0 /|0 /|0 /|0 /|0 /|0 /|
   | / | / | / | / | / | / | / | / | 0
 24|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|
   +---+---+---+---+---+---+---+---+-
     26  15  13  18  17  13  09  00

 01
 002
 0017
 00024
 000026
 0000015
 00000013
 000000018
 0000000017
 00000000013
 000000000009
 0000000000000
 —————————————
  139676498390

= 139,676,498,390

Binární nebo rolnické násobení

Binární metoda je také známá jako rolnické násobení, protože byla široce používána lidmi, kteří jsou klasifikováni jako rolníci, a proto si nezapamatovali multiplikační tabulky potřebné pro dlouhé násobení. Algoritmus byl používán ve starověkém Egyptě. Jeho hlavní výhody spočívají v tom, že se lze rychle naučit, nevyžaduje žádné zapamatování a lze je provádět pomocí žetonů, jako jsou pokerové žetony , pokud není k dispozici papír a tužka. Nevýhodou je, že to vyžaduje více kroků než dlouhé násobení, takže to může být pro velká čísla nepraktické.

Popis

Na papír si zapište do jednoho sloupce čísla, která získáte, když multiplikátor opakovaně snížíte na polovinu, zbytek ignorujete; ve sloupci vedle něj opakovaně zdvojnásobte multiplikand. Přeškrtněte každý řádek, ve kterém je poslední číslice prvního čísla sudá, a přidejte zbývající čísla do druhého sloupce, abyste získali produkt.

Příklady

Tento příklad používá násobení rolníků k vynásobení 11 na 3, aby dospěl k výsledku 33.

Decimal:     Binary:
11   3       1011  11
5    6       101  110
2   12       10  1100
1   24       1  11000
    ——         ——————
    33         100001

Výslovný popis kroků:

• 11 a 3 jsou napsány nahoře
• 11 se sníží na polovinu (5,5) a 3 se zdvojnásobí (6). Částečná část se zahodí (5,5 se stane 5).
• 5 se sníží na polovinu (2,5) a 6 se zdvojnásobí (12). Částečná část se zahodí (2,5 se stane 2). Údaj v levém sloupci (2) je sudý , takže údaj v pravém sloupci (12) je vyřazen.
• 2 se sníží na polovinu (1) a 12 se zdvojnásobí (24).
• Všechny nepoškrábané hodnoty jsou sečteny: 3 + 6 + 24 = 33.

Metoda funguje, protože násobení je distribuční , takže:

${\ Displaystyle {\ begin {aligned} 3 \ times 11 & = 3 \ times (1 \ times 2^{0} +1 \ times 2^{1} +0 \ times 2^{2} +1 \ times 2^ {3}) \\ & = 3 \ times (1+2+8) \\ & = 3+6+24 \\ & = 33. \ end {aligned}}}$

Složitější příklad s použitím čísel z dřívějších příkladů (23 958 233 a 5 830):

Decimal:             Binary:
5830  23958233       1011011000110  1011011011001001011011001
2915  47916466       101101100011  10110110110010010110110010
1457  95832932       10110110001  101101101100100101101100100
728  191665864       1011011000  1011011011001001011011001000
364  383331728       101101100  10110110110010010110110010000
182  766663456       10110110  101101101100100101101100100000
91  1533326912       1011011  1011011011001001011011001000000
45  3066653824       101101  10110110110010010110110010000000
22  6133307648       10110  101101101100100101101100100000000
11 12266615296       1011  1011011011001001011011001000000000
5  24533230592       101  10110110110010010110110010000000000
2  49066461184       10  101101101100100101101100100000000000
1  98132922368       1  1011011011001001011011001000000000000
  ————————————          1022143253354344244353353243222210110 (before carry)
  139676498390         10000010000101010111100011100111010110

Binární násobení v počítačích

Toto je variace množení rolníků.

V základně 2 se dlouhé násobení snižuje na téměř triviální operaci. Pro každý bit '1' v multiplikátoru posuňte multiplikátor o příslušnou částku a poté sečtěte posunuté hodnoty. V některých procesorech je rychlejší použít bitové posuny a sčítání než pokyny pro násobení, zvláště pokud je multiplikátor malý nebo vždy stejný.

Posuňte a přidejte

Historicky počítače používaly k násobení malých celých čísel algoritmus „posun a přidání“. Na stejné algoritmus se redukuje dlouhé násobení základny 2 a rolnické násobení základny 2 . V základu 2 se vynásobení jednou číslicí multiplikátoru sníží na jednoduchou sérii logických operací AND . Každý dílčí součin se přičte k průběžné částce, jakmile se vypočítá každý dílčí součin. Většina aktuálně dostupných mikroprocesorů implementuje tento nebo jiné podobné algoritmy (například Boothovo kódování ) pro různá celočíselná a plovoucí desetinnou čárku v multiplikátorech hardwaru nebo v mikrokódu .

Na aktuálně dostupných procesorech je bitová instrukce posunu rychlejší než instrukce násobení a lze ji použít k násobení (posun vlevo) a dělení (posun vpravo) mocninami dvou. Násobení konstantou a dělení konstantou lze implementovat pomocí posloupnosti posunů a sčítání nebo odčítání. Například existuje několik způsobů, jak vynásobit 10 pomocí pouze bitového posunu a sčítání.

((x << 2) + x) << 1 # Here 10*x is computed as (x*2^2 + x)*2
(x << 3) + (x << 1) # Here 10*x is computed as x*2^3 + x*2

V některých případech takové sekvence posunů a sčítání nebo odčítání překonají hardwarové multiplikátory a zejména rozdělovače. Dělení číslem formuláře nebo často může být převedeno na tak krátkou sekvenci. ${\ displaystyle 2^{n}}$${\ Displaystyle 2^{n} \ pm 1}$

Tyto typy sekvencí musí být vždy použity pro počítače, které nemají instrukci „násobení“, a mohou být také použity rozšířením na čísla s plovoucí desetinnou čárkou, pokud jeden nahradí posuny výpočtem 2*x jako x+x , protože tyto jsou logicky ekvivalentní.

Násobení čtvrtletí čtverce

Dvě veličiny lze vynásobit pomocí čtverečkovaných čtverců s využitím následující identity zahrnující podlahovou funkci, kterou některé zdroje připisují babylonské matematice (2000–1600 př. N. L.).

${\ Displaystyle \ left \ lfloor {\ frac {\ left (x+y \ right)^{2}} {4}} \ right \ rfloor -\ left \ lfloor {\ frac {\ left (xy \ right)^ {2}} {4}} \ right \ rfloor = {\ frac {1} {4}} \ left (\ left (x^{2}+2xy+y^{2} \ right)-\ left (x ^{2} -2xy+y^{2} \ right) \ right) = {\ frac {1} {4}} \ left (4xy \ right) = xy.}$

Pokud je jedno z x + y a x - y liché, druhé je také liché, takže jejich čtverce jsou 1 mod 4, potom zabírání podlahy sníží oba o čtvrtinu; odčítání pak zruší čtvrtiny a vyřazení zbytků nezpůsobí žádný rozdíl ve srovnání se stejným výrazem bez podlahových funkcí. Níže je vyhledávací tabulka čtverečků se zbytkem vyřazeným pro číslice 0 až 18; to umožňuje znásobení čísel až na 9 × 9 .

Pokud například chcete vynásobit 9 čísly 3, zjistíte, že součet a rozdíl jsou 12, respektive 6. Při pohledu na obě tyto hodnoty v tabulce se získá 36 a 9, přičemž rozdíl je 27, což je součin 9 a 3.

Antoine Voisin vydal v roce 1817 tabulku čtverečků od 1 do 1000 jako pomůcku při rozmnožování. Větší tabulku čtverečků od 1 do 100 000 publikoval Samuel Laundy v roce 1856 a tabulku od 1 do 200 000 Joseph Blater v roce 1888.

Čtvrtletní multiplikátory byly použity v analogových počítačích k vytvoření analogového signálu, který byl produktem dvou analogových vstupních signálů. V této aplikaci je součet a rozdíl dvou vstupních napětí tvořen pomocí operačních zesilovačů . Čtverec každého z nich je aproximován pomocí lineárních obvodů po částech . Nakonec je rozdíl dvou čtverců vytvořen a zmenšen o faktor jedné čtvrtiny pomocí dalšího operačního zesilovače.

V roce 1980 navrhl Everett L. Johnson použití metody quarter square v digitálním multiplikátoru. Například pro vytvoření součinu dvou 8bitových celých čísel digitální zařízení tvoří součet a rozdíl, vyhledá obě veličiny v tabulce čtverců, vezme rozdíl výsledků a vydělí čtyřmi posunutím dvou bitů na že jo. U 8bitových celých čísel bude mít tabulka čtverečků 2 ⁹ -1 -1 = 511 položek (jeden záznam pro celý rozsah 0..510 možných součtů, rozdíly využívající pouze prvních 256 záznamů v rozsahu 0..255) popř. 2 ⁹ -1 = 511 záznamů (použití záporných rozdílů pomocí techniky 2 doplňků a 9bitového maskování, které zabrání testování znaku rozdílů), každý záznam má šířku 16 bitů (vstupní hodnoty jsou od (0²/4) ) = 0 až (510²/4) = 65025).

Technika multiplikátoru Quarter square také prospěla 8bitovým systémům, které nemají žádnou podporu pro hardwarový multiplikátor. Charles Putney to implementoval pro 6502 .

Rychlé multiplikační algoritmy pro velké vstupy

Komplexní algoritmus násobení

Komplexní násobení obvykle zahrnuje čtyři násobení a dvě sčítání.

${\ Displaystyle (a+bi) (c+di) = (ac-bd)+(bc+ad) i.}$

Nebo

${\ displaystyle {\ begin {array} {c | c | c} \ times & a & bi \\\ hline c & ac & bci \\\ hline di & adi & -bd \ end {array}}}$

Existuje však způsob, jak snížit počet násobení na tři.

Součin ( a  +  bi ) · ( c  +  di ) lze vypočítat následujícím způsobem.

k ₁ = c · ( a + b )

k ₂ = a · ( d - c )

k ₃ = b · ( c + d )

Skutečná část = k ₁ - k ₃

Imaginární část = k ₁ + k ₂ .

Tento algoritmus používá pouze tři násobení místo čtyř a pět sčítání nebo odčítání místo dvou. Pokud je násobení dražší než tři sčítání nebo odčítání, jako při ručním výpočtu, pak dojde ke zvýšení rychlosti. Na moderních počítačích může znásobení a přidání trvat přibližně stejnou dobu, takže nemusí dojít ke zvýšení rychlosti. Existuje kompromis v tom, že při použití plovoucí desetinné čárky může dojít k určité ztrátě přesnosti.

Pro rychlé Fourierovy transformace (FFT) (nebo jakoukoli lineární transformaci ) jsou komplexní násobky konstantními koeficienty c  +  di ( ve FFT nazývané twiddle faktory ), v takovém případě lze dvě z adicí ( d - c a c + d ) předpočítat . Vyžadují se tedy pouze tři násobení a tři přidání. Obchodování s násobením za přidání tímto způsobem však již nemusí být u moderních jednotek s plovoucí desetinnou čárkou výhodné .

Násobení Karatsuba

U systémů, které potřebují znásobit čísla v rozsahu několika tisíc číslic, jako jsou systémy počítačové algebry a knihovny bignum , je dlouhé násobení příliš pomalé. Tyto systémy mohou využívat násobení Karatsuba , které bylo objeveno v roce 1960 (publikováno v roce 1962). Jádro Karatsubovy metody spočívá v pozorování, že dvouciferné násobení lze provádět pouze třemi, namísto klasicky požadovaných čtyř násobení. Toto je příklad toho, čemu se nyní říká algoritmus rozděl a panuj . Předpokládejme, že chceme znásobit dvě dvouciferná čísla základny- m : x ₁ m + x ₂ a y ₁ m + y ₂ :

1. spočítejte x ₁ · y ₁ , zavolejte výsledek F
2. spočítejte x ₂ · y ₂ , zavolejte výsledek G
3. spočítejte ( x ₁ + x ₂ ) · ( y ₁ + y ₂ ), zavolejte výsledek H
4. spočítejte H - F - G , zavolejte výsledek K ; toto číslo se rovná x ₁ · y ₂ + x ₂ · y ₁
5. výpočetní F · m ² + K · m + G .

Pro výpočet těchto tří produktů základních m čísel můžeme použít stejný trik znovu, efektivně pomocí rekurze . Jakmile jsou čísla vypočítána, musíme je sečíst (kroky 4 a 5), ​​což zabere asi n operací.

Násobení Karatsuba má časovou složitost O ( n ^{log ₂ 3} ) ≈ O ( n ^1,585 ), což činí tuto metodu výrazně rychlejší než dlouhé násobení. Kvůli režii rekurze je Karatsubova násobení pomalejší než dlouhé násobení pro malé hodnoty n ; typické implementace proto přecházejí na dlouhé násobení pro malé hodnoty n .

Karatsubův algoritmus byl prvním známým algoritmem pro násobení, který je asymptoticky rychlejší než dlouhé násobení, a lze jej tedy považovat za výchozí bod pro teorii rychlého násobení.

V roce 1963 Peter Ungar navrhl nastavení m na i, aby se dosáhlo podobného snížení v algoritmu komplexního násobení. Chcete -li znásobit ( a  +  bi ) · ( c  +  di ), postupujte takto:

1. spočítejte b · d , zavolejte výsledek F
2. spočítejte a · c , zavolejte výsledek G
3. spočítejte ( a + b ) · ( c + d ), zavolejte výsledek H
4. imaginární část výsledku je K = H - F - G = a · d + b · c
5. skutečná část výsledku je G - F = a · c - b · d

Stejně jako algoritmus v předchozí části to vyžaduje tři násobení a pět sčítání nebo odčítání.

Toom – Cook

Další způsob násobení se nazývá Toom – Cook nebo Toom-3. Metoda Toom – Cook rozděluje každé číslo, které má být vynásobeno, na více částí. Metoda Toom – Cook je jednou z generalizací metody Karatsuba. Třícestný Toom – Cook může provádět násobení velikosti 3N za cenu pěti násobků- N násobení. To operaci zrychlí faktorem 9/5, zatímco metoda Karatsuba ji zrychlí o 4/3.

Přestože používání stále více dílů může dále zkrátit čas strávený rekurzivním násobením, roste také režie z přírůstků a správy číslic. Z tohoto důvodu je metoda Fourierových transformací obvykle rychlejší u čísel s několika tisíci číslicemi a asymptoticky rychlejší u ještě větších čísel.

Fourierovy transformační metody

Ukázka násobení 1234 × 5678 = 7006652 pomocí rychlých Fourierových transformací (FFT). Jsou použity číslově teoretické transformace v celých číslech modulo 337, přičemž jako 8. kořen jednoty je vybráno 85. Základna 10 se používá místo báze 2 ^w pro ilustrativní účely.

Základní myšlenkou Strassena (1968) je použít rychlé polynomické násobení k provedení rychlého celočíselného násobení. Algoritmus byl praktický a teoretické záruky poskytly v roce 1971 Schönhage a Strassen, což vedlo k algoritmu Schönhage – Strassen . Podrobnosti jsou následující: Vybereme největší celé číslo w, které během níže uvedeného postupu nezpůsobí přetečení . Poté rozdělíme dvě čísla do m skupin w bitů následujícím způsobem

${\ Displaystyle a = \ sum _ {i = 0}^{m-1} {a_ {i} 2^{wi}} {\ text {and}} b = \ sum _ {j = 0}^{m -1} {b_ {j} 2^{wj}}.}$

Podíváme se na tato čísla jako polynomy v x , kde x = 2 ^w , abychom dostali,

${\ Displaystyle a = \ sum _ {i = 0}^{m-1} {a_ {i} x^{i}} {\ text {and}} b = \ sum _ {j = 0}^{m -1} {b_ {j} x^{j}}.}$

Pak můžeme říci, že

${\ Displaystyle ab = \ sum _ {i = 0}^{m-1} \ sum _ {j = 0}^{m-1} a_ {i} b_ {j} x^{(i+j)} = \ sum _ {k = 0}^{2m-2} c_ {k} x^{k}.}$

Je zřejmé, že výše uvedené nastavení je realizováno polynomickým násobením dvou polynomů a a b . Zásadním krokem je nyní použít rychlé Fourierovo násobení polynomů k realizaci násobení výše rychleji než v naivním čase O ( m ² ).

Abychom zůstali v modulárním nastavení Fourierových transformací, hledáme prsten s (2 m ) th kořenem jednoty. Proto děláme multiplikační modul N (a tedy v kruhu Z / NZ ). Dále, N musí být zvoleny tak, že neexistuje žádný ‚obtékání‘ v podstatě žádná snížení modulo N dojít. Volba N je tedy zásadní. Mohlo by to být například provedeno jako

${\ Displaystyle N = 2^{3m} +1.}$

Prsten Z / NZ by tedy měl (2 m ) th kořen jednoty, konkrétně 8. Lze také zkontrolovat, že c _k < N , a tedy nedojde k žádnému zalomení.

Algoritmus má časovou složitost Θ ( n  log ( n ) log (log ( n ))) a v praxi se používá pro čísla s více než 10 000 až 40 000 desítkovými číslicemi. V roce 2007 to vylepšil Martin Fürer ( Fürerův algoritmus ), aby poskytl časovou složitost n  log ( n ) 2 ^{Θ ( log * ( n ))} pomocí Fourierových transformací přes komplexní čísla. Anindya De, Chandan Saha, Piyush Kurur a Ramprasad Saptharishi poskytli v roce 2008 podobný algoritmus využívající modulární aritmetiku a dosáhli stejného času běhu. V souvislosti s výše uvedeným materiálem dosáhli tito autoři N mnohem méně než 2 ^{3 k} + 1, takže Z / NZ má (2 m ) th kořen jednoty. To zrychluje výpočet a snižuje časovou složitost. Tyto posledně jmenované algoritmy jsou však pro neprakticky velké vstupy pouze rychlejší než Schönhage – Strassen.

V březnu 2019 David Harvey a Joris van der Hoeven vydali dokument popisující multiplikační algoritmus O ( n log n ) .

Použití číselně teoretických transformací místo diskrétních Fourierových transformací se vyhne problémům s chybami zaokrouhlení pomocí modulární aritmetiky namísto aritmetiky s pohyblivou řádovou čárkou. Aby bylo možné použít faktoring, který umožňuje FFT pracovat, délka transformace musí být faktorovatelná pro malé prvočísla a musí být faktorem N - 1 , kde N je velikost pole. Zejména výpočet pomocí Galoisova pole GF ( k ² ), kde k je Mersenneova prime , umožňuje použití transformace dimenzované na mocninu 2; např. k = 2 ³¹ - 1 podporuje transformační velikosti až 2 ³² .

Dolní hranice

Pro znásobení dvou n -bitových čísel na jednom procesoru existuje triviální spodní hranice Ω ( n ) ; není znám žádný algoritmus shody (na konvenčních strojích, to znamená na ekvivalentních strojích Turing) ani žádná ostřejší dolní hranice. Násobení lži mimo AC ⁰ [ p ] pro každou primární p , což znamená, že žádná rodina konstantní hloubky, polynomu (či dokonce subexponential) velikost obvodů s využitím AND, OR, NOT a MOD _p brány, které mohou počítat produkt. To vyplývá z konstantní hloubky redukce MOD _q na násobení. Dolní hranice pro násobení jsou také známé pro některé třídy větvících programů .

Polynomiální násobení

Všechny výše uvedené multiplikační algoritmy lze také rozšířit na násobení polynomů . Pro multiplikaci polynomů lze například použít Strassenův algoritmus. Alternativně lze k převedení problému násobení polynomů do jediné binární multiplikace použít substituční techniku Kronecker .

Metody dlouhého násobení lze zobecnit, aby bylo možné násobit algebraické vzorce:

 14ac - 3ab + 2 multiplied by ac - ab + 1

 14ac  -3ab   2
   ac   -ab   1
 ————————————————————
 14a2c2  -3a2bc   2ac
        -14a2bc         3 a2b2  -2ab
                 14ac           -3ab   2
 ———————————————————————————————————————
 14a2c2 -17a2bc   16ac  3a2b2    -5ab  +2
 =======================================

Jako další příklad násobení na základě sloupců zvažte vynásobení 23 dlouhých tun (t), 12 stovek (cwt) a 2 čtvrtin (qtr) 47. Tento příklad používá opatření avoirdupois : 1 t = 20 cwt, 1 cwt = 4 qtr.

    t    cwt  qtr
   23     12    2
               47 x
 ————————————————
  141     94   94
  940    470
   29     23
 ————————————————
 1110    587   94
 ————————————————
 1110      7    2
 =================  Answer: 1110 ton 7 cwt 2 qtr

Nejprve vynásobte čtvrtiny 47, výsledek 94 se zapíše do prvního pracovního prostoru. Dále vynásobte cwt 12*47 = (2 + 10)*47, ale zatím nesčítejte dílčí výsledky (94, 470). Podobně vynásobte 23 47 výnosy (141, 940). Sloupec čtvrtletí se sečte a výsledek se umístí do druhého pracovního prostoru (v tomto případě triviální tah). 94 čtvrtletí je 23 cwt a 2 qtr, takže umístěte 2 do odpovědi a vložte 23 do dalšího sloupce vlevo. Nyní sečtěte tři položky ve sloupci cwt a dejte 587. To je 29 t 7 cwt, napište tedy 7 do odpovědi a 29 do sloupce vlevo. Nyní sečtěte sloupec tun. Nelze provádět žádné úpravy, takže výsledek je pouze zkopírován dolů.

Stejné rozložení a metody lze použít pro všechna tradiční měření a nedecimální měny, jako je starý britský systém £ sd .

Viz také

• Binární multiplikátor
• Algoritmus dělení
• Logaritmus
• Mentální výpočet
• Prosthaphaeresis
• Pravidlo skluzu
• Systém Trachtenberg
• Hornerovo schéma pro hodnocení polynomu
• Systém čísel zbytků § Násobení pro další rychlý multiplikační algoritmus, zvláště účinný, když je mnoho operací prováděno postupně, například v lineární algebře
• Dadda multiplikátor
• Wallaceův strom

Reference

Další čtení

• Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
• Savard, John JG (2018) [2006]. „Pokročilé aritmetické techniky“ . quadibloc . Archivováno od originálu dne 2018-07-03 . Citováno 2018-07-16 .
• Johansson, Kenny. Nízký výkon a nízká složitost Výpočty založené na řazení a přidávání (PDF) (Disertační práce). Linköping Studies in Science and Technology (1. vyd.). Linköping, Švédsko: Katedra elektrotechniky, Linköping University . ISBN 978-91-7393-836-5. ISSN  0345-7524 . Č. 1201. Archivováno (PDF) z originálu dne 2017-08-13 . Citováno 2021-08-23 . (x+268 stran)

externí odkazy

Základní aritmetika

• Mnoho způsobů aritmetiky v každodenní matematice UCSMP
• Prezentace v Powerpointu o starověké matematice
• Flash Video s multiplikácí mříže

Pokročilé algoritmy

• Multiplikační algoritmy používané GMP