Mathematicians have found a new way to multiply two numbers together

Re:Mathematicians have found a new way to multiply two numbe... by MrEldritch on Friday March 29, 2019 @03:07PM (#19524576)

The reason it isn't actually important to have a specific algorithmic implementation is that - like other exotic multiplication algorithms with better big-O complexity than the usual ones - the constant factors are much, much bigger, to the point where they would only become noticeably faster for absurdly huge integers. The theoretical aspect of this is the interesting part.

[ Parent | on HN ]

Re:Mathematicians have found a new way to multiply two numbe... by db48x on Saturday March 30, 2019 @02:23AM (#19528084)

In fact, in this case the algorithm is only intended for numbers with 2^4096 bits. See section 5 of the paper:

  In this section we present the main integer multiplication
  algorithm. We actually give a family of algorithms,
  parameterised by a dimension parameter d > 2. Let n_0 :=
  2^(d^12) > 2^4096, and suppose that we wish to multiply
  integers with n bits. For n < n_0, we may use any convenient
  base-case multiplication algorithm, such as the classical
  O(n^2) algorithm.

[ Parent | on HN ]