Fast bignum square computation

This article aims to determine the fastest method for computing y = x^2 for bigints expressed as dynamic arrays of unsigned DWORDs.

Problem statement

Given the representation of a bigint x as an array of DWORDs:

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

where:

• n 1 is the number of DWORDs used
• x = x[0] x[1]

Find the value of y = x^2 as quickly as possible without losing precision.

Assumptions:

• Calculations are performed using C and 32-bit integer arithmetic with carry.

Naive approach (O(n^2) multiplication)

The naive approach involves multiplying x by itself, which takes O(n^2) time. This can be expressed as:

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

Expanding the product, we get:

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 multiplication

The Karatsuba algorithm can be used to speed up multiplication to O(n^log2(3)). While it appears promising, the recursive nature of the algorithm can introduce a significant performance overhead for large numbers.

Optimized Schönhage-Strassen multiplication

The Schönhage-Strassen algorithm offers even faster multiplication at O(nlog(n)(log(log(n)))) using a divide-and-conquer approach. However, this algorithm has practical limitations due to overflow issues and the need for modular arithmetic on unsigned integers.

Conclusion

For smaller numbers, the simple O(n^2) multiplication approach is the most efficient. For larger numbers, the Karatsuba multiplication algorithm is recommended. Further optimizations can be explored to improve performance, such as using FFT (Fast Fourier Transform) or NTT (Number Theoretic Transform).