How Can We Achieve Fast Square Computation of Big Numbers?

Fast Sqare Computation of Big Numbers

Problem:
Given a bignum represented as a dynamic array of unsigned DWORDs, the task is to find the square of the bignum as fast as possible without losing precision.

Solution Approach:

The provided algorithm efficiently computes the square of a bignum by optimizing the multiplication using a divide-and-conquer approach.

Optimized Karatsuba Multiplication:

After tweaking and optimizations, Karatsuba multiplication is faster than the O(N^2) classic multiplication for input sizes over 32*98 bits. For smaller numbers, the fast sqr method remains more efficient.

Modified Schönhage-Strassen Multiplication for Square Implementation:

FFT and NTT transforms were explored for speedup, but their accuracy loss and implementation complexity made them less suitable.

NTT Optimization:

Intensive optimizations of NTT resulted in improved performance, with the threshold for NTT sqr set at 31032 bits and NTT mul at 139632 bits.

Conclusion:

For smaller numbers, the fast sqr method proves to be the fastest option. After a threshold, Karatsuba multiplication becomes more efficient. However, the search for a more efficient alternative to Karatsuba continues.

The above is the detailed content of How Can We Achieve Fast Square Computation of Big Numbers?. For more information, please follow other related articles on the PHP Chinese website!