Karatsuba: Stora siffror multiplicera snabbare

Stenulf Nordlund April 23, 2016 Vetenskap 5 0
FONT SIZE:
fontsize_dec
fontsize_inc
Karatsuba är namnet på en snabb multiplikation algoritm. Den är uppkallad efter upptäckaren Alexeevitch Anatolii Karatsuba 1960. Algoritmen är ett relativt enkelt sätt att föröka stort antal effektivt med varandra, än i det vanliga sättet. Vi får se hur denna algoritm. Innan vi dyker in arbetet i algoritmen, är det bra att först titta på tillämpningen och användningen av denna algoritm. Multiplikation är en grundläggande färdighet som vi alla lärt oss i skolan och denna metod är tillämplig på alla nummer, oavsett storlek.

Multiplicera med datorn

Om vi ​​multiplicerar nu siffror tillsammans, greppa vi oftast en miniräknare, dator eller smartphone på. Speciellt när siffrorna är större än två eller tre siffror och vi behöver ett exakt resultat. Processorerna i våra enheter kan utföra sådana beräkningar mycket snabbt. Men det finns gränser för vad en dator kan beräkna standard.

64-bitars kontra 32-bitars: Windows kalkylator

Ovannämnda gränser är mycket tydlig med ett enkelt experiment med Windows kalkylator. Detta kräver både en 32-bitars Windows kräver 64-bitars Windows-dator. På en 32-bitarssystem är 2147483647, det högsta värdet som räknaren kan hantera. Så om du försöker utföra en multiplikation där resultatet är större än detta värde, kommer räknaren inte räkna. Exempelvis en x 2.000.000 miljoner. Det korrekta resultatet är 2 biljoner, är att en andra med 12 nollor.
Vi ger denna summa till räknaren på en 64-bitars Windows-system, kommer det förmodligen att beräkna denna summa. Den 64-bitars maximala värdet då 9.223.372.036.854.775.807, eller en 9 av 18 nollor. Anledningen är vidare utforskas Vad är fördelen med 64-bitars?

Stora siffror

Men just nu finns det ett behov av att ta itu med mycket större siffror, så kommer det också att vara en 64-bitars Windows kalkylator är otillräckliga. Dessa typer av siffror används till exempel i matematik, kosmologi och kryptografi. Ett exempel är sökandet efter primtal. Det största primtal hittat hittills är 17,425,170 siffror. För att hitta måste ett sådant antal att kunna vara så att det numrerade med siffror i den storleksordning. För att kunna göra detta måste särskild programvara som skall skrivas, för att arbeta med den här typen av stora tal. I korthet innebär det att antalet bör skäras i mindre bitar som är kapabel att hantera en dator. Detta innebär att bör utföras i antalet hundratals eller tusentals figurer det finns många enkla multiplikationer. Efter att alla dessa resultat kombineras igen och läggs samman för att få rätt resultat. Eller utför multiplikationer av denna kaliber tar betydande tid, eftersom det finns så många. Och på så sätt snabbare alternativa algoritmer plötsligt intressant.

Multiplicera Standard

Det är inte bekvämt här för att arbeta med stora mängder, men lyckligtvis kan vi också förklara principen med mindre värden. Först kommer vi att multiplicera det vanliga sättet, har vi lärt oss i skolan.
Vi tar summan av 67 x 85. Resultatet är för övrigt 5695. För att förklara den princip som vi låtsas att vi kan räkna upp av enskilda siffror och resultatet är upp kommer att bestå av två siffror.
0067
0085 *
--------
0035 → 5 x 7
0300 → lägga 0; sedan fem gånger sex
0560 → lägga 0; sedan 8 gånger 7
4800 → lägga 0; 0 Lägg till och sedan åtta gånger sex
---------
5695 → senaste fyra resultat räknas
Vad vi har här är gjort fyra gånger multiplikator, då en summa. På multiplikationerna vi omedelbart lägga till extra nollor när siffrorna är faktiskt ett dussin. Finns det talade om hundratals eller tusentals, då kommer vi att lägga till fler nollor.

Karatsuba

Den Karatsuba algoritmen skär de två första siffrorna i bitar. Med dessa bitar räknas på ett smart sätt och sedan hela kombineras i det slutliga resultatet. Detta sker på följande sätt:
De två ingångs siffrorna delas upp i en hög och en låg del:
  • invoer1 = 67 L1 = 7 H1 = 6
  • invoer2 = 85: L2 = 5, H 2 = 8

Då kan vi ta dessa siffror för att beräkna tre mellanresultat:
  • Z0 = L1 L2 *
  • = Z1 *
  • Z2 = H1 * H2
Så i vårt fall:
  • Z0 = 7 * 5 = 35
  • Z1 = * = 13 * 13 = 169
  • Z2 = 6 * 8 = 48

Med dessa tre resultat beräknar vi följande delresultat:
  • Y = Z1 -
Så:
  • Y = 169 - = 169-83 = 86

Allt som återstår nu är att slå samman resultaten Z0, Z2 och Y till resultatet. Som går med följande formel:
  • Resultat = Z2 * 10 ^ 10 ^ * P + Y + Z 1

Denna formel ser komplicerat men är faktiskt väldigt enkelt. Det viktiga är att de tre mellanresultat är inte alla lika "tunga" kan räknas. Det är som i vår ursprungliga metod där vi nollor, aktiveras när en
nummer är ett dussin eller två nollor om båda siffrorna är ett dussin. Detsamma gäller för Karatsuba. Sättet att göra det är följande: Bestäm vilken numret är den största av de inmatade siffror, och skapa P lika med antalet siffror där den siffran består av. I vårt fall är 85 den största, och 85 består av två siffror, så P är lika med två.
Ser man tillbaka till det sista formel vi ser det Z2 måste multipliceras med 10 upphöjt till P och Y måste multipliceras med 10 upphöjt. Eftersom P är lika med 2, betyder det inte mer än som tar emot två nollor Z 2 och Y är en nolla. Så:
  • Resultat = 48 * 10 ^ 2 + 86 * 10 ^ + 35 = 48 * 100 + 86 * 10 + 35 = 4800 + 860 + 35 = 5695
Och vi ser att vi får samma resultat.

Varför är så mycket snabbare med denna extra börda?

Ofta den första reaktionen på ser Karatsuba algoritmen att den aldrig kan vara snabbare än standard multiplikation, men det är så.
Om vi ​​spåra våra steg genomförts ser vi i vår ursprungliga metod fyra multiplikationer och en summa av fyra siffror. Men vid Karatsuba bara tre multiplikationer behövs. Dessutom finns det två plus-operationer som krävs för beräkning av Z 1 och ett plus och ett minus funktion för att bestämma Y. tiopotenser beräkna för Z2 och Y inte är riktiga beräkningar, utan helt enkelt lägga till ett antal nollor. Slutligen bör då fortfarande plus två operationer utförs. Resultatet är en följd av förlusten av att en multiplikation. För även om vi får ett par plus / minus operationer i gengäld; en multiplikation tar så mycket mer processor tid att utföra, är det fortfarande på det hela taget, snabbare.

Storlek på siffrorna

Som nämnts Karatsuba är bara effektivt om siffror får en viss storlek. Hur mycket mer effektiv än är exakta, beror på hur Karatsuba algoritmen och standardalgoritmen implementeras. Med antagande av att båda algoritmerna har optimerats på ett liknande sätt, är i allmänhet sant att de inmatade numren är redan åtminstone 320 bitar måste vara stora. Det är ungefär 96 siffror långa på vanligt decimalsystemet, så ett stort antal. Men i jämförelse med primtal miljoner siffror långa, är 96 siffror ännu inte så stor. Och så hastigheten förstärkningen kommer att vara ännu större antal kommer bara att öka om det räknas med Karatsuba metoden.
  Like 0   Dislike 0
Kommentarer (0)
Inga kommentarer

Lägg till en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tecken kvar: 3000
captcha