Complexity of the Schönhage–Strassen algorithm

Question

In the Wikipedia article, 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)))$?

Answer 1

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?, likely written with similar motivation to yours.