𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The number of steps in the Euclidean algorithm

✍ Scribed by John D Dixon

Publisher
Elsevier Science
Year
1970
Tongue
English
Weight
378 KB
Volume
2
Category
Article
ISSN
0022-314X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the asymptotic analysis of the Euclid
On the asymptotic analysis of the Euclidean algorithm
✍ G.H. Norton πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 213 KB

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.

Approximation algorithms for the Euclide
Approximation algorithms for the Euclidean bipartite TSP
✍ Andreas Baltz; Anand Srivastav πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 214 KB

We study approximation results for the Euclidean bipartite traveling salesman problem (TSP). We present the first worstcase examples, proving that the approximation guarantees of two known polynomial-time algorithms are tight. Moreover, we propose a new algorithm which displays a superior average ca

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