Editing Schönhage–Strassen algorithm (section)

=== How to choose ''K'' for a specific ''N'' ===

The following formula is helpful, finding a proper {{mvar|K}} (number of groups to divide {{mvar|N}} bits into) given bit size {{mvar|N}} by calculating efficiency :<ref>{{cite web |last1=Gaudry |first1=Pierrick |last2=Kruppa |first2=Alexander |last3=Zimmermann |first3=Paul |title=A GMP-based Implementation of Schönhage-Strassen's Large Integer Multiplication Algorithm | page = 2 | date=2007|url=https://inria.hal.science/inria-00126462/file/fft.final.pdf}}</ref>

<math> E = \frac{\frac{2N}{K}+k}{n} </math> {{mvar|N}} is bit size (the one used in <math> 2^N + 1 </math>) at outermost level. {{mvar|K}} gives <math> \frac{N}{K} </math> groups of bits,  where <math> K = 2^k </math>.

{{mvar|n}} is found through {{mvar|N, K}} and {{mvar|k}} by finding the smallest {{mvar|x}}, such that  <math>  2N/K +k \le n = K2^x </math>

If one assume efficiency above 50%, <math> \frac{n}{2} \le \frac{2N}{K}, K \le n </math> and {{mvar|k}} is very small compared to rest of formula; one get

:<math> K \le 2\sqrt{N} </math>

This means: When something is very effective; {{mvar|K}} is bound above by <math> 2\sqrt{N} </math> or asymptotically bound above by <math> \sqrt{N} </math>