5 ms·

Schönhage–Strassen Algorithm

• civilized 4y ago
  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
• marcinreal 4y ago
  Found this link amusing (from the article): https://en.m.wikipedia.org/wiki/Galactic_algorithm https://en.m.wikipedia.org/wiki/Galactic_algorithm
• agumonkey 4y ago
  First time I heard FFT was involved in multiplication I was as shocked as excited.
  • emacs28 4y ago
    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.