Fürer's algorithm

Fürer's algorithm is an integer multiplication algorithm for quite large integers possessing a very low asymptotic complexity which can be also optimized by using the inverse Ackermann function instead of the iterated logarithm.

This algorithm was published in 2007 by the Swiss mathematician Martin Fürer of Pennsylvania State University as an asymptotically faster algorithm when analysed on a multitape Turing machine than its predecessor the famous Schönhage-Strassen algorithm.

Schönhage-Strassen's algorithm uses Fast Fourier Transform (FFT) to compute integer products in time O ( n log ⁡ n log ⁡ log ⁡ n ) and its authors Arnold Schönhage and Volker Strassen conjecture a lower bound of Ω ( n log ⁡ n ) .

Fürer's algorithm reduces the gap between these two bounds.

It can be used to multiply integers of length n in time n log ⁡ n 2 O ( log ∗ ⁡ n ) where log*n stands for the iterated logarithm.

The difference between the terms log ⁡ log ⁡ n and 2 log ∗ ⁡ n from a complexity point of view is asymptotically in the advantage of Fürer's algorithm which is only efficient for huge integers starting from 2 2 64 .

However the difference between the log ⁡ log ⁡ n and 2 log ∗ ⁡ n factors in the time bounds of Schönhage-Strassen's algorithm and Fürer's algorithm for realistic values of n is very small.

Meanwhile, in 1976 Luigi Dadda already proposed a parallel implementation of the multiplication operator.

In 1983 « the pilgrim fathers » Aho, Hopcroft and Ullmann focused on this topic from an algorithmic point of view.

Jean Vuillemin designed during the same year a very quick algorithm for the multiplication operator and its application to VLSI architectures.

In the 90's Barry Fagin published different algorithms for long integer multiplication within the sequential and parallel frameworks, the first being based on Fermat's number transform.

In 1993 and 1994 Dan Zuras published two complementary papers related to quick multiplication of long integers.

In 1996 Benjamin Singer and George Saon proposed a parallel algorithm for integer multiplication.

In 2003 Viktor Bunimov and Manfred Schimmler published two algorithms, one sequential and one parallel, to compute respectively the modular product and the parallel product of very long integers.

In 2008 De gave a similar algorithm which relies on modular arithmetic instead of complex arithmetic to achieve in fact the same running time.

In 2013 Bantikyan proposed a fast integer multiplication algorithm based on FFT and dedicated to CUDA architectures.

In 2015 Harvey proved that their optimized version of Fürer's algorithm achieves a running time of O ( n log ⁡ n 2 3 log ∗ ⁡ n ) making explicit the implied constant in the O ( log ∗ ⁡ n ) exponent.

He also proposed a modification to Fürer's algorithm which achieves O ( n log ⁡ n 2 2 log ∗ ⁡ n ) but whose validity relies on standard conjectures about the distribution of Mersenne primes.

In 2015 Covanov and Thomé provided another modification of Fürer's algorithm which achieves the same running time.

Nevertheless, it remains just as impractical as all the other implementations of this algorithm.

In 2016 Covanov and Thomé proposed an original multiplication algorithm of long integers based on the generalization of Fermat primes.