4 ms·

Respect :). I Implemented Karatsuba a while ago and wondered if an even faster method would be available. It is! I admire the perseverance, grit, and intellig

by tdons 6y ago

Respect :). I Implemented Karatsuba a while ago and wondered if an even faster method would be available. It is! I admire the perseverance, grit, and intelligence needed to crack hard nuts like this.

jacobolus 6y ago
This new method will be marginally faster if you ever need to multiply two numbers on a scale where writing down the bits fills every plank-length cube in the known universe. Otherwise the “practical” benefit is limited to saving a few symbols when writing abstract math papers.
- the8472 6y ago
  > This new method will be marginally faster if you ever need to multiply two numbers on a scale where writing down the bits fills every plank-length cube in the known universe. If we're talking about physical implementations then you would also have to take the delay between those planck volumes into account
- croutonix 6y ago
  > “The best we can hope for is we’re three times faster,” van der Hoeven said. And they talk about billions of digits elsewhere in the article. I doubt that only applies for the ~8.46e184 digits you seem to be talking about.
  - jacobolus 6y ago
    From last time this came up, the number of bits in the numbers involved is 2^(9^12). Storing a count of the number of bits takes about 930 billion digits. Actually storing the bits or digits of the numbers per se takes a whole lot more, to say the least. https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document
- MauranKilom 6y ago
  Surely a practical benefit can come from this result being used in other proofs/systems, which then have real-world impact?
  - jacobolus 6y ago
    Yes, this result will be used to save a few printed symbols each time the topic comes up in future mathematics papers, and the beauty of the slightly simpler mathematical expressions will spark joy in mathematicians reading them.
deleted 6y ago
[deleted]
dreamcompiler 6y ago
Karatsuba is a beautiful algorithm and as good as it gets for "small" numbers (on the order of a few thousand bits or less). But when you get bigger than that you need the FFT methods, which are impractical for "small" numbers. So the two algorithms complement each other nicely.

by tdons 6y ago

Respect :). I Implemented Karatsuba a while ago and wondered if an even faster method would be available. It is! I admire the perseverance, grit, and intelligence needed to crack hard nuts like this.

jacobolus 6y ago

This new method will be marginally faster if you ever need to multiply two numbers on a scale where writing down the bits fills every plank-length cube in the known universe. Otherwise the “practical” benefit is limited to saving a few symbols when writing abstract math papers.

the8472 6y ago
> This new method will be marginally faster if you ever need to multiply two numbers on a scale where writing down the bits fills every plank-length cube in the known universe. If we're talking about physical implementations then you would also have to take the delay between those planck volumes into account
croutonix 6y ago
> “The best we can hope for is we’re three times faster,” van der Hoeven said. And they talk about billions of digits elsewhere in the article. I doubt that only applies for the ~8.46e184 digits you seem to be talking about.
- jacobolus 6y ago
  From last time this came up, the number of bits in the numbers involved is 2^(9^12). Storing a count of the number of bits takes about 930 billion digits. Actually storing the bits or digits of the numbers per se takes a whole lot more, to say the least. https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document
MauranKilom 6y ago
Surely a practical benefit can come from this result being used in other proofs/systems, which then have real-world impact?
- jacobolus 6y ago
  Yes, this result will be used to save a few printed symbols each time the topic comes up in future mathematics papers, and the beauty of the slightly simpler mathematical expressions will spark joy in mathematicians reading them.

deleted 6y ago

[deleted]

dreamcompiler 6y ago

Karatsuba is a beautiful algorithm and as good as it gets for "small" numbers (on the order of a few thousand bits or less). But when you get bigger than that you need the FFT methods, which are impractical for "small" numbers. So the two algorithms complement each other nicely.