# CARMA Colloquium

## 4:00 pm

## Thursday, 23^{rd} 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.