Type: Seminar

Distribution: World

Expiry: 30 Oct 2019

CalTitle1: Integer multiplication in time O(n log n)

Auth: leo@1.157.197.244 (ltzo2369) in SMS-LDAP

Joris van der Hoeven and I recently discovered an algorithm that computes the product of two n-bit integers in O(nlogn) 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 ofinteger multiplication, and give an overview of the new algorithm. No previous background on multiplication algorithms will be assumed.