David Harvey's algorithm multiplies integers faster than all previous algorithms

Date: 

Monday, 8th April 2019


David Harvey

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.

The paper has attracted a wide range of media attention. 

David's page on the paper 

UNSW newsroom announcement