Der Algorithmus von Euklid

Isaac Newton's assistant at Cambridge claimed that during five years he saw Newton laugh only once. Newton had loaned a copy of Euclid to an acquaintance, and the gentleman asked what use it was to study Euclid, "upon which Sir Isaac was very merry". Euclid's Plan and Proposition 6

Integer Relations

Euclid is known as author of the Elements a book about geometry that had an immense influence in science (Probably the most important scientific book ever written). But Euclid also is probably the first who developed algorithms much earlier than Al Khwarizmi from which the name algorithm is derived. Euclid used algorithms for the construction of geometric objects and thus can be considered to be the first computational geometrist.

Euclid provided the first algorithm for the calculation of the greatest common divisor gcd(a,b) of two integers a and b. Euclid provided the synonymous algorithm in the 7^th book (chapter), Proposition 2 of the Elements.

As an example what is the greatest common divisor of 36 and 15?

We calculate 36/15 which gives 2 and a remainder 6
Then 15/6 gives 2 and a remainder of 3
6/3 gives 2 and and no rest.

We take the last non zero remainder, which is 3 and this is the greatest common divisor of 36 and 15, i.e. gcd(36,15) = 3.

With a > b the steps of Euclid's algorithm are:
a/b gives a remainder of r₁
b/r₁ gives a remainder of r₂
r₁/r₂ gives a remainder of r₃
...
r_n-1/r_n gives a remainder of r_n+1
If r_n/r_n+1 gives no remainder

then r_n+1 is the gcd of a and b. If the first step produced no remainder, then b is the gcd.

Two numbers a,b with gcd(a,b)=1 are called relative prime. Euclid's algorithm can be used to reduce a faction a/b to a simpler fraction. We take

a/b = (a/gcd(a,b)) / ( b/gcd(a,b)) or for our example 36/15 = (36/3) / (15/3) = 12/5.

This can be consider to be related to the equation 36x₁ + 15x₂ = 0 that has an integer solution x₁ = 5 and x₂ = -12.

The algorithm is very efficient except if a, b are two Fibonacci numbers in sequence, which also explains why the golden ratio is the most irrational number! The run time complexity is O(( log a)( log b)) bit operations. *

This algorithm belongs to the so called class of integer relation algorithms which for a given set of real numbers (x₁,x₂,...,x_n) try to find if integers a₁, a₂, ..., a_n (not all 0) exists such that:

a₁x₁ + a₂x₂ + ...+a_nx_n = 0.

Helaman Ferguson and Rodney Forcade were able to provide such an algorithm in 1977 that is considered one of the top algorithms of the last Century that generalizes Euclid's algorithm for the case n=2 after 2300 years. At present time the PSLQ algorithm by Ferguson is the most powerful such algorithm.

These algorithms allow the discovery of unknown mathematical identities and the trend in mathematics is the use of computing power to detect additional with visualization tools relations that otherwise cannot be obtained or extremely unlikely to be found. They use Fast Fourier Transform algorithms used to multiply efficiently very large integers. This show that we have entered a new period where computers become continuously more important even if mathematicians are required to produce the relevant input and to think about the output of the calculations performed by the computers.

The physicist David J. Broadhurst used the PSLQ algorithm to discover unexpected relations in quantum field theory.

* Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n". f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n. See: Dictionary of Algorithms and Data Structures

A geometrical version of Euclid's algorithm was provided by Hipassos who showed that the geometric version of it will never stop if we consider the ratio of the diagonal/side length of a regular Pentagon.

References

Dongarra and Sullivan, Top Ten Algorithms of the Century, Computing in Science and Engineering, January/February 2000.

LINKS

The Euclidean Algorithm

D. J. Broadhurst, Massive 3-loop Feynman diagrams reducible to SC* primitives of algebras of the sixth root of unity. http://xxx.lanl.gov/abs/hep-th/9803091

From Euclid to Gregory