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.

Calendar (ICS file) download, for import into your favourite calendar application

UNCLUTTER for printing

AUTHENTICATE to mark the scnews item as read