Remote Access Mathematics of Computation
Green Open Access

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

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

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