Korrutamisalgoritmidega

Korrutamisalgoritmid on arvutiteaduses ja matemaatikas meetodid suurte arvude või polünoomide korrutamise efektiivseks teostamiseks. Traditsioonilised algoritm, nagu näiteks paberil ja pliiatsiga tehtav algoritm, on aeglased, kui tegemist on väga suurte arvudega, kuna nende tööaeg kasvab ruuduga sisendandmete numbri pikkusest. Seetõttu on välja töötatud mitmeid kiiremaid korrutamisalgoritme.

Üks esimesi efektiivseid algoritme oli Karatsuba algoritm, mis vähendab vajalike üksikute korrutuste arvu võrreldes traditsioonilise meetodiga. See saavutatakse rekursiivse jagamise ja valitsemise strateegia abil. Kuigi Karatsuba algoritm on kiiremini kui traditsiooniline meetod, on sellelgi oma piirangud.

Veelgi kiiremaid tulemusi pakuvad algoritmid, mis põhinevad kiirel Fourier' teisendusel (FFT). Nende hulka kuuluvad Schönhage-Strassen algoritm ja Füreri algoritm. Need meetodid kasutavad polünoomide korrutamist tsükliliste polünoomide korrutamiseks FFT abil, mis on oluliselt kiirem suuremate andmemahtude korral. FFT-põhised algoritmid on eriti olulised krüptograafias ja numbriväljade teoorias, kus töötatakse pidevalt väga suurte arvudega. Valitud algoritm sõltub sageli korrutatavate arvude suurusest ja soovitud jõudlusest.