arXiv preprint ·
Long rational and Gaussian integer multiplication
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Long integer multiplication is a fundamental operation in computational algebra, heavily relying on Toom--Cook and related evaluation-interpolation algorithms. Conventional wisdom dictates that multiplication on the Gaussian integers $\mathbb{Z}[i]$ is reduced to standard rational integer multiplication, since $\mathbb{Z}[i]$ is a ring extension of $\mathbb{Z}$. We show that this approach is far from optimal and moreover inverting this established paradigm, that is reducing rational to Gaussian multiplication, leads to faster rational integer multiplication algorithms. We introduce a novel Toom--Cook framework that reduces rational long integer multiplication to Gaussian integer multiplication, yielding a strictly more efficient computational pipeline. By taking advantage of the special properties of the rational integer domain inside the Gaussian integers, we achieve a more favourable algebraic structure that reduces the overall arithmetic cost in every metric. To validate this theoretical shift, we provide a complete implementation of our algorithm. Benchmarks demonstrate that our approach outperforms the highly optimised GNU Multiple Precision Arithmetic Library (GMP) by up to 29\%, bridging a fundamental theoretical insight with significant practical improvements in high-performance computer algebra.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
On the boomerang spectrum of the APN power function $x^{q+2}$ over $\F_{q^2}$
Matrix Waring Problem in finite fields with coefficients from $\mathrm{GL}(2, \mathbb{F}_p)$
Gaussian mass inequalities for lattices
Rohrbach's Conjecture for Finite Groups
ECPack.wl: A Mathematica Package for Elliptic Curves over the Rationals and Finite Fields
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.