# Integer multiplication in time O(n log n)

## Media coverage

### Newspapers etc

• BBC World Service — Newsday program, 4-minute interview with Joris (2nd April 2019), beginning at 18:45 in the stream, or listen to OGG file or MP3 file
• BNR Nieuwsradio, 3-minute interview with Joris (in Dutch) (3rd April 2019), listen to the stream, or OGG file or MP3 file
• ABC Illawarra — Mornings with Nick Rheinberger, 8-minute interview with David (9th April 2019), listen to OGG file or MP3 file
• Triple J, 3-minute interview with David on “Alice Matthews' Maths News” segment, Mornings with Ben and Liam (5th April 2019), listen to OGG file or MP3 file
• ABC Hobart — Evenings with Louise Saunders, 12-minute interview with David, broadcast simultaneously in Sydney, Melbourne, Brisbane, Adelaide, etc (25th April 2019), beginning at 1:37:22 in the stream, or listen to OGG file or MP3 file

1. Has the paper been peer-reviewed?

No (as of March 2019). Yes, it was published in March 2021.

2. Is there pseudocode available?

No, and we have no plans to write any.

3. For what size numbers is the new algorithm faster than previous algorithms?

Short answer: we have no idea.

Much internet commentary has focused on the quantity n0 = 2172912 appearing in the paper. This number is roughly 10214857091104455251940635045059417341952.

Some people have asserted that the new algorithm only works for nn0, and/or that the algorithm only becomes faster than previous algorithms for nn0. These assertions are somewhat misleading.

For n < n0, the new algorithm is by definition no faster than existing algorithms, because it calls an existing algorithm to do its work. The value n0 is simply an explicit threshold that was chosen to ensure that the inductive step of our proof of the complexity bound works out correctly. The actual value was chosen to make the proof as straightforward as possible; it was not chosen to optimise the overall running time.

On the other hand, for n slightly larger than n0, the new algorithm might turn out to be either faster or slower than existing algorithms. This depends on, among other things, the implied big-O constants for both the new algorithm and the algorithm with which it is being compared. Since we do not know (yet) what these constants are, we cannot tell which is faster.

In any case, it is not really possible to make a fair comparison without first making a serious effort to optimise the new algorithm. There are many points where the algorithm could be tightened up (see for example the discussion in Section 5.4), and there are many parameters that could be tweaked (such as the threshold n0, the dimension d, and the resampling parameter α). This is a very complex problem which is beyond the scope of the paper. Moreover, we observe that for implementations on actual computers, the efficiency of the new algorithm depends heavily on hardware characteristics; as the new algorithm reduces the bulk of the workload to additions and subtractions, it may be particularly well-suited for processors that perform hardware additions much faster than hardware multiplications.

4. Why 1729?

Just a lucky coincidence!

5. What is the space complexity (memory usage) of the algorithm?

If implemented in a reasonable way, and assuming O(1) processors, the space complexity should be O(n) bits.

6. The paper is too hard. Is there an easier way?