Schönhagen–Strassenin algoritmi

Wikipediasta
Siirry navigaatioon Siirry hakuun

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ähteet

[muokkaa | muokkaa wikitekstiä]
Noudettu kohteesta ”https://fi.wikipedia.org/w/index.php?title=Schönhagen–Strassenin_algoritmi&oldid=18685281”