Rapid multiplication modulo the sum and difference of highly composite numbers
Author:
Colin Percival
Journal:
Math. Comp. 72 (2003), 387-395
MSC (2000):
Primary 65G50, 65T50; Secondary 11A51
DOI:
https://doi.org/10.1090/S0025-5718-02-01419-9
Published electronically:
March 5, 2002
MathSciNet review:
1933827
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
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.
- 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 https://doi.org/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
- 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 Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
- George U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Comp. 25 (1971), 757–768. MR 300488, DOI https://doi.org/10.1090/S0025-5718-1971-0300488-0
- G. Woltman, The Great Internet Mersenne Prime Search, http://www.mersenne.org/ (2000).
Retrieve articles in Mathematics of Computation with MSC (2000): 65G50, 65T50, 11A51
Retrieve articles in all journals with MSC (2000): 65G50, 65T50, 11A51
Additional Information
Colin Percival
Affiliation:
Department of Mathematics and Statistics, Simon Fraser University, Burnaby, British Columbia, Canada
Email:
cperciva@sfu.ca
Keywords:
Rapid multiplication,
FFT,
rounding errors
Received by editor(s):
September 12, 2000
Received by editor(s) in revised form:
March 15, 2001
Published electronically:
March 5, 2002
Additional Notes:
This work was supported by MITACS and NSERC of Canada
Article copyright:
© Copyright 2002
American Mathematical Society
