Hacking Multiplication med Karatsuba’s algoritme

Folk har tendens til at besætte over at lave computersoftwareapplikation hurtigere. Du kan selvfølgelig bare vride klokkeslættet såvel som tilføj flere processorer, men ofte er den mest kraftfulde metode til at gøre noget hurtigere at opdage en meget bedre metode til at gøre det. Nogle gange er disse teknikker ekstremt forskellige fra præcis, hvordan et menneske ville gøre den nøjagtige samme opgave, men det passer til computerens evner. [Nemean] har en video, der forklarer en meget bedre multiplikationsalgoritme, der forstod, som Karatsubas algoritme såvel som det er virkelig temmelig klogt. Du kan se videoen nedenfor.

For at hjælpe dig med at forstå algoritmen, viser videoen et simpelt tocifret med tocifret multiplikation. Du kan se, at de allerførste såvel som sidste cifre er i det væsentlige resultatet af en multiplikation. Det er alle de mellemliggende cifre, der tilføjer sammen. Det eneste, der kan modificere det allerførste ciffer, er en bære.

Ved hjælp af Clever Math kan du beregne det allerførste såvel som sidste ciffer sammen med en sum, der indeholder de mellemdele, der er tilføjet til de allerførste såvel som sidste cifre. Ved at subtrahere dem ud, kan du få alle de nødvendige cifre ved hjælp af færre multiplikationer end den traditionelle metode. Tilføjelse såvel som subtraktion er generelt billigt, så handel med multiplikationer kan resultere i større tidsbesparelser.

Selvfølgelig sker i disse dage, at din multiplikation sandsynligvis forekommer i hardware, men det kan stadig ikke være så hurtigt som tilsætning såvel som subtraktion. Kompleksiteten af ​​denne algoritme betyder dog, at den ikke ofte udnyttes, medmindre du har at gøre med ekstremt store tal. Uanset hvad er det en smart anvendelse af matematik såvel som disproved, hvad “alle” forstod – at den allerbedste teknik allerede var fundet. Det gør dig spørgsmål til, hvor mange andre forstået ting vil blive disproven i fremtiden.

Vi tænker altid på mærkelige matematiske metoder. Et par af dem er temmelig farverige.