Schönhagen–Strassenin algoritmi

Wikipedia
Loikkaa: valikkoon, 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.

Viitteet[muokkaa | muokkaa wikitekstiä]