Hacking multiplikasjon med Karatsubas algoritme

folk har en tendens til å obsessere over å gjøre dataprogramvare programmet raskere. Du kan selvsagt bare vri opp klokkehastigheten, samt legge til flere prosessorer, men ofte den kraftigste metoden for å gjøre noe raskere, er å oppdage en mye bedre metode for å gjøre det. Noen ganger er disse teknikkene ekstremt forskjellige fra nøyaktig hvordan et menneske ville gjøre nøyaktig samme oppgave, men det passer til datamaskinens evner. [Nemean] har en video som forklarer en mye bedre multiplikasjonsalgoritme forstått som Karatsubas algoritme, så vel som det er egentlig ganske smart. Du kan se videoen nedenfor.

For å hjelpe deg med å forstå algoritmen, viser videoen et enkelt tosifret med tosifret multiplikasjon. Du kan se at de aller første så vel som siste siffer er i hovedsak resultatet av en multiplikasjon. Det er alle mellomliggende siffer som legger sammen. Det eneste som kan modifiseres det aller første sifferet er en bære.

Ved hjelp av smart matte, kan du beregne det aller første, så vel som siste siffer, sammen med en sum som inneholder de midterste delene som er lagt til de aller første, så vel som siste siffer. Ved å subtrahere dem ut, kan du få alle nødvendige sifrene som bruker færre multiplikasjoner enn den tradisjonelle metoden. Legge til så vel som subtraherer er generelt billig, så handel med dem for multiplikasjoner kan resultere i store tidsbesparelser.

Selvfølgelig, i disse dager, skjer multiplikasjonen mest sannsynlig i maskinvare, men det kan fortsatt ikke være så raskt som tillegg og subtraksjon. Kompleksiteten til denne algoritmen, men betyr at den ikke ofte benyttes, med mindre du har å gjøre med ekstremt store tall. Uansett er det en smart anvendelse av matte, så vel som deproset hva “alle” forstod – at den aller beste teknikken allerede hadde blitt funnet. Det gjør deg spørsmålet nøyaktig hvor mange andre forstått ting vil bli disproven i fremtiden.

Vi tenker alltid på merkelige matte metoder. Noen av dem er ganske fargerike.