<p>What you are actually asking is for the performance of the Schönhage–Strassen algorithm in the unit cost RAM (rather than its bit complexity). This is covered in Fürer's paper <a href="https://arxiv.org/abs/1402.1811" rel="noreferrer">How Fast Can We Multiply Large Integers on an Actual Computer?</a>, likely written with similar motivation to yours.</p>

CC BY-SA 3.0
2017-10-15T16:12:14.650Z
2017-10-15T16:12:14.650Z
Yuval Filmus
<p>In the Wikipedia <a href="https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm" rel="nofollow noreferrer">article</a>, the complexity is listed as $O(n \cdot \log (n) \cdot \log (\log (n)))$, where $n$ is the number of bits. </p>

<p>Would the real bound be given by setting $n=\frac{b}{w}$, where $b$ is the number of bits and $w$ is the word length in the computer? i.e., if I assume that numbers of size $\log (n)$ can be multiplied in $O(1)$ time, then can two numbers of size $r \log (n)$ be multiplied in $O(r \cdot \log (r) \cdot \log( \log (r)))$?</p>

<complexity>
Complexity of the Schönhage–Strassen algorithm
Arjun P
# Complexity of the Schönhage–Strassen algorithm

(Asked by: username_0 on 2017-10-15)

In the Wikipedia [article](https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm), the complexity is listed as $O(n \cdot \log (n) \cdot \log (\log (n)))$, where $n$ is the number of bits.

Would the real bound be given by setting $n=\frac{b}{w}$, where $b$ is the number of bits and $w$ is the word length in the computer? i.e., if I assume that numbers of size $\log (n)$ can be multiplied in $O(1)$ time, then can two numbers of size $r \log (n)$ be multiplied in $O(r \cdot \log (r) \cdot \log( \log (r)))$?

**Tags:** complexity

---

## 1 answers

### Answer by username_1 on 2017-10-15. Score: 11 | Accepted answer

What you are actually asking is for the performance of the Schönhage–Strassen algorithm in the unit cost RAM (rather than its bit complexity). This is covered in Fürer's paper [How Fast Can We Multiply Large Integers on an Actual Computer?](https://arxiv.org/abs/1402.1811), likely written with similar motivation to yours.


---

