Name
Abstract | ||
|---|---|---|
We give an N . log N . 2(O(log)* (N)) time algorithm to multiply two N-bit integers that uses modular arithmetic for intermediate computations instead of arithmetic over complex numbers as in Furer's algorithm, which also has the same and so far the best known complexity. The previous best algorithm using modular arithmetic (by Schonhage and Strassen) has complexity O(N . log N . log log N). The advantage of using modular arithmetic as opposed to complex number arithmetic is that we can completely evade the task of bounding the truncation error due to finite approximations of complex numbers, which makes the analysis relatively simple. Our algorithm is based upon Furer's algorithm, but uses fast Fourier transform over multivariate polynomials along with an estimate of the least prime in an arithmetic progression to achieve this improvement in the modular setting. It can also be viewed as a p-adic version of Furer's algorithm. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1137/100811167 | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
integer multiplication,fast Fourier transform,modular arithmetic | Journal | 42 |
Issue | ISSN | Citations |
2 | 0097-5397 | 1 |
PageRank | References | Authors |
0.35 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anindya De | 1 | 239 | 24.77 |
| Piyush P. Kurur | 2 | 88 | 9.41 |
| Chandan Saha | 3 | 227 | 16.91 |
| Ramprasad Saptharishi | 4 | 184 | 13.72 |