✦ LIBER ✦

A Double-Digit Lehmer-Euclid Algorithm for Finding the GCD of Long Integers

✍ Scribed by Tudor Jebelean

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 316 KB
Volume: 19
Category: Article
ISSN: 0747-7171
DOI: 10.1006/jsco.1995.1009

No coin nor oath required. For personal study only.

✦ Synopsis

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 exiting the partial cosequence computation. Also, additional speed-up is achieved by approximative GCD computation. The combined effect of these improvements is an experimentally measured speed-up by a factor of 2 for operands with 10032 -bit words.

📜 SIMILAR VOLUMES

A carry-free algorithm for finding the g

A carry-free algorithm for finding the greatest common divisor of two integers

✍ George B. Purdy 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 503 KB

We investigate a variant of the so-called "binary" algorithm for finding the GCD (greatest common divisor) of two numbers which requires no comparisons. We show that when implemented with carry-save hardware, it can be used to find the modulo B inverse of an n-bit binary integer in a time proportion