of the vector before moving on to the next one. The "square root of 2 trick", first described by Schönhage, is to note that, provided k ≥ 2, 23n/4−2n/4 is a square root of 2 mod 2n+1, and so a 4n-th root of unity (since 22n ≡ 1). This allows the transform length to be extended from 2k to 2k + 1. Finally, the authors are careful to choose the right value of k for different ranges of input numbers, noting that the optimal value of k may go back and forth between the same values several times as the input size increases. References Computer arithmetic algorithms Multiplication