For over 35 years, the fastest known method of computing the product of two integers has been the Schönhage-Strassen algorithm, until Fürer’s algorithm was created in 2007. Since then, however, no known implementations of Fürer’s algorithm have ever been created. In this thesis, an implementation of Fürer’s algorithm is presented, coded in Java, and analyzed. This implementation is then compared to an implementation of the Schönhage-Strassen algorithm to analyze the running speeds for increasing values of n, the length of the two integers to multiply in binary. For large enough n, Fürer’s algorithm is asymptotically faster than Schönhage-Strassen’s algorithm. The claim that an implementation of Fürer’s algorithm should then be faster for comparable n is investigated and conclusions are drawn about the practicality of Fürer’s algorithm in practice, using observations from the implementation.
