Fast Bignum Square Computation

Este artículo tiene como objetivo determinar el método más rápido para calcular y = x^2 para BigInts expresados ​​como matrices dinámicas de Dwords unsigned. DWords:

dword x [n 1] = {lsw, ......, msw};

[&] donde:

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

x = x [0] x [1]

Encuentre el valor de y = x^2 lo más rápido posible sin perder la precisión.
supuestaciones:

Los cálculos se realizan usando C y 32-bit intrager aritmetic con transporte. (O (n^2) multiplicación)

El enfoque ingenuo implica multiplicar x por sí mismo, que toma o (n^2) tiempo. Esto se puede expresar como:

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

• expandiendo el producto, obtenemos:

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 multiplicación

El algoritmo Karatsuba se puede usar para acelerar la multiplicación a o (n^log2 (3)). Si bien parece prometedor, la naturaleza recursiva del algoritmo puede introducir una sobrecarga de rendimiento significativa para números grandes.

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

schönhage-straassen multiplicación

el schönhage-straassen algorithm ofrece una multiplicación aún más rápida en o (n [&] log (n)

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  )