Skip to main content
2 of 2
grammar corrected
user3483902
  • 325
  • 3
  • 10

For new results, in integer multiplication, check the breakthrough paper by: David Harvey, and Joris Van Der Hoeven, et al . Integer multiplicaion in $O(n*(log$ $n))$. This proves Schonhage Strassens' conjecture from the 1970s that integer multiplication is really possible in $O(n*(log$ $n))$. From, straightforward (school) integer multiplication which is $O( n^{2}) $, to karatsubas' algorithm which is $O(n^{1.58})$, to $O(n*(log$ $n))$, by above authors. The authors use the property of specific multivariate polynomial rings that admit efficient multiplication.

The authors show that integer multiplication (which is one dimensional) could be represented in a setting of a specific multivariate polynomial ring. Starting with a binary representation of integers, begin with the fixed point coordinate vectors(to a precision), and then go on to utilize them in coefficient rings for that polynomial representation. One could select parameters, and reduce the integer multiplication problem to one of convolution over a ring with a specific structure, reaching the bound.

The bound is a significant improvement over earlier algorithms, and with many digits the efficiencies are apparent, for a large number of digits billions, and larger scales as author(s) claim its unknown, but good performance is possible.

user3483902
  • 325
  • 3
  • 10