Joris van der Hoeven

CNRS

Day 2 (Wednesday April 20) @ 10:00 – 11:00 N.G. de Bruijn prize winner

Fast integer multiplication

(Joint work with David Harvey)

Integer multiplication is one of the oldest mathematical operations and still a central problem for computer arithmetic.  The complexities of many other basic operations such as division, base conversion, gcds, computing e and pi, FFTs, etc. can be expressed in terms of the complexity of integer multiplication.  In our talk, we will survey a new algorithm for multiplying two n-digit integers in time O(n log n).