Mathematics of Computation

Author(s): Colin Percival.
Journal: Math. Comp. 72 (2003), 387-395.
MSC (2000): Primary 65G50, 65T50; Secondary 11A51
Posted: March 5, 2002
Retrieve article in: PDF DVI PostScript

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.

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).

Retrieve articles in Mathematics of Computation with MSC (2000): 65G50, 65T50, 11A51

Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Second Edition, SIAM, 2002.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS