Rapid multiplication modulo the sum and difference of highly composite numbers
From MaRDI portal
It is known that when using discrete weighted transforms for multiplication, time is saved by working modulo \(2^n-1\) for some \(n\) [see \textit{B. Crandall} and \textit{B. Fagin}, ibid. 62, 305-324 (1994; Zbl 0839.11065)]. In the present paper it is shown how a similar benefit is given by working modulo \(a\pm b\) when the product of the primes that divide \(ab\) is small. Some results of experiments with randomly selected numbers, and also with worst-case numbers, are given.
Recommendations
Cites work
- Discrete Weighted Transforms and Large-Integer Arithmetic
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 108109 (Why is no real title available?)
- scientific article; zbMATH DE number 846277 (Why is no real title available?)
- Roundoff Error Analysis of the Fast Fourier Transform
- The twenty-fourth Fermat number is composite
Cited in
(7)- Optimization of multidigit multiplication based on discrete (Fourier, cosine, sine) transforms in the parallel computing model
- Error bounds on complex floating-point multiplication
- Discrete Weighted Transforms and Large-Integer Arithmetic
- Fast convolutions of packed strings and pattern matching with wildcards
- Multiple product modulo arbitrary numbers
- Multiple product modulo arbitrary numbers
- The nature of numbers: real computing
This page was built for publication: Rapid multiplication modulo the sum and difference of highly composite numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4780378)