jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.92k stars 1.02k forks source link

Reference Harvey and Van Der Hoeven's multiplication algorithm #123

Closed jeffgerickson closed 5 years ago

jeffgerickson commented 5 years ago

Update references to the fastest known integer multiplication algorithm to David Harvey and Joris Van Der Hoeven's O(n log n)-time algorithm, discovered in 2019:

jeffgerickson commented 5 years ago

Note that this result almost closes the complexity of integer multiplication, thanks to another recent result by Peyman Afshani andcoauthors, relating multiplication to network coding.

https://arxiv.org/abs/1902.10935

So it's not clear if I should continue describing the complexity of integer multiplication as an open problem. Yes, it is still an open problem, but it's arguably not an algorithmic open problem any more.

jeffgerickson commented 5 years ago

Done. Removed discussion of iterated logs. No longer describe integer multiplication as an open problem.