3 ms·

There are practical problems in pure mathematics that require multiplication of numbers with 85 billion digits. For example, polynomial multiplication can be re

by 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.

by wbhart 8y ago

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.