// Es ist 2 <= len1 <= len2.
{
// Methode:
- // source1 ist ein Stück der Länge N1, source2 ein oder mehrere Stücke
- // der Länge N2, mit N1+N2 <= N, wobei N Zweierpotenz ist.
+ // source1 ist ein Stück der Länge N1, source2 ein oder mehrere Stücke
+ // der Länge N2, mit N1+N2 <= N, wobei N Zweierpotenz ist.
// sum(i=0..N-1, x_i b^i) * sum(i=0..N-1, y_i b^i) wird errechnet,
// indem man die beiden Polynome
// sum(i=0..N-1, x_i T^i), sum(i=0..N-1, y_i T^i)
var uint32 n;
integerlengthC(len1-1, n=); // 2^(n-1) < len1 <= 2^n
var uintC len = (uintC)1 << n; // kleinste Zweierpotenz >= len1
- // Wählt man N = len, so hat man ceiling(len2/(len-len1+1)) * FFT(len).
- // Wählt man N = 2*len, so hat man ceiling(len2/(2*len-len1+1)) * FFT(2*len).
- // Wir wählen das billigere von beiden:
+ // Wählt man N = len, so hat man ceiling(len2/(len-len1+1)) * FFT(len).
+ // Wählt man N = 2*len, so hat man ceiling(len2/(2*len-len1+1)) * FFT(2*len).
+ // Wir wählen das billigere von beiden:
// Bei ceiling(len2/(len-len1+1)) <= 2 * ceiling(len2/(2*len-len1+1))
// nimmt man N = len, bei ....... > ........ dagegen N = 2*len.
- // (Wahl von N = 4*len oder mehr bringt nur in Extremfällen etwas.)
+ // (Wahl von N = 4*len oder mehr bringt nur in Extremfällen etwas.)
if (len2 > 2 * (len-len1+1) * (len2 <= (2*len-len1+1) ? 1 : ceiling(len2,(2*len-len1+1)))) {
n = n+1;
len = len << 1;