Vi har fundet en hurtigere måde at gange virkelig store tal på

Multiplikation af to tal er let, ret?

I folkeskolen lærer vi at lave lang multiplikation sådan her:

Metoder, der ligner denne, går tusinder af år tilbage, i hvert fald for de gamle sumerere og egyptere.

Men er dette virkelig den bedste måde at gange to store tal sammen?

I lang multiplikation, vi skal gange hvert ciffer i det første tal med hvert ciffer i det andet tal. Hvis de to tal hver har N cifre, det er N ² (eller N x N ) multiplikationer helt. I eksemplet ovenfor, N er 3, og vi skulle lave 3 ² =9 multiplikationer.

Omkring 1956, den berømte sovjetiske matematiker Andrey Kolmogorov formodede, at dette er bedst mulige måde at gange to tal sammen.

Med andre ord, uanset hvordan du arrangerer dine beregninger, mængden af ​​arbejde, du skal udføre, vil være proportional med mindst N ² . Dobbelt så mange cifre betyder fire gange så meget arbejde.

Kolmogorov mente, at hvis en genvej var mulig, det ville sikkert allerede være blevet opdaget. Trods alt, mennesker har ganget tal i tusinder af år.

Dette er et fremragende eksempel på den logiske fejlslutning kendt som "argumentet fra uvidenhed".

En hurtigere måde

Blot et par år senere, Kolmogorovs formodning viste sig at være spektakulært forkert.

I 1960, Anatoly Karatsuba, en 23-årig matematikstuderende i Rusland, opdagede et lusket algebraisk trick, der reducerer antallet af nødvendige multiplikationer.

For eksempel, at gange firecifrede tal, i stedet for at have brug for 4 ² =16 gange, Karatsubas metode slipper med kun ni. Når han bruger hans metode, dobbelt så mange cifre betyder kun tre gange så meget arbejde.

Dette giver en imponerende fordel, efterhånden som tallene bliver større. For tal med tusinde cifre, Karatsubas metode har brug for omkring 17 gange færre gange end lang multiplikation.

Men hvorfor i alverden skulle nogen ønske at gange så store tal sammen?

Faktisk, der er et enormt antal ansøgninger. En af de mest synlige og økonomisk betydningsfulde er inden for kryptografi.

Store tal i det virkelige liv

Hver gang du engagerer dig i krypteret kommunikation på internettet – f.eks. få adgang til dit bankwebsted eller foretag en websøgning – din enhed udfører et stort antal multiplikationer, involverer tal med hundreder eller endda tusindvis af cifre.

Meget sandsynligt bruger din enhed Karatsubas trick til denne aritmetik. Dette er alt sammen en del af det fantastiske software-økosystem, der holder vores websider indlæst så hurtigt som muligt.

For nogle mere esoteriske anvendelser, matematikere skal håndtere endnu større tal, med millioner, milliarder eller endda billioner af cifre. For så enorme tal, selv Karatsubas algoritme er for langsom.

Et reelt gennembrud kom i 1971 med de tyske matematikere Arnold Schönhages og Volker Strassens arbejde. De forklarede, hvordan man bruger den nyligt offentliggjorte hurtige Fourier-transformation (FFT) til at multiplicere enorme tal effektivt. Deres metode bruges rutinemæssigt af matematikere i dag til at håndtere tal i milliarder af cifre.

FFT er en af ​​de vigtigste algoritmer i det 20. århundrede. En applikation, der er kendt i dagligdagen, er digital lyd:når du lytter til MP3'er, musikstreamingtjenester eller digital radio, FFT'er håndterer lydafkodningen bag kulisserne.

En endnu hurtigere måde?

I deres papir fra 1971, Schönhage og Strassen fremsatte også en slående formodning. At forklare, Jeg bliver nødt til at blive lidt teknisk et øjeblik.

Den første halvdel af deres formodning er, at det skal være muligt at multiplicere N -cifrede tal ved hjælp af et antal grundlæggende operationer, der er proportional med højst N log ( N ) (det er N gange den naturlige logaritme af N ).

Deres egen algoritme nåede ikke helt dette mål; de var for langsomme med en faktor log (log N ) (logaritmen af ​​logaritmen af N ). Alligevel, deres intuition fik dem til at mistænke, at de manglede noget, og det N log ( N ) bør være mulig.

I årtierne siden 1971, nogle få forskere har fundet forbedringer af Schönhage og Strassens algoritme. Især en algoritme designet af Martin Fürer i 2007 kom pinefuldt tæt på det undvigende N log ( N ).

Den anden (og meget sværere) del af deres formodning er det N log ( N ) bør være den grundlæggende hastighedsgrænse - at ingen mulig multiplikationsalgoritme kunne gøre det bedre end dette.

Lyder det bekendt?

Har vi nået grænsen?

Et par uger siden, Joris van der Hoeven og jeg udsendte et forskningspapir, der beskrev en ny multiplikationsalgoritme, der endelig når N log ( N ) hellig gral, dermed afklarede den "lette" del af Schönhage-Strassen formodningen.

Papiret er endnu ikke blevet peer-reviewet, så en vis forsigtighed er berettiget. Det er standard praksis i matematik at formidle forskningsresultater, før de har gennemgået peer review.

I stedet for at bruge endimensionelle FFT'er - det vigtigste i alt arbejde med dette problem siden 1971 - er vores algoritme afhængig af flerdimensionelle FFT'er. Disse gadgets er ikke noget nyt:det meget udbredte JPEG-billedformat afhænger af 2-dimensionelle FFT'er, og 3-dimensionelle FFT'er har mange anvendelser inden for fysik og teknik.

I vores avis, vi bruger FFT'er med 1, 729 dimensioner. Det er svært at visualisere, men matematisk ikke mere besværligt end det 2-dimensionelle tilfælde.

Virkelig, virkelig store tal

Den nye algoritme er ikke rigtig praktisk i sin nuværende form, fordi beviset i vores papir kun virker for latterligt store tal. Selv hvis hvert ciffer blev skrevet på et brintatom, der ville ikke være nær nok plads til rådighed i det observerbare univers til at skrive dem ned.

På den anden side, vi håber, at med yderligere justeringer, Algoritmen kan blive praktisk for tal med kun milliarder eller billioner af cifre. Hvis så, det kan meget vel blive et uundværligt værktøj i beregningsmatematikerens arsenal.

Hvis den fulde Schönhage-Strassen-formodning er korrekt, fra et teoretisk synspunkt, den nye algoritme er vejens ende – det er ikke muligt at gøre det bedre.

Personligt, Jeg ville blive meget overrasket, hvis formodningen viste sig at være forkert. Men vi må ikke glemme, hvad der skete med Kolmogorov. Matematik kan nogle gange give overraskelser.

Denne artikel er genudgivet fra The Conversation under en Creative Commons -licens. Læs den originale artikel.