1
$\begingroup$

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)))$?

$\endgroup$
11
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.