Quel est l'algorithme le plus rapide pour mettre au carré de grands entiers représentés sous forme de tableaux DWORD ?

Calcul rapide du carré bignum

Cet article vise à déterminer la méthode la plus rapide pour calculer y = x^2 pour les bigints exprimés sous forme de tableaux dynamiques de DWORDs non signés.

Énoncé du problème

Étant donné la représentation d'un bigint x sous la forme d'un tableau de DWORDs :

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

où :

• n 1 est le nombre de DWORDs utilisés
• x = x[0] x[1]<< 32 ... x[N]<<32*(n)

Trouver la valeur de y = x^2 le plus rapidement possible sans perdre en précision.

Hypothèses :

• Les calculs sont effectués en utilisant l'arithmétique C et entière 32 bits avec report.

Approche naïve (multiplication O(n^2))

L'approche naïve consiste à multiplier x par lui-même, ce qui prend un temps O(n^2). Cela peut être exprimé comme suit :

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

En développant le produit, nous obtenons :

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  )

Multiplication de Karatsuba

L'algorithme de Karatsuba peut être utilisé pour accélérer la multiplication jusqu'à O(n^log2(3)). Bien que cela semble prometteur, la nature récursive de l'algorithme peut introduire une surcharge de performances significative pour les grands nombres.

Multiplication de Schönhage-Strassen optimisée

L'algorithme de Schönhage-Strassen offre une multiplication encore plus rapide en O( nlog(n)(log(log(n)))) en utilisant une approche diviser pour régner. Cependant, cet algorithme présente des limites pratiques en raison de problèmes de débordement et de la nécessité d'une arithmétique modulaire sur les entiers non signés.

Conclusion

Pour les nombres plus petits, l'approche simple de multiplication O(n^2) est la meilleure solution. le plus efficace. Pour les nombres plus grands, l'algorithme de multiplication Karatsuba est recommandé. D'autres optimisations peuvent être explorées pour améliorer les performances, comme l'utilisation de FFT (Fast Fourier Transform) ou NTT (Number Theoretic Transform).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!