David Harvey's algorithm multiplies integers faster than all previous algorithms
Published on the 08 Apr 2019
A/Prof. David Harvey and his collaborator Joris van der Hoeven have posted a HAL preprint that describes a new algorithm for multiplication of two $n$-bit integers in $O(n \log n)$ time.
This surpasses the previously known complexity bounds in efficiency, confirming the 48-year-old conjecture of Schönhage and Strassen.
About the result
The problem is to find the fastest algorithm for multiplying two n-digit numbers, in the limit of large n. The naive algorithm learned in primary school has complexity O(n2 ). This was improved during the 1960s, culminating with the famous Schönhage-Strassen algorithm of Schönhage and Strassen from 1971, which realised the bound O(n log n log log n).
They also conjected that the best possible complexity bound for multiplication should be O(n log n). Between 2007 and 2016, progress was made on this conjecture, with a 2016 result of Harvey with Hoeven and Lecerf the state of the art at that time.
In March 2019, Harvey and van der Hoeven announced a new multiplication algorithm achieving the conjectured O(n log n) upper bound, thus settling this part of the almost 50-year-old Schönhage-Strassen conjecture. This remarkable result attracted considerable media attention, with news reports, interviews and articles appearing in mainstream outlets such as New Scientist, BBC World Service, The Australian, Le Monde, Quanta magazine and Triple J.