# .

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 7th 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 r1
b/r1 gives a remainder of r2
r1/r2 gives a remainder of r3
...
rn-1/rn gives a remainder of rn+1
If rn/rn+1 gives no remainder

then rn+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 36x1 + 15x2 = 0 that has an integer solution x1 = 5 and x2 = -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 (x1,x2,...,xn) try to find if integers a1, a2, ..., an (not all 0) exists such that:

a1x1 + a2x2 + ...+anxn = 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

References

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

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

Ancient Greece

Medieval Greece / Byzantine Empire

Modern Greece

Science, Technology, Arts, , Warfare , Literature, Biographies, Icons, History

Greece

World

Hellenica World

Index