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

Page 1 of 1

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

### #1 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,861
• Joined: 27-December 08

# [News] Integer Multiplication in O(n log n) Time 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 Reputation: 7187
• Posts: 24,357
• 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.

### #3 jon.kiparsky Reputation: 11736
• Posts: 19,929
• 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

### #4 Skydiver Reputation: 7187
• Posts: 24,357
• 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).

### #5 macosxnerd101 • • Games, Graphs, and Auctions
•     Reputation: 12680
• Posts: 45,861
• 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? Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }