WorksComputer Science
Long rational and Gaussian integer multiplication
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 is reduced to standard rational integer multiplication, since is a ring extension of . 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.