Multiplikationsalgoritm - Multiplication algorithm

En multiplikationsalgoritm är en algoritm (eller metod) för att multiplicera två tal. Beroende på storleken på siffrorna används olika algoritmer. Effektiva multiplikationsalgoritmer har funnits sedan decimalsystemets tillkomst.

Rutnätmetod

Den metod galler (eller box-metoden) är en inledande förfarande för fler siffrig multiplikation som ofta lärs ut till elever på grundskolan eller folkskola . Det har varit en standard del av den nationella grundskolans matematikplan i England och Wales sedan slutet av 1990 -talet.

Båda faktorerna är uppdelade ("uppdelade") i sina hundratals, tiotals och enhetsdelar, och produkterna från delarna beräknas sedan uttryckligen i ett relativt enkelt multiplikationssteg, innan dessa bidrag sammanställs för att ge det slutliga svaret i ett separat tilläggssteg.

Beräkningen 34 × 13 kan till exempel beräknas med rutnätet:

  300
   40
   90
 + 12
 ————
  442

följt av tillägg för att erhålla 442, antingen i en enda summa (se till höger), eller genom att bilda raderna för rad (300 + 40) + (90 + 12) = 340 + 102 = 442.

Denna beräkningsmetod (men inte nödvändigtvis med det uttryckliga nätarrangemanget) är också känd som delproduktalgoritmen . Dess väsen är beräkningen av de enkla multiplikationerna separat, med alla tillägg kvar till det sista samlingsstadiet.

Gridmetoden kan i princip tillämpas på faktorer av alla storlekar, även om antalet underprodukter blir besvärligt när antalet siffror ökar. Ändå ses det som en användbar och tydlig metod för att införa idén om flersiffriga multiplikationer; och i en tid då de flesta multiplikationsberäkningarna görs med hjälp av en miniräknare eller ett kalkylblad kan det i praktiken vara den enda multiplikationsalgoritmen som vissa elever någonsin kommer att behöva.

Lång multiplikation

Om ett positionsbetalsystem används lärs ett naturligt sätt att multiplicera siffror i skolor som lång multiplikation , ibland kallad klassskolemultiplikation , ibland kallad standardalgoritm : multiplicera multiplikand med varje siffra i multiplikatorn och lägg sedan ihop alla korrekta förändrade resultat. Det kräver memorering av multiplikationstabellen för enkelsiffror.

Detta är den vanliga algoritmen för att multiplicera större tal för hand i bas 10. Datorer använde initialt ett mycket liknande skift och lägger till algoritm i bas 2, men moderna processorer har optimerat kretsar för snabba multiplikationer med effektivare algoritmer, till priset av en mer komplex hårdvaruförverkligande. En person som gör lång multiplikation på papper kommer att skriva ner alla produkter och sedan lägga ihop dem; en abacus -användare summerar produkterna så snart var och en har beräknats.

Exempel

Detta exempel använder lång multiplikation för att multiplicera 23,958,233 (multiplicand) med 5,830 (multiplikator) och kommer till 139,676,498,390 för resultatet (produkten).

      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        )

Nedanför beskriver pseudokoden processen med ovanstående multiplikation. Det behåller bara en rad för att behålla summan som slutligen blir resultatet. Observera att operatorn '+=' används för att beteckna summan till befintligt värde och lagra drift (liknande språk som Java och C) för kompakthet.

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

Optimera rymdkomplexitet

Låt n vara det totala antalet siffror i de två ingångsnumren i bas D . Om resultatet måste hållas i minnet är rymdkomplexiteten trivial Θ ( n ). Men i vissa applikationer behöver inte hela resultatet lagras i minnet och istället kan siffrorna i resultatet strömmas ut när de beräknas (till exempel till systemkonsol eller fil). I dessa scenarier har lång multiplikation fördelen att den enkelt kan formuleras som en loggutrymme -algoritm ; det vill säga en algoritm som bara behöver arbetsyta proportionell mot logaritmen för antalet siffror i ingången ( Θ (log  n )). Detta är den dubbla logaritmen för siffrorna som multipliceras själva (logg  N ). Observera att operanderna själva fortfarande måste hållas i minnet och deras Θ ( n ) utrymme beaktas inte i denna analys.

Metoden är baserad på observationen att varje siffra i resultatet kan beräknas från höger till vänster med bara kunskap om bärningen från föregående steg. Låta en _i och b _jag vara den i : te siffran i operand, med en och b vadderad till vänster av nollor att vara längden n , r _jag vara den i : te siffran i resultatet och c _jag vara carry genereras för r _i (i = 1 är den högsta siffran) då

${\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}}}$

eller

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

Ett enkelt induktivt argument visar att bäringen aldrig kan överstiga n och den totala summan för r _i aldrig kan överstiga D * n : transporterna in i den första kolumnen är noll, och för alla andra kolumner finns det högst n siffror i kolumnen och högst n från den föregående kolumnen (genom induktionshypotesen). Summan är högst D * n , och överföringen till nästa kolumn är högst D * n / D eller n . Således kan båda dessa värden lagras i O (log n ) siffror.

I pseudokod är log-space-algoritmen:

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

Användning i datorer

Vissa chips implementerar lång multiplikation, i hårdvara eller i mikrokod , för olika heltal och flytande ordstorlekar. I aritmetik med godtycklig precision är det vanligt att använda lång multiplikation med basen inställd på 2 ^w , där w är antalet bitar i ett ord, för att multiplicera relativt små tal.

För att multiplicera två tal med n -siffror med denna metod, behöver man cirka n ² operationer. Mer formellt: med hjälp av en naturlig storleksmätning av antalet siffror är tidskomplexiteten för att multiplicera två n -siffriga tal med lång multiplikation Θ ( n ² ).

När de implementeras i programvara måste långa multiplikationsalgoritmer hantera överflöd under tillägg, vilket kan vara dyrt. En typisk lösning är att representera talet i en liten bas, b , så att till exempel 8b är ett representabelt maskintal. Flera tillägg kan sedan utföras innan ett överflöd inträffar. När antalet blir för stort lägger vi till en del av det i resultatet, eller så bär vi och kartlägger den återstående delen till ett tal som är mindre än b . Denna process kallas normalisering . Richard Brent använde detta tillvägagångssätt i sitt Fortran -paket, MP.

Gittermultiplikation

Sätt först upp rutnätet genom att markera dess rader och kolumner med siffrorna som ska multipliceras. Fyll sedan i rutorna med tio siffror i de övre trianglarna och enhetssiffrorna på undersidan.

Slutligen summera längs de diagonala sträckorna och bära efter behov för att få svaret

Gitter, eller sil, multiplikation är algoritmiskt ekvivalent med lång multiplikation. Det kräver framställning av ett gitter (ett rutnät ritat på papper) som styr beräkningen och separerar alla multiplikationer från tilläggen . Det infördes till Europa 1202 i Fibonacci 's Liber Abaci . Fibonacci beskrev operationen som mental, med hjälp av höger och vänster hand för att bära mellanliggande beräkningar. Matrakçı Nasuh presenterade 6 olika varianter av denna metod i denna 1500-talsbok, Umdet-ul Hisab. Det användes i stor utsträckning i Enderun -skolor i det ottomanska riket. Napiers ben , eller Napiers stavar använde också denna metod, som publicerades av Napier 1617, året för hans död.

Som visas i exemplet skrivs multiplikand och multiplikator ovan och till höger om ett gitter eller en sil. Den finns i Muhammad ibn Musa al-Khwarizmis "Arithmetic", en av Leonardos källor som nämns av Sigler, författare till "Fibonaccias Liber Abaci", 2002.

• Under multiplikationsfasen fylls gallret med tvåsiffriga produkter av motsvarande siffror som märker varje rad och kolumn: tiotalet går i det övre vänstra hörnet.
• Under additionsfasen summeras gitteret på diagonalerna.
• Slutligen, om en bärfas är nödvändig, omvandlas svaret som visas längs vänster och botten av gallret till normal form genom att bära tio siffror som vid lång addition eller multiplikation.

Exempel

Bilderna till höger visar hur man beräknar 345 × 12 med hjälp av gittermultiplikation. Som ett mer komplicerat exempel, överväga bilden nedan som visar beräkningen av 23 958 233 multiplicerat med 5 830 (multiplikator); resultatet är 139 676 498 390. Meddelande 23,958,233 är längs toppen av gallret och 5,830 är längs höger sida. Produkterna fyller gallret och summan av dessa produkter (på diagonalen) är längs vänster och undersida. Sedan summeras dessa summor enligt bilden.

     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är eller bondemultiplikation

Den binära metoden är också känd som bondemultiplikation, eftersom den har använts i stor utsträckning av människor som klassificerats som bönder och därmed inte har memorerat multiplikationstabellerna som krävs för lång multiplikation. Algoritmen användes i forntida Egypten. Dess främsta fördelar är att den kan undervisas snabbt, kräver ingen memorering och kan utföras med tokens, till exempel pokerchips , om papper och penna inte är tillgängliga. Nackdelen är att det tar fler steg än lång multiplikation, så det kan vara obehagligt för stora antal.

Beskrivning

På papper, skriv ner i en kolumn de siffror du får när du upprepade gånger halverar multiplikatorn, ignorerar resten; i en kolumn bredvid den dubbla multiplicand. Strecka varje rad där den sista siffran i det första numret är jämn och lägg till de återstående talen i den andra kolumnen för att få produkten.

Exempel

Detta exempel använder bonde multiplikation för att multiplicera 11 med 3 för att komma fram till ett resultat av 33.

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

Beskriv stegen uttryckligen:

• 11 och 3 är skrivna överst
• 11 halveras (5,5) och 3 fördubblas (6). Den fraktionerade delen kastas (5,5 blir 5).
• 5 halveras (2,5) och 6 fördubblas (12). Den fraktionerade delen kastas (2,5 blir 2). Siffran i den vänstra kolumnen (2) är jämn , så figuren i den högra kolumnen (12) kastas.
• 2 halveras (1) och 12 fördubblas (24).
• Alla icke-repade värden summeras: 3 + 6 + 24 = 33.

Metoden fungerar eftersom multiplikation är distributiv , så:

${\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}}}$

Ett mer komplicerat exempel, med hjälp av siffrorna från de tidigare exemplen (23958233 och 5830):

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är multiplikation i datorer

Detta är en variant av bondemultiplikation.

I bas 2 reduceras lång multiplikation till en nästan trivial operation. För varje '1' bit i multiplikatorn , flytta multiplikand med en lämplig mängd och summera sedan de skiftade värdena. I vissa processorer är det snabbare att använda bitskift och tillägg snarare än multiplikationsinstruktioner, särskilt om multiplikatorn är liten eller alltid densamma.

Skift och lägg till

Historiskt sett använde datorer en "skift och lägg till" -algoritm för att multiplicera små heltal. Både bas 2 lång multiplikation och bas 2 bonde multiplikation reducerar till samma algoritm. I bas 2 reduceras multipliceringen med multipelns enda siffra till en enkel serie logiska OCH -operationer. Varje delprodukt läggs till en löpande summa så snart varje delprodukt har beräknats. De flesta för närvarande tillgängliga mikroprocessorer implementerar denna eller andra liknande algoritmer (som Booth-kodning ) för olika heltal och flytpunktsstorlekar i hårdvarumultiplikatorer eller i mikrokod .

På för närvarande tillgängliga processorer är en bitvis skiftinstruktion snabbare än en multiplikationsinstruktion och kan användas för att multiplicera (skifta vänster) och dela (skift höger) med tvåmakter. Multiplikation med en konstant och division med en konstant kan implementeras med hjälp av en sekvens av skift och adderar eller subtraherar. Till exempel finns det flera sätt att multiplicera med 10 med endast bit-shift och addition.

((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

I vissa fall kommer sådana sekvenser av skiftningar och adderingar eller subtraktioner att överträffa hårdvarumultiplikatorer och särskilt delare. En division med ett nummer i formen eller kan ofta konverteras till en så kort sekvens. ${\displaystyle 2^{n}}$${\displaystyle 2^{n}\pm 1}$

Dessa typer av sekvenser måste alltid användas för datorer som inte har en "multiplicera" -instruktion, och kan också användas som förlängning till flyttal om man ersätter skift med beräkning av 2*x som x+x , eftersom dessa är logiskt likvärdiga.

Kvartal kvadrat multiplikation

Två kvantiteter kan multipliceras med hjälp av fjärdedelar genom att använda följande identitet som innefattar den golvfunktion som vissa källor tillskriver babylonisk matematik (2000–1600 f.Kr.).

${\displaystyle \left\lfloor {\frac {\left(x+y\right)^{2}}{4}}\right\rfloor -\left\lfloor {\frac {\left(x-y\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.}$

Om en av x + y och x - y är udda, är den andra också udda, så deras kvadrater är 1 mod 4, då minskar golvet båda med en fjärdedel; subtraktionen avbryter sedan kvartalen, och att kasta resten ger ingen skillnad jämfört med samma uttryck utan golvfunktionerna. Nedan följer en uppslagstabell över kvartfält med resten kasserad för siffrorna 0 till 18; detta möjliggör multiplikation av tal upp till 9 × 9 .

Om du till exempel ville multiplicera 9 med 3, observerar du att summan och skillnaden är 12 respektive 6. Om man tittar upp båda dessa värden på bordet får man 36 och 9, vars skillnad är 27, vilket är produkten av 9 och 3.

Antoine Voisin publicerade en tabell med kvartsrutor från 1 till 1000 år 1817 som ett hjälpmedel vid multiplikation. Ett större bord med kvartsrutor från 1 till 100000 publicerades av Samuel Laundy 1856 och ett bord från 1 till 200000 av Joseph Blater 1888.

Kvartal kvadratmultiplikatorer användes i analoga datorer för att bilda en analog signal som var produkten av två analoga insignaler. I denna ansökan, summan och skillnaden av två ingångsspänningar bildas med användning av operationsförstärkare . Kvadraten för var och en av dessa approximeras med hjälp av bitvis linjära kretsar. Slutligen bildas och skalas skillnaden mellan de två rutorna med en faktor på en fjärdedel med ytterligare en operationsförstärkare.

År 1980 föreslog Everett L. Johnson att använda kvarts kvadratmetoden i en digital multiplikator. För att bilda produkten av två 8-bitars heltal, till exempel, bildar den digitala enheten summan och skillnaden, tittar upp båda storheterna i en kvadrattabell, tar skillnaden mellan resultaten och delar med fyra genom att flytta två bitar till höger. För 8 -bitars heltal kommer tabellen över kvartrutor att ha 2 ⁹ -1 = 511 poster (en post för hela intervallet 0..510 möjliga summor, skillnaderna med endast de första 256 posterna i intervall 0..255) eller 2 ⁹ -1 = 511 poster (för negativa skillnader används tekniken för 2-kompletteringar och 9-bitars maskering, vilket undviker att testa tecken på skillnader), varvid varje post är 16-bitars bred (inmatningsvärdena är från (0²/4 ) = 0 till (510²/4) = 65025).

Quarter square multiplier-tekniken har också gynnats av 8-bitars system som inte har något stöd för en hårdvarumultiplikator. Charles Putney implementerade detta för 6502 .

Snabba multiplikationsalgoritmer för stora ingångar

Komplex multiplikationsalgoritm

Komplex multiplikation innebär normalt fyra multiplikationer och två tillägg.

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

Eller

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

Men det finns ett sätt att minska antalet multiplikationer till tre.

Produkten ( a  +  bi ) · ( c  +  di ) kan beräknas på följande sätt.

k ₁ = c · ( a + b )

k ₂ = a · ( d - c )

k ₃ = b · ( c + d )

Verklig del = k ₁ - k ₃

Imaginär del = k ₁ + k ₂ .

Denna algoritm använder bara tre multiplikationer, snarare än fyra, och fem tillägg eller subtraktioner snarare än två. Om en multiplicering är dyrare än tre adderar eller subtraherar, som vid beräkning för hand, så är det en ökning i hastighet. På moderna datorer kan en multiplicering och ett tillägg ta ungefär samma tid så att det inte kan finnas någon hastighetsökning. Det finns en avvägning genom att det kan förekomma viss förlust av precision vid användning av flytpunkt.

För snabba Fouriertransformationer (FFT) (eller någon linjär transformation ) är de komplexa multiplikationerna med konstanta koefficienter c  +  di (kallade twiddle -faktorer i FFT), i vilket fall två av tilläggen ( d - c och c + d ) kan beräknas på förhand . Därför krävs bara tre multiplikationer och tre tillägg. Att byta ut en multiplikation för ett tillägg på detta sätt kan dock inte längre vara fördelaktigt med moderna flytande enheter .

Karatsuba multiplikation

För system som behöver multiplicera tal i intervallet mellan flera tusen siffror, till exempel datoralgebrasystem och bignumbibliotek , är lång multiplikation för långsam. Dessa system kan använda Karatsuba -multiplikation , som upptäcktes 1960 (publicerad 1962). Hjärtat i Karatsubas metod ligger i observationen att tvåsiffrig multiplikation kan göras med bara tre snarare än de fyra multiplikationer som klassiskt krävs. Detta är ett exempel på vad som nu kallas en dela-och-erövra-algoritm . Antag att vi vill multiplicera två tvåsiffriga bas- m- tal: x ₁ m + x ₂ och y ₁ m + y ₂ :

1. beräkna x ₁ · y ₁ , ring resultatet F
2. beräkna x ₂ · y ₂ , ring resultatet G
3. beräkna ( x ₁ + x ₂ ) · ( y ₁ + y ₂ ), ring resultatet H
4. beräkna H - F - G , kalla resultatet K ; detta tal är lika med x ₁ · y ₂ + x ₂ · y ₁
5. compute F · m ² + K · m + G .

För att beräkna dessa tre produkter med bas -m -nummer kan vi använda samma trick igen, effektivt med hjälp av rekursion . När siffrorna har beräknats måste vi lägga till dem (steg 4 och 5), vilket tar ungefär n operationer.

Karatsubamultiplikation har en tidskomplexitet på O ( n ^{log ₂ 3} ) ≈ O ( n ^1.585 ), vilket gör denna metod betydligt snabbare än lång multiplikation. På grund av kostnaden för rekursion är Karatsubas multiplikation långsammare än lång multiplikation för små värden på n ; typiska implementeringar byter därför till lång multiplikation för små värden på n .

Karatsubas algoritm var den första kända algoritmen för multiplikation som är asymptotiskt snabbare än lång multiplikation, och kan därmed ses som utgångspunkten för teorin om snabba multiplikationer.

1963 föreslog Peter Ungar att ställa in m till i för att få en liknande minskning av den komplexa multiplikationsalgoritmen. För att multiplicera ( a  +  bi ) · ( c  +  di ), följ dessa steg:

1. beräkna b · d , ring resultatet F
2. beräkna a · c , ring resultatet G
3. beräkna ( a + b ) · ( c + d ), ring resultatet H
4. den imaginära delen av resultatet är K = H - F - G = a · d + b · c
5. den verkliga delen av resultatet är G - F = a · c - b · d

Liksom algoritmen i föregående avsnitt kräver detta tre multiplikationer och fem additioner eller subtraktioner.

Toom – Cook

En annan metod för multiplikation kallas Toom – Cook eller Toom-3. Metoden Toom – Cook delar upp varje tal som ska multipliceras i flera delar. Toom – Cook -metoden är en av generaliseringarna av Karatsuba -metoden. En trevägs Toom-Cook kan göra en storlek- 3N multiplikation för kostnaden för fem storlek- N multiplikationer. Detta påskyndar operationen med en faktor 9/5, medan Karatsuba -metoden accelererar den med 4/3.

Även om fler och fler delar kan minska tiden som läggs på rekursiva multiplikationer ytterligare, ökar också omkostnaderna från tillägg och siffrahantering. Av denna anledning är metoden för Fouriertransformationer vanligtvis snabbare för tal med flera tusen siffror och asymptotiskt snabbare för ännu större tal.

Fourier -omvandlingsmetoder

Demonstration av att multiplicera 1234 × 5678 = 7006652 med hjälp av snabba Fourier -transformer (FFT). Talteoretiska transformationer i heltalet modulo 337 används och väljer 85 som en åttonde rot av enhet. Bas 10 används i stället för bas 2 ^w för illustrativa ändamål.

Grundidén på grund av Strassen (1968) är att använda snabb polynommultiplikation för att utföra snabb heltalsmultiplikation. Algoritmen gjordes praktisk och teoretiska garantier lämnades 1971 av Schönhage och Strassen vilket resulterade i algoritmen Schönhage – Strassen . Detaljerna är följande: Vi väljer det största heltalet w som inte kommer att orsaka överflöd under processen som beskrivs nedan. Sedan delar vi de två talen i m -grupper av w -bitar enligt följande

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

Vi ser på dessa tal som polynom i x , där x = 2 ^w , för att få,

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

Då kan vi säga att

${\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}.}$

Uppenbarligen uppnås ovanstående inställning genom polynommultiplikation, av två polynom a och b . Det avgörande steget nu är att använda Fast Fourier multiplikation av polynom för att realisera multiplikationerna ovan snabbare än i naiv O ( m ² ) tid.

För att stanna kvar i den modulära inställningen för Fourier -transformationer letar vi efter en ring med en (2 m ) rots enhet. Därför gör vi multiplikationsmodul N (och därmed i Z / NZ -ringen ). Vidare måste N väljas så att det inte finns någon "linda runt", i huvudsak uppstår inga reduktioner modulo N. Således är valet av N avgörande. Det kan till exempel göras som,

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

Ringen Z / NZ skulle således ha (2 m ) roten av enhet, nämligen 8. Dessutom kan det kontrolleras att c _k < N , och därmed ingen omringning kommer att inträffa.

Algoritmen har en tidskomplexitet på Θ ( n  log ( n ) log (log ( n ))) och används i praktiken för tal med mer än 10 000 till 40 000 decimaler. År 2007 förbättrades detta av Martin Fürer ( Ferrers algoritm ) för att ge en tidskomplexitet av n  log ( n ) 2 ^{Θ ( log * ( n )) med} hjälp av Fourier -transformer över komplexa tal. Anindya De, Chandan Saha, Piyush Kurur och Ramprasad Saptharishi gav en liknande algoritm med hjälp av modulär aritmetik 2008 för att uppnå samma drifttid. I samband med ovanstående material, vad dessa senare författare har åstadkommit är att hitta N mycket mindre än 2 ^{3 k} + 1, så att Z / NZ har en (2 m ) th rot av enhet. Detta påskyndar beräkningen och minskar tidskomplexiteten. Dessa senare algoritmer är dock bara snabbare än Schönhage – Strassen för opraktiskt stora ingångar.

I mars 2019 släppte David Harvey och Joris van der Hoeven ett papper som beskriver en O ( n log n ) multiplikationsalgoritm.

Genom att använda talteoretiska transformeringar istället för diskreta Fourier-transformeringar undviks avrundningsfelproblem genom att använda modulär aritmetik istället för floating-point- aritmetik. För att kunna tillämpa factoring som gör det möjligt för FFT att fungera måste längden på transformen vara faktorbar till små primtal och måste vara en faktor N - 1 , där N är fältstorleken. I synnerhet tillåter beräkning med hjälp av ett Galois -fält GF ( k ² ), där k är en Mersenne -prim , användning av en transform som är stor till 2; t.ex. k = 2 ³¹ - 1 stöder transformstorlekar upp till 2 ³² .

Lägre gränser

Det finns en trivial nedre gräns för Ω ( n ) för att multiplicera två n -bit -tal på en enda processor; ingen matchningsalgoritm (på konventionella maskiner, det vill säga på Turing -ekvivalenta maskiner) eller någon vassare nedre gräns är känd. Multiplikation ligger utanför AC ⁰ [ p ] för alla prim- p , vilket betyder att det inte finns någon familj med konstantdjup, polynom (eller till och med supexponentiell) storlekskretsar som använder AND, OR, NOT och MOD _p- portar som kan beräkna en produkt. Detta följer från en konstant djupreduktion av MOD _q till multiplikation. Lägre gränser för multiplikation är också kända för vissa klasser av förgreningsprogram .

Polynom multiplikation

Alla ovanstående multiplikationsalgoritmer kan också expanderas till att multiplicera polynom . Till exempel kan Strassen -algoritmen användas för polynommultiplikation Alternativt kan Kronecker -substitutionstekniken användas för att konvertera problemet med att multiplicera polynom till en enda binär multiplikation.

Långa multiplikationsmetoder kan generaliseras för att möjliggöra multiplikation av algebraiska formler:

 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
 =======================================

Som ett ytterligare exempel på kolumn baserad multiplikation, överväga att multiplicera 23 långa ton (t), 12 hundred (CWT) och 2 fjärde (qtr) genom 47. I detta exempel används avoirdupois åtgärder: 1 t = 20 cwt, en 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

Multiplicera först kvartalen med 47, resultatet 94 skrivs in i den första arbetsytan. Multiplicera därefter cwt 12*47 = (2 + 10)*47 men lägg inte ihop delresultaten (94, 470) än. På samma sätt multiplicera 23 med 47 ger (141, 940). Kvartalkolumnen summeras och resultatet placeras i den andra arbetsytan (ett trivialt drag i det här fallet). 94 kvartal är 23 cwt och 2 qtr, så placera 2: an i svaret och lägg 23 i nästa kolumn till vänster. Lägg nu ihop de tre posterna i cwt -kolumnen som ger 587. Detta är 29 t 7 cwt, så skriv 7: an i svaret och 29 i kolumnen till vänster. Lägg nu till tonkolumnen. Det finns ingen justering att göra, så resultatet kopieras bara ner.

Samma layout och metoder kan användas för alla traditionella mått och icke-decimala valutor som det gamla brittiska £ sd- systemet.

Se även

• Binär multiplikator
• Division algoritm
• Logaritm
• Mental beräkning
• Prosthaphaeresis
• Räknesticka
• Trachtenberg -system
• Horner -schema för utvärdering av ett polynom
• Restnummernummer § Multiplikation för en annan snabb multiplikationsalgoritm, särskilt effektiv när många operationer utförs i sekvens, till exempel i linjär algebra
• Dadda multiplikator
• Wallace träd

Referenser

Vidare läsning

• Warren Jr., Henry S. (2013). Hacker's Delight (2 utg.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
• Savard, John JG (2018) [2006]. "Avancerade aritmetiska tekniker" . quadibloc . Arkiverad från originalet 2018-07-03 . Hämtad 2018-07-16 .
• Johansson, Kenny. Low Power och Low Complexity Shift-and-Add Based Computations (PDF) (avhandling). Linköpings studier i vetenskap och teknik (1 red.). Linköping, Sverige: Institutionen för elektroteknik, Linköpings universitet . ISBN 978-91-7393-836-5. ISSN  0345-7524 . Nr 1201. Arkiverad (PDF) från originalet 2017-08-13 . Hämtad 2021-08-23 . (x+268 sidor)

externa länkar

Grundläggande aritmetik

• Aritmetikens många sätt i UCSMP Everyday Mathematics
• En Powerpoint -presentation om antik matematik
• Gittermultiplikation Flash Video

Avancerade algoritmer

• Multiplikationsalgoritmer som används av GMP