Hacker News Reader

Another wiki article says the fastest current algorithm involves a 1729-dimensional Fourier transform [1]. And now I need to know: what is the taxicab number [2] doing there???

EDIT: nevermind, it's just a coincidence... any number larger than 1728 would have worked according to the paper.

[1] https://en.m.wikipedia.org/wiki/Galactic_algorithm

[2] https://en.m.wikipedia.org/wiki/Taxicab_number

Specifically, the author has said that he thinks that the number could go down to ~8 but it would have made the paper another 50 pages.

Paper link? Was it this? https://web.archive.org/web/20130425232048/http://www.cse.ps...

Integer multiplication in time O(n log n): https://hal.archives-ouvertes.fr/hal-02070778/document

Found this link amusing (from the article):

https://en.m.wikipedia.org/wiki/Galactic_algorithm

First time I heard FFT was involved in multiplication I was as shocked as excited.

Yeah its interesting, multiplication is essentially a convolution of the digits in the two numbers, and convolution is definitely something that FFT is used for.

Schönhage–Strassen Algorithm