𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the asymptotic analysis of the Euclidean algorithm

✍ Scribed by G.H. Norton

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
213 KB
Volume
10
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

Let N > 2 and 8 > 0. For uniformly distributed integers in the interval I-1, N], the Euclidean algorithm requires an average of 121n2( 1

divisions, where C is Porter's constant.

πŸ“œ SIMILAR VOLUMES

On the complexity of the extended euclid
On the complexity of the extended euclidean algorithm (Extended Abstract)
✍ George Havas πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 92 KB

Euclid's algorithm for computing the greatest common divisor of 2 numbers is considered to be the oldest proper algorithm known ([10]). This algorithm can be amplified naturally in various ways. The GCD problem for more than two numbers is interesting in its own right. Thus, we can use Euclid's algo

A Supplement to J. Shallit's Paper β€œOrig
A Supplement to J. Shallit's Paper β€œOrigins of the Analysis of the Euclidean Algorithm”
✍ Peter Schreiber πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 166 KB

As early as the 16th century, Simon Jacob, a German reckoning master, noticed that the worst case in computing the greatest common divisor of two numbers by the Euclidean algorithm occurs if these numbers are equimultiples of two consecutive members of the Fibonacci sequence.