Schönhagen–Strassenin algoritmi

Kohteesta Wikipedia
Siirry navigaatioon Siirry hakuun

Matematiikassa Schönhagen–Strassenin algoritmi on 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ähteet[muokkaa | muokkaa wikitekstiä]