Rapid multiplication modulo the sum and difference of highly composite numbers

Percival, Colin

doi:10.1090/S0025-5718-02-01419-9

Rapid multiplication modulo the sum and difference of highly composite numbers
HTML articles powered by AMS MathViewer

by Colin Percival PDF

Math. Comp. 72 (2003), 387-395 Request permission

Abstract:

We extend the work of Richard Crandall et al. to demonstrate how the Discrete Weighted Transform (DWT) can be applied to speed up multiplication modulo any number of the form $a \pm b$ where $\prod _{p|ab}{p}$ is small. In particular this allows rapid computation modulo numbers of the form $k \cdot 2^n \pm 1$. In addition, we prove tight bounds on the rounding errors which naturally occur in floating-point implementations of FFT and DWT multiplications. This makes it possible for FFT multiplications to be used in situations where correctness is essential, for example in computer algebra packages.

References

D.H. Bailey, FFTs in External or Hierarchical Memory, NAS report RNR-89-004, December 1989.
Richard Crandall and Barry Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), no. 205, 305–324. MR 1185244, DOI 10.1090/S0025-5718-1994-1185244-1
R.E. Crandall, E.W. Mayer, and J.S. Papadopoulos, The twenty-fourth Fermat number is composite, submitted to Math. Comp.
M. Frigo and S.G. Johnson, FFTW, http://www.fftw.org/ (2000).
K. O. Geddes, S. R. Czapor, and G. Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Boston, MA, 1992. MR 1256483, DOI 10.1007/b102438
David Goldberg, What every compute scientist should know about floating-point arithmetic, ACM Computing Surveys, 23(1) (March 1991), 5-48.
Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
George U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Comp. 25 (1971), 757–768. MR 300488, DOI 10.1090/S0025-5718-1971-0300488-0
G. Woltman, The Great Internet Mersenne Prime Search, http://www.mersenne.org/ (2000).