betaFeedback

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 Z[i]\mathbb{Z}[i] is reduced to standard rational integer multiplication, since Z[i]\mathbb{Z}[i] is a ring extension of Z\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.

Paper details

vlnc:W_mbnshrxs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…