4 Replies - 726 Views - Last Post: 10 April 2019 - 09:36 PM

#1 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12556
  • View blog
  • Posts: 45,683
  • Joined: 27-December 08

[News] Integer Multiplication in O(n log n) Time

Post icon  Posted 07 April 2019 - 03:52 PM

A couple weeks ago, a new algorithm was released. This algorithm multiplies two n-bit integers (using a multi-tape Turing Machine) in O(n log(n)) time. The best previous known result was O(n log(n) * 4 log*(n)) time.

In 1971, Schonhage and Strassen developed an algorithm to multiply two n-bit integers in O(n log(n) log(log(n))) time. In the same paper, they conjectured that the actual bound was Theta(n log(n)). In 2007, this result was sharpened to O(n log(n) * Klog*(n)) for some unspecified K > 1. Very recently, in 2018-2019, this bound was improved to O(n log(n) * 4 log*(n)).

The only lower bounds are linear. The trivial lower bound follows from the fact that we have to examine each bit, and there are 2n bits (given two n-bit integers).

Here is a link to the paper, in case anyone is interested. It is 43 pages and uses a lot of heavy-handed techniques, including algebra, Fourier analysis, and numerical approximations over the complex numbers.

https://hal.archives...070778/document

This post has been edited by macosxnerd101: 07 April 2019 - 03:54 PM


Is This A Good Question/Topic? 3
  • +

Replies To: [News] Integer Multiplication in O(n log n) Time

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6818
  • View blog
  • Posts: 23,196
  • Joined: 05-May 12

Re: [News] Integer Multiplication in O(n log n) Time

Posted 08 April 2019 - 01:14 PM

I tried jumping straight to section 5 first to see an outline of the algorithm, but I was rebuffed because their description of the algorithm seems to point back to sections 3 and 4 and just plugging in some baseline numbers. :( I wish the algorithm was described in much simpler terms like the way the Karatsuba multiplication algorithm is described.
Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11458
  • View blog
  • Posts: 19,523
  • Joined: 19-March 11

Re: [News] Integer Multiplication in O(n log n) Time

Posted 08 April 2019 - 05:23 PM

Literally, the first thing that popped into my head


Was This Post Helpful? 0
  • +
  • -

#4 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6818
  • View blog
  • Posts: 23,196
  • Joined: 05-May 12

Re: [News] Integer Multiplication in O(n log n) Time

Posted 10 April 2019 - 06:00 PM

From the paper...

Quote

All of the algorithms presented in this paper can be made completely explicit, and all implied big-O constants are in principle effectively computable. On the other hand, we make no attempt to minimise these constants or to otherwise exhibit a practical multiplication algorithm. Our aim is to establish the theoretical O(n log n) bound as directly as possible.

(emphasis mine).
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12556
  • View blog
  • Posts: 45,683
  • Joined: 27-December 08

Re: [News] Integer Multiplication in O(n log n) Time

Posted 10 April 2019 - 09:36 PM

Itís a theory paper. What did you expect? :P
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1