Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

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
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\vert 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 [Enhancements On Off] (What's this?)

  • 1. D.H. Bailey, FFTs in External or Hierarchical Memory, NAS report RNR-89-004, December 1989.
  • 2. R. Crandall and B. Fagin, Discrete weighted transforms and large integer arithmetic, Math. Comp. 62 (1994), 305-324. MR 94c:11123
  • 3. R.E. Crandall, E.W. Mayer, and J.S. Papadopoulos, The twenty-fourth Fermat number is composite, submitted to Math. Comp.
  • 4. M. Frigo and S.G. Johnson, FFTW, http://www.fftw.org/ (2000).
  • 5. K.O. Geddes, S.R. Czapor, and G. Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, 1992. MR 96a:68049
  • 6. David Goldberg, What every compute scientist should know about floating-point arithmetic, ACM Computing Surveys, 23(1) (March 1991), 5-48.
  • 7. N.J. Higham, Accuracy and stability of numerical algorithms, SIAM, 1996. MR 97a:65047
  • 8. D.E. Knuth, The art of computer programming, volume 2: seminumerical algorithms, 2nd edition, Addison-Wesley, 1997. MR 83i:68003 (earlier ed.)
  • 9. G.U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Comp. 25 (1971), 757-786. MR 45:9534
  • 10. G. Woltman, The Great Internet Mersenne Prime Search, http://www.mersenne.org/ (2000).

Similar Articles

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

DOI: http://dx.doi.org/10.1090/S0025-5718-02-01419-9
PII: S 0025-5718(02)01419-9
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