CARMA Colloquium

4:00 pm

Thursday, 23rd May 2019

LSTH, Life Sciences Lecture Theatre

A/Prof David Harvey

(University of NSW)

Integer multiplication in time $O(n \log n)$

Joris van der Hoeven and I recently discovered an algorithm that computes the product of two $n$-bit integers in $O(n \log n)$ bit operations. This is asymptotically faster than all previous known algorithms, and matches the complexity bound conjectured by Schönhage and Strassen in 1971. In this talk, I will discuss the history of integer multiplication, and give an overview of the new algorithm. No previous background on multiplication algorithms will be assumed.