Schönhage-Strassen Depth

Question

Good evening,

I recognized that the depth of the Schönhage-Strassen algorithm in the Chapter "Parallel Arithmetic Algorithms" is given in the theorem on slide 127 as O(log(n)) and in the summary on slide 144 as O(log(n)^2).

I assume that the depth on slide 144 also considers 'n' to be the number of bits of both numbers and therefore probably O(log(n)^2) is the correct depth like it is for the other radix-B-multiplication algorithms listed there.

Is this assumption correct?

Thanks in advance.

Answer 1

Thanks for pointing out this inconsistency. Actually, the in-depth analysis you find on the slides has been made to clarify such inconsistencies since the parallel runtime is nowhere mentioned for the Schönhage-Strassen multiplication. The analysis around slides 127 give us the result that the depth is O(log(n)), so the summary on slide 144 is too pessimistic and has now been corrected.

You know that the algorithms in that chapter are less relevant for the exam. It is sufficient to know which algorithms exist, what their depth and work is and how they work in principle so that you may be able to use them in a given problem. However, you don't have to provide correctness proofs or complexity analyses of these algorithms (but of others!) in the exam.