On squaring and multiplying large integers
Dan Zuras · 2002
Methods of squaring large integers are discussed. The obvious O(n/sup 2/) method turns out to be best for small numbers. The existing /spl ap/ O(n/sup 1.585/) method becomes better as the numbers get bigger. New methods that are /spl ap/ O(n/sup 1.465/) and /spl ap/ O(n/sup 2.404/) are presented. All of these methods can be generalized to multiplication and turn out to be faster than a fast Fourier transform (FFT) multiplication for numbers that can be quite large (>3,000,000 b). Squaring seems to be fundamentally faster than multiplication, but it is shown that T/sub mult/ /spl les/ 2T/sub sq/ + O(n).>