SMS scnews item created by Leo Tzou at Tue 30 Apr 2019 1148
Type: Seminar
Distribution: World
Expiry: 30 Oct 2019
Calendar1: 7 May 2019 1200-1300
CalLoc1: UNSW Red Centre 4082
CalTitle1: Integer multiplication in time O(n log n)
Auth: leo@1.157.197.244 (ltzo2369) in SMS-LDAP

Joint Colloquium: David Harvey -- 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(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.


If you are registered you may mark the scnews item as read.
School members may try to .