Editing Schönhage–Strassen algorithm (section)

==Optimizations==

This section explains a number of important practical optimizations, when implementing Schönhage–Strassen.

=== Use of other multiplications algorithm, inside algorithm ===

Below a certain cutoff point, it's more efficient to use other multiplication algorithms, such as [[Toom–Cook multiplication]].<ref>{{cite web |last1=Gaudry |first1=Pierrick |last2=Kruppa |first2=Alexander |last3=Zimmermann |first3=Paul |page=7|year=2007|title=A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm |url=https://inria.hal.science/inria-00126462/file/fft.final.pdf}}</ref>

=== Square root of 2 trick ===

The idea is to use <math> \sqrt{2}  </math> as a [[root of unity]] of order <math> 2^{n+2} </math> in finite field <math>\mathrm{GF}(2^{n+2} +1)</math> ( it is a solution to equation <math> \theta^{2^{n+2}} \equiv 1  \pmod {2^{n+2} + 1}</math>), when weighting values in NTT (number theoretic transformation) approach. It has been shown to save 10% in integer multiplication time.<ref>{{cite web |last1=Gaudry |first1=Pierrick |last2=Kruppa |first2=Alexander |page=6 | date=2007 | last3=Zimmermann |first3=Paul |title=A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm |url=https://inria.hal.science/inria-00126462/file/fft.final.pdf}}</ref>

=== Granlund's trick ===

By letting <math> m = N + h </math>, one can compute
<math>uv \bmod {2^N +1}</math> and <math>(u \bmod {2^h})(v \bmod 2^h)</math>. In combination with CRT (Chinese Remainder Theorem) to 
find exact values of multiplication {{mvar|uv}}<ref>{{cite web |last1=Gaudry |first1=Pierrick |last2=Kruppa |page=6|date=2007|first2=Alexander |last3=Zimmermann |first3=Paul |title=A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm |url=https://inria.hal.science/inria-00126462/file/fft.final.pdf}}</ref>