Karatsuba algoritm

Karatsuba multiplikation av az+b och cz+d (inramad) och 1234 och 567. Magentapilar betecknar multiplikation, bärnsten betecknar addition, silver betecknar subtraktion och ljuscyan betecknar vänsterförskjutning. (A), (B) och (C) visar rekursion som används för att erhålla mellanliggande värden.

Karatsuba -algoritmen är en snabb multiplikationsalgoritm . Det upptäcktes av Anatoly Karatsuba 1960 och publicerades 1962. Det är en dividera-och-härska-algoritm som reducerar multiplikationen av två n -siffriga tal till tre multiplikationer av n /2-siffriga tal och, genom att upprepa denna reduktion, till högst $n^{\log _{2}3}\approx n^{1,58}$ ensiffrig multiplikation. Den är därför asymptotiskt snabbare än den traditionella algoritmen, som utför $n^{2}$ ensiffriga produkter. Till exempel, för att multiplicera två 1024-siffriga tal ( n = 1024 = 2 ¹⁰ ), kräver den traditionella algoritmen (2 ¹⁰ ) ² = 1 048 576 ensiffriga multiplikationer, medan Karatsuba-algoritmen kräver 3 ¹⁰ = 59 049 gånger snabbare och därmed är den snabbare ~ 17,75 gånger snabbare. .

Karatsuba-algoritmen var den första multiplikationsalgoritmen som var asymptotiskt snabbare än den andragradsalgoritmen "begärda skola". Toom –Cook-algoritmen (1963) är en snabbare generalisering av Karatsubas metod, och Schönhage–Strassen-algoritmen (1971) är ännu snabbare, för tillräckligt stor n .

Historia

Standardproceduren för multiplikation av två n -siffriga tal kräver ett antal elementära operationer som är proportionella mot $n^{2}\,\!$ eller $O(n^{2 })\,\!$ i big-O notation . Andrey Kolmogorov förmodade att den traditionella algoritmen var asymptotiskt optimal , vilket betyder att vilken algoritm som helst för den uppgiften skulle kräva $\Omega (n^{2})\,\!$ elementära operationer.

1960 organiserade Kolmogorov ett seminarium om matematiska problem i cybernetik vid Moskvas statsuniversitet , där han angav $\Omega (n^{2})\,\!$ förmodan och andra problem i komplexitet i beräkningen . Inom en vecka hittade Karatsuba, då en 23-årig student, en algoritm som multiplicerar två n -siffriga tal i $O(n^{\log _{2}3} )$ elementära steg, vilket motbevisar gissningen. Kolmogorov var mycket exalterad över upptäckten; han meddelade det vid nästa möte i seminariet, som sedan avslutades. Kolmogorov höll några föreläsningar om Karatsuba-resultatet vid konferenser över hela världen (se t.ex. "Proceedings of the International Congress of Mathematicians 1962", s. 351–356, och även "6 föreläsningar levererade vid International Congress of Mathematicians i Stockholm, 1962") och publicerade metoden 1962, i Proceedings of the USSR Academy of Sciences . Artikeln hade skrivits av Kolmogorov och innehöll två resultat om multiplikation, Karatsubas algoritm och ett separat resultat av Yuri Ofman ; den listade "A. Karatsuba och Yu. Ofman" som författarna. Karatsuba blev medveten om tidningen först när han fick nytrycken från förlaget.

Algoritm

Grundläggande steg

Grundprincipen för Karatsubas algoritm är dividera-och-härska , med hjälp av en formel som gör att man kan beräkna produkten av två stora tal $x$ och $y$ med hjälp av tre multiplikationer av mindre tal, var och en med ca. hälften så många siffror som $x$ eller $y$ , plus några tillägg och siffror. Detta grundläggande steg är i själva verket en generalisering av en liknande komplex multiplikationsalgoritm , där den imaginära enheten i ersätts med en potens av basen .

Låt $x$ och $y$ representeras som $n$ -siffriga strängar i någon bas $B$ . För varje positivt heltal $m$ mindre än $n$ , kan man skriva de två givna talen som

$x=x_{1}B^{m}+x_{0},$

$y=y_{1}B^ {m}+y_{0},$

där $x_{0}$ och $y_{0}$ är mindre än $B^{m}$ . Produkten är då

${\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\ \&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0} \\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}$

var

$z_{2}=x_{1}y_{1},$

$z_{1}=x_{1}y_ {0}+x_{0}y_{1},$

$z_{0}=x_{0}y_{0}.$

Dessa formler kräver fyra multiplikationer och var kända för Charles Babbage . Karatsuba observerade att $xy$ kan beräknas i endast tre multiplikationer, till priset av några extra tillägg. Med $z_{0}$ och $z_{2}$ som tidigare kan man observera att

${\begin{aligned}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{0}+x_{0}y_ {1}+x_{1}y_{1}-x_{1}y_{1}+x_{0}y_{0}-x_{0}y_{0}\\&=x_{1}y_{0 }+x_{0}y_{0}+x_{0}y_{1}+x_{1}y_{1}-x_{1}y_{1}-x_{0}y_{0}\\&= (x_{1}+x_{0})y_{0}+(x_{0}+x_{1})y_{1}-x_{1}y_{1}-x_{0}y_{0}\ \&=(x_{1}+x_{0})(y_{0}+y_{1})-x_{1}y_{1}-x_{0}y_{0}\\&=(x_{ 1}+x_{0})(y_{1}+y_{0})-z_{2}-z_{0}.\\\end{aligned}}$

Exempel

För att beräkna produkten av 12345 och 6789, där B = 10, välj m = 3. Vi använder m högerskift för att dekomponera ingångsoperanderna med den resulterande basen ( B ^m = 1000 ), som:

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

Endast tre multiplikationer, som fungerar på mindre heltal, används för att beräkna tre delresultat:

z ₂ = 12 × 6 = 72

₀ z = 345 × 789 = 272205

₀ z ₁ = ( 12 + 345 ) × ( 6 + 789 ) − z ₂ − z = 357 × 795 − 72 − 272205 = 5 − 1 205 = 5 −1 289

Vi får resultatet genom att bara lägga till dessa tre delresultat, skiftade därefter (och sedan ta hänsyn till dessa tre indata i bas 1000 som för ingångsoperanderna):

₀⁰ resultat = z ₂ · ( B ^m ) ² + z ₁ · ( B ^m ) ¹ + z · ( B ^m ) , dvs

resultat = 72 · 1000 ² + 11538 · 1000 + 272205 = 83810205 .

Observera att den mellanliggande tredje multiplikationen fungerar på en ingångsdomän som är mindre än två gånger större än för de två första multiplikationerna, dess utdatadomän är mindre än fyra gånger större och bas-1000 bäringar beräknade från de två första multiplikationerna måste tas med i när du beräknar dessa två subtraktioner.

Rekursiv applikation

Om n är fyra eller fler, involverar de tre multiplikationerna i Karatsubas grundläggande steg operander med färre än n siffror. Därför kan dessa produkter beräknas genom rekursiva anrop från Karatsuba-algoritmen. Rekursionen kan tillämpas tills talen är så små att de kan (eller måste) beräknas direkt.

₀₀ I en dator med en full 32-bitars med 32-bitars multiplikator , till exempel, skulle man kunna välja B = 2 ³¹ och lagra varje siffra som ett separat 32-bitars binärt ord. Då behöver summorna x ₁ + x och y ₁ + y inte ett extra binärt ord för att lagra den överförda siffran (som i carry-save adder ) , och Karatsuba-rekursionen kan tillämpas tills talen som ska multipliceras bara är ett siffra lång.

Tidskomplexitetsanalys _

Karatsubas grundsteg fungerar för vilken bas B som helst och vilken m som helst , men den rekursiva algoritmen är mest effektiv när m är lika med n /2, avrundat uppåt. I synnerhet, om n är 2 ^k , för något heltal k , ^och rekursionen slutar endast när n är 1, då är antalet ensiffriga multiplikationer 3 ^k , vilket är nc där c = log ₂ 3.

Eftersom man kan utöka vilken inmatning som helst med nollsiffror tills deras längd är en potens av två, följer det att antalet elementära multiplikationer, för varje n , är högst ${\ displaystyle 3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!}$ .

Eftersom additionerna, subtraktionerna och sifferförskjutningarna (multiplikationer med potenser av B ) i Karatsubas grundläggande steg tar tid proportionellt mot n , blir deras kostnad försumbar när n ökar. Mer exakt, om t ( n ) anger det totala antalet elementära operationer som algoritmen utför när två n -siffriga tal multipliceras

$T(n)=3T(\lceil n/2\rceil )+cn+d$

för vissa konstanter c och d . För denna upprepningsrelation ger huvudsatsen för dela-och-härska-recidiv den asymptotiska gränsen $T(n)=\Theta (n^{\log _{ 2}3})\,\!$ .

Det följer att för tillräckligt stort n kommer Karatsubas algoritm att utföra färre skift och enkelsiffriga additioner än långhandsmultiplikation, även om dess grundläggande steg använder fler additioner och skiftningar än den enkla formeln. För små värden på n kan dock de extra skift- och add-operationerna göra att den går långsammare än långhandsmetoden. Poängen för positiv avkastning beror på datorplattformen och sammanhanget. Som en tumregel är Karatsubas metod vanligtvis snabbare när multiplikanterna är längre än 320–640 bitar.

Genomförande

Här är pseudokoden för denna algoritm, med siffror representerade i bas tio. För den binära representationen av heltal räcker det att ersätta 10 överallt med 2.

Det andra argumentet för split_at-funktionen anger antalet siffror som ska extraheras från höger : till exempel kommer split_at("12345", 3) att extrahera de 3 sista siffrorna, vilket ger: high="12", low="345".

  
           
            
    
    
       
         
    
    
    
        
        
    
    
       
           
       
    
                        funktion  karatsuba  (  num1  ,  num2  )  if  (  num1  <  10  eller  num2  <  10  )  returnera  num1  ×  num2  /* falla tillbaka till traditionell multiplikation */  /* Beräknar storleken på talen. */   m  =  max  (  size_base10  (  num1  ),  size_base10  (  num2  ))  m2  =  golv  (  m  /  2  )  /* m2 = ceil (m / 2) kommer också att fungera */  /* Dela siffersekvenserna på mitten. */   high1  ,  low1  =  split_at  (  num1  ,  m2  )  high2  ,  low2  =  split_at  (  num2  ,  m2  )  /* 3 rekursiva anrop till nummer som är ungefär hälften så stora. */   z0  =  karatsuba  (  låg1  ,  låg2  )  z1  =  karatsuba  (  låg1  +  hög1  ,  låg2  +  hög2  )  z2  =  karatsuba  (  hög1  ,  hög2  )  retur  (  z2  ×  10  ^  (  m2  ×  2  ))  +  ((  z1  -  z2  -  z0)  )  ×  10  ^  m2  )  +  z0 

Ett problem som uppstår vid implementering är att ovanstående beräkning av $(x_{1}+x_{0})$ och $(y_{1}+y_ {0})$ för $z_{1}$ kan resultera i spill (kommer att ge ett resultat i intervallet $B^{m}\leq {\text{ result}}<2B^{m}$ ), som kräver en multiplikator med en extra bit. Detta kan undvikas genom att notera det

$z_{1}=(x_{0}-x_{1})(y_{1}-y_{0})+z_{2}+z_{0}.$

Denna beräkning av $(x_{0}-x_{1})$ och $(y_{1}-y_{0})$ ger ett resultat i intervallet $-B^{m}<{\text{result}}<B^{m}$ . Denna metod kan producera negativa tal, som kräver en extra bit för att koda tecken, och fortfarande skulle kräva en extra bit för multiplikatorn. Ett sätt att undvika detta är dock att registrera tecknet och sedan använda det absoluta värdet av $(x_{0}-x_{1})$ och $(y_{1}-y_{0})$ för att utföra en multiplikation utan tecken, varefter resultatet kan negeras när båda tecknen ursprungligen skilde sig åt. En annan fördel är att även om $(x_{0}-x_{1})(y_{1}-y_{0})$ kan vara negativ, så beräkning av $z_{1}$ involverar endast tillägg.

externa länkar

• Karatsubas algoritm för polynom multiplikation
• Weisstein, Eric W. "Karatsuba Multiplication" . MathWorld .
• Bernstein, DJ, " Mångsiffrig multiplikation för matematiker ". Täcker Karatsuba och många andra multiplikationsalgoritmer.