๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Improvements on the accelerated integer GCD algorithm

โœ Scribed by Mohamed S. Sedjelmaci; Christian Lavault

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
493 KB
Volume
61
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

The present paper analyses and presents several improvements to the algorithm for finding the (a, b)-pairs used in the k-ary reduction of the right-shift k-ary integer GCD algorithm. While the worst-case complexity of the "Accelerated integer GCD algorithm" is 0( (log,( k))'), we show that the worst-case number of iterations of the while loop is exactly t(k) = $ [log,( k)J (where 4 = $ ( 1 + a) ). We suggest improvements on the latter algorithm and 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.

๐Ÿ“œ SIMILAR VOLUMES

A Double-Digit Lehmer-Euclid Algorithm f
A Double-Digit Lehmer-Euclid Algorithm for Finding the GCD of Long Integers
โœ Tudor Jebelean ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 316 KB

The use of pairs of double digits in the Lehmer-Euclid multiprecision GCD algorithm halves the number of long multiplications, but a straightforward implementation of this idea does not give the desired speed-up. We show how to overcome the practical difficulties by using an enhanced condition for e

On Accelerating the Convergence of Nonli
On Accelerating the Convergence of Nonlinear Iterative Algorithms
โœ D.W. Black; A.P. Rothmayer ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 505 KB

The underlying theory of vector sequence extrapolation methods for linear and nonlinear problems is examined. It is shown that nonlinearity limits savings in total number of iterations to \(50 \%\) for strongly nonlinear problems when linear-based extrapolation methods are used. In support of this c