5 ms·

For whoever wondering about the practicality of this algorithm, no, at least for now. Constants aside, the algorithm currently requires an enormous cutoff for t

For whoever wondering about the practicality of this algorithm, no, at least for now. Constants aside, the algorithm currently requires an enormous cutoff for the recursion (anything below that should be handled by traditional algorithms): > Let `n0 := 2^(d^12) >= 2^4096`, and suppose that we wish to multiply integers with n bits. For `n >= n0` we will describe a recursive algorithm that reduces the problem to a collection of multiplication problems of size roughly n^(1/d). We will show that this algorithm achieves `M(n) = O(n log n)`, provided that `d >= 1729`. (p. 33) 2^(1729^12) ~= 10^(2.15 * 10^38). The authors do note the possibility of much lower cutoff: > In this section we outline a number of such modifications that together reduce the constant to `K = 8 + epsilon`, so that the modified algorithm achieves `M(n) = O(n log n)` for any `d >= 9` (rather than `d >= 1729`). (p. 39) Here 2^(9^12) has about 85 billion decimal digits. Much smaller, but still too big to be practical.

wbhart 8y ago
There are practical problems in pure mathematics that require multiplication of numbers with 85 billion digits. For example, polynomial multiplication can be reduced to integer multiplication, and certain problems, such as computing congruent numbers or class numbers of quadratic number fields can be reduced to that. Naturally the authors of the paper do not make any claims about the algorithm being practical though.
- lifthrasiir 8y ago
  Yeah, the recent pi calculation amassed 31.4 trillion decimal digits (or about 10^15 binary digits) of the computation load, which would definitely include the integer multiplication of numbers with the comparable size among others. I'm not sure though, because the currently widespread algorithm (Schönhage-Strassen) is practically within two orders of magnitude from O(n log n) [1] and the previous record holder (Fürer's) had been proved extremely infeasible. Also note that 85 billion digits do not relate to the constant itself: it is the lower bound that the new algorithm can make difference, otherwise it reduces to the base case. I'm not really qualified to determine the expected constant of this algorithm though, so it might actually prove feasible. [1] Its time complexity is O(n log n * log log n). The double logarithm is already slowly growing; log log 2^(10^15) ~= 34 for the reference. At this stage the constant is much more important than the time complexity itself. y-cruncher, a record-setting pi computation software, actually has a set of proprietary algorithms [2] optimized for modern hardwares. [2] http://www.numberworld.org/y-cruncher/internals/multiplication.html http://www.numberworld.org/y-cruncher/internals/multiplicati...
  - dragontamer 8y ago
    > Yeah, the recent pi calculation amassed 31.4 trillion decimal digits (or about 10^15 binary digits) of the computation load But that was to be cool, not for any practical problem. They needed 156 TiB of storage to hold that singular number, and that happened to be all-solid state storage ( because the majority of the time was spent on I/O, believe it or not!! ) That is to say: a faster CPU wouldn't really make the computation much faster. You need faster storage when you're dealing with numbers that big. Double-precision floats are what people need most of the time. Crypto-guys need 2048+ or 4096+ byte numbers or something around those sizes for cryptography purposes. I'm not sure if large numbers are really used anywhere else.
    - lifthrasiir 8y ago
      If you do agree that mathematical problems can be considered practical, many prime-hunting computations do intend to resolve conjectures (Seventeen or Bust [1] was a good example), thus solving practical problems. I of course think that that pi calculation is nothing more than GCP advertisement ;-) [1] https://en.wikipedia.org/wiki/Seventeen_or_Bust https://en.wikipedia.org/wiki/Seventeen_or_Bust
- fdej 8y ago
  Note that number of digits is actually 10^(85 billion), not 85 billion.
jacobolus 8y ago
Or for the audience here, 2^(9^12) is a number that takes roughly 100 gigabytes to store. Edit: oh wait, 2^(9^12) is the number of bits. So we are actually talking about numbers of the size 2^(2^(9^12)). “Too big to be practical” is a serious understatement here.
- deleted 8y ago
  [deleted]
chess93 8y ago
On the other hand, in practice, log log n is basically constant so we have had a practical n log n algorithm for a while :)

wbhart 8y ago

There are practical problems in pure mathematics that require multiplication of numbers with 85 billion digits. For example, polynomial multiplication can be reduced to integer multiplication, and certain problems, such as computing congruent numbers or class numbers of quadratic number fields can be reduced to that. Naturally the authors of the paper do not make any claims about the algorithm being practical though.

lifthrasiir 8y ago
Yeah, the recent pi calculation amassed 31.4 trillion decimal digits (or about 10^15 binary digits) of the computation load, which would definitely include the integer multiplication of numbers with the comparable size among others. I'm not sure though, because the currently widespread algorithm (Schönhage-Strassen) is practically within two orders of magnitude from O(n log n) [1] and the previous record holder (Fürer's) had been proved extremely infeasible. Also note that 85 billion digits do not relate to the constant itself: it is the lower bound that the new algorithm can make difference, otherwise it reduces to the base case. I'm not really qualified to determine the expected constant of this algorithm though, so it might actually prove feasible. [1] Its time complexity is O(n log n * log log n). The double logarithm is already slowly growing; log log 2^(10^15) ~= 34 for the reference. At this stage the constant is much more important than the time complexity itself. y-cruncher, a record-setting pi computation software, actually has a set of proprietary algorithms [2] optimized for modern hardwares. [2] http://www.numberworld.org/y-cruncher/internals/multiplication.html http://www.numberworld.org/y-cruncher/internals/multiplicati...
- dragontamer 8y ago
  > Yeah, the recent pi calculation amassed 31.4 trillion decimal digits (or about 10^15 binary digits) of the computation load But that was to be cool, not for any practical problem. They needed 156 TiB of storage to hold that singular number, and that happened to be all-solid state storage ( because the majority of the time was spent on I/O, believe it or not!! ) That is to say: a faster CPU wouldn't really make the computation much faster. You need faster storage when you're dealing with numbers that big. Double-precision floats are what people need most of the time. Crypto-guys need 2048+ or 4096+ byte numbers or something around those sizes for cryptography purposes. I'm not sure if large numbers are really used anywhere else.
  - lifthrasiir 8y ago
    If you do agree that mathematical problems can be considered practical, many prime-hunting computations do intend to resolve conjectures (Seventeen or Bust [1] was a good example), thus solving practical problems. I of course think that that pi calculation is nothing more than GCP advertisement ;-) [1] https://en.wikipedia.org/wiki/Seventeen_or_Bust https://en.wikipedia.org/wiki/Seventeen_or_Bust
fdej 8y ago
Note that number of digits is actually 10^(85 billion), not 85 billion.

jacobolus 8y ago

Or for the audience here, 2^(9^12) is a number that takes roughly 100 gigabytes to store. Edit: oh wait, 2^(9^12) is the number of bits. So we are actually talking about numbers of the size 2^(2^(9^12)). “Too big to be practical” is a serious understatement here.

deleted 8y ago
[deleted]

chess93 8y ago

On the other hand, in practice, log log n is basically constant so we have had a practical n log n algorithm for a while :)