Graduate Student Seminar: How to multiply integers (fast), Speaker: Dan Fess

Graduate Student Seminars
  • Dan Fess
  • How to multiply integers (fast)
May 14, 2019
12:30 pm
Fine Hall 214

Title: How to multiply integers (fast)

Abstract: Multiplying two n-bit numbers naively takes time O(n^2).  Recently, Harvey & van der Hoeven developed an algorithm to do this in time O(n log(n)).  We will discuss a handful of algorithms for multiplying integers quickly, including the Karatsuba and Schoenhage-Strassen algorithms, building up to a rough overview of the method of Harvey & van der Hoeven.