Schönhagen–Strassenin algoritmi

Schönhagen–Strassenin algoritmi on matematiikassa asymptoottisesti nopea menetelmä suurten kokonaislukujen kertolaskuun. Sen kehittivät Arnold Schönhage (s. 1934) ja Volker Strassen (s. 1936). Algoritmin asymptoottinen suoritusaika on O(N log N log log N). Algoritmi käyttää nopeaa Fourier'n muunnosta ja algebrasta tuttuja renkaita.

LähteetMuokkaa