Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T13:05:55.364Z Has data issue: false hasContentIssue false

Is the Euclidean Algorithm Optimal Among its Peers?

Published online by Cambridge University Press:  15 January 2014

Lou Van Den Dries
Affiliation:
University of Illinois, Department of Mathematics, 1409 W. Green Street, Urbana, IL 61801, USA E-mail: , vddries@math.uiuc.edu
Yiannis N. Moschovakis
Affiliation:
Department of Mathematics, University of California, Los Angeles, CA, 90095-1555, USA E-mail: , ynm@math.ucla.eduDepartment of Mathematics, University of Athens, Athens, Greece

Extract

The Euclidean algorithm on the natural numbers ℕ = {0,1,…} can be specified succinctly by the recursive program

where rem(a, b) is the remainder in the division of a by b, the unique natural number r such that for some natural number q,

It is an algorithm from (relative to) the remainder function rem, meaning that in computing its time complexity function cε (a, b), we assume that the values rem(x, y) are provided on demand by some “oracle” in one “time unit”. It is easy to prove that

Much more is known about cε(a, b), but this simple-to-prove upper bound suggests the proper formulation of the Euclidean's (worst case) optimality among its peers—algorithms from rem:

Conjecture. If an algorithm α computes gcd (x,y) from rem with time complexity cα (x,y), then there is a rational number r > 0 such that for infinitely many pairs a > b > 1, cα (a,b) > r log2a.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable