4 ms·

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

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 https://en.m.wikipedia.org/wiki/Galactic_algorithm [2] https://en.m.wikipedia.org/wiki/Taxicab_number https://en.m.wikipedia.org/wiki/Taxicab_number

psi75 4y ago
adgjlsfhk1 4y ago
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.
djmips 4y ago
Paper link? Was it this? https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf https://web.archive.org/web/20130425232048/http://www.cse.ps...
- btdmaster 4y ago
  Integer multiplication in time O(n log n): https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document