Module Euclid

module Euclid: sig  end

Given two rational numbers a, b, euclid finds integers , y0 satisfying a * x0 + b * y0 = (a, b), where (a, b) denotes the greatest common divisor of a, b. For example, euclid 1547 560 equals (7, 21, -58)

The value of (a, b) is unchanged in the loop in euclid, since (a, b) = (a - (a/b)*b, b); thus, using (a, 0) = a, the first result of euclid computes (a0, b0). Other invariants are: c * a0 + e * b0 = a d * a0 + f * b0 = b Now it is obvious that a * x0 + b * y0 = (a, b).

module type Rat = sig  end

module type S = sig  end

module Make: functor (R : Rat) -> sig  end