Professor Martin Fürer Featured in the German Newspaper, Die Zeit

Professor Martin Fürer's fast integer multiplication algorithm and its predecessors were featured in the German Newpaper, Die Zeit.

Furer's algorithm created in 2007 is currently the asymptotically fastest integer multiplication algorithm. The previously fastest such algorithm by Arnold Schönhage and Volker Strassen has been published in 1971. It computes the product of two binary integers of length n in time O(n log n loglog n), while the authors conjectured a lower bound of order n log n. The running time of Fürer's algorithm is somewhere between these two bounds. These time bounds are so close together that it has not yet been determined for which lengths n the new algorithm can compete with its predecessor. Multiplications of integers whose lengths are in the millions are routinely done in primality testing and are needed for other number theoretic tasks.

Please click here to read the article on Zeit Online.