Improvements on the accelerated integer GCD algorithm

DOI10.1016/S0020-0190(96)00185-8MaRDI QIDQ290191zbMATH OpenOpenAlexFDO

Authors Mohamed S. Sedjelmaci, Christian Lavault

Publication date 1 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.2266

zbMATH Keywords

parallel algorithmsnumber theoryinteger greatest common divisor (GCD)parallel arithmetic computing

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Number-theoretic algorithms; complexity (11Y16)

Abstract: The present paper analyses and presents several improvements to the algorithm for finding the $(a,b)$-pairs of integers used in the $k$-ary reduction of the right-shift $k$-ary integer GCD algorithm. While the worst-case complexity of Weber's "Accelerated integer GCD algorithm" is $cOl(lo{g}_{p}hi(k{)}^2)$, we show that the worst-case number of iterations of the while loop is exactly $frac12llfloorlo{g}_{phi}(k)floor$, where $phi:=frac12l(1+sqrt5)$.par We suggest improvements on the average complexity of the latter algorithm and also present two new faster residual algorithms: the sequential and the parallel one. A lower bound on the probability of avoiding the while loop in our parallel residual algorithm is also given.

Recommendations

• The accelerated integer GCD algorithm
• The mixed binary Euclid algorithm
• Two Fast GCD Algorithms
• On a parallel Lehmer-Euclid GCD algorithm
• Parallel implementation of the accelerated integer GCD algorithm

Cites work

• scientific article; zbMATH DE number 3874496 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 1263309 (Why is no real title available?)
• Parallel implementation of the accelerated integer GCD algorithm
• The accelerated integer GCD algorithm
• Two Fast GCD Algorithms

Cited in

(7)

• Fast computation of GCDs
• scientific article; zbMATH DE number 3908170 (Why is no real title available?)
• Worst-case analysis of Weber's GCD algorithm
• Arithmetically improved algorithmic performance
• A modular reduction for GCD computation.
• scientific article; zbMATH DE number 1736309 (Why is no real title available?)
• scientific article; zbMATH DE number 3995051 (Why is no real title available?)

This page was built for publication: Improvements on the accelerated integer GCD algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290191)