4 ms·

Ok I'll be that guy - where is the reference implementation and at what n can I expect an improvement over existing libgmp multiplication on a core i7 ?

• ekimekim 7y ago
  https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document is the paper, which contains the closest thing to an implementation that I believe exists, and the answer for n is 'so large it would never fit in memory'. This is an important result mathematically, not something intended for practical use.
• thomasahle 7y ago
  It only really kicks in over the previous best at about n>2^2^4000 iirc. This is a theoretical paper, but it is possible that some of the new fourier transform ideas can be used by libgmp down the line.
  • Someone 7y ago
    Not that it matters, but the constant used in the paper is 4096, not 4000. This algorithm is proven to be O(n log n) only for numbers with at least 2^4096 ≪ 10^1200 bits. For comparison, we estimate there are 10^80 or so atoms in the known universe, so we would need quite a bit of progress in physics to even store one such number; this clearly is theoretical computer science. On the plus side, they didn’t set out to minimize that constant, and think it can easily [1] be decreased significantly. [1] ‘easily’ in the mathematical sense of “we think everybody who understands this paper and is willing to do potentially a lot of hard work will be able to pull it of”
    • klyrs 7y ago
      > This algorithm is proven to be O(n log n) only for numbers with at least 2^4096... No worries, all the rest runs in O(1)..
• vardump 7y ago
  This is what bothers me when someone uses Core i7 for performance comparisons: it covers a range of CPUs since 2008. Even saying "modern x86" would be more specific.