Schonhage–Strassen algorithm

views updated

Schonhage–Strassen algorithm A development of the Strassen algorithm that was published in 1970 and avoids the explicit use of complex numbers. It multiplies two n-bit numbers in steps of O(nlogn loglogn)