How does the code accomplish the squaring?
For a large integer occupying N computer words, a simple digit-by-digit (“grammar school”) multiply operation (which needs on the order of N2 machine operations) is much too slow to be practical. Rather, the code uses a multiply algorithm based on the fast Fourier transform (FFT), which is described in many numerical analysis texts, such as the well-known Numerical Recipes (NR) books. (NR even has a set of so-called multiprecision integer routines, but I suggest staying away from them – they’re awful.) The code also uses the now-well-known Discrete Weighted Transform technique of Crandall and Fagin (for a detailed reference, see the source code header or this research paper) to implicitly do the modding. This permits one to “fill” the digits of the input vector to the FFT-based squaring, and thus to reduce the vector length by a factor of 2 or more relative to any pre-1994 codes. The upshot is, to write the world’s fastest Mersenne testing program, one must write (or make use of) the w
Related Questions
- What does software testing accomplish? Software testing will verify that the code written to perform the designed function does indeed do what it was designed to within predetermined parameters.
- Who were the Navajo Code Talkers and what did they accomplish in WWII?
- Get Discount Coupon Code - AnyMP4 Blu-ray Ripper
