Was ist der schnellste Algorithmus zum Quadrieren großer Ganzzahlen, die als DWORD-Arrays dargestellt werden?

Schnelle Bignum-Quadrat-Berechnung

Ziel dieses Artikels ist es, die schnellste Methode zur Berechnung von y = x^2 für Bigints zu bestimmen, die als dynamische Arrays von vorzeichenlosen DWORDs ausgedrückt werden.

Problemstellung

Gegeben sei die Darstellung eines Bigint x als Array von DWORDs:

DWORD x[n+1] = { LSW, ......, MSW };

wobei:

• n 1 die Anzahl der verwendeten DWORDs ist
• x = x[0] x[1]<< 32 ... x[N]<<32*(n)

Finden Sie den Wert von y = x^2 so schnell wie möglich, ohne an Präzision zu verlieren.

Annahmen:

• Berechnungen werden mit C und 32-Bit-Ganzzahlarithmetik mit Übertrag durchgeführt.

Naiver Ansatz (O(n^2)-Multiplikation)

Der naive Ansatz beinhaltet die Multiplikation von x mit selbst, was O(n^2) Zeit benötigt. Dies kann ausgedrückt werden als:

y = x * x
y = (x0 + x1 + x2 + ...xn)*(x0 + x1 + x2 + ...xn)

Wenn wir das Produkt erweitern, erhalten wir:

y0     = x0*x0
y1     = x1*x0 + x0*x1
y2     = x2*x0 + x1*x1 + x0*x2
y3     = x3*x0 + x2*x1 + x1*x2
...
y(2n-3) = xn(n-2)*x(n  ) + x(n-1)*x(n-1) + x(n  )*x(n-2)
y(2n-2) = xn(n-1)*x(n  ) + x(n  )*x(n-1)
y(2n-1) = xn(n  )*x(n  )

Karatsuba-Multiplikation

Der Karatsuba-Algorithmus kann verwendet werden, um die Multiplikation zu beschleunigen O(n^log2(3)). Obwohl es vielversprechend erscheint, kann die rekursive Natur des Algorithmus bei großen Zahlen zu einem erheblichen Leistungsaufwand führen.

Optimierte Schönhage-Strassen-Multiplikation

Der Schönhage-Strassen-Algorithmus bietet eine noch schnellere Multiplikation bei O( nlog(n)(log(log(n)))) unter Verwendung eines Divide-and-Conquer-Ansatzes. Dieser Algorithmus hat jedoch praktische Einschränkungen aufgrund von Überlaufproblemen und der Notwendigkeit einer modularen Arithmetik für vorzeichenlose ganze Zahlen.

Schlussfolgerung

Für kleinere Zahlen ist der einfache O(n^2)-Multiplikationsansatz der am effizientesten. Für größere Zahlen empfiehlt sich der Karatsuba-Multiplikationsalgorithmus. Weitere Optimierungen können untersucht werden, um die Leistung zu verbessern, beispielsweise die Verwendung von FFT (Fast Fourier Transform) oder NTT (Number Theoretic Transform).

Das obige ist der detaillierte Inhalt vonWas ist der schnellste Algorithmus zum Quadrieren großer Ganzzahlen, die als DWORD-Arrays dargestellt werden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!