The μEuclidean Algorithm

The μEuclidean algorithm is an integer relation algorithm [1]. Let

r₁, r₂, … r_k

be k real numbers, in short ⟨r|. They obey an integer relation if integer numbers m₁, m₂, ... m_k exist such that

r₁·m₁ + r₂·m₂ + ... + r_k·m_k = 0.

An integer valued matrix B is determined iteratively out of the input numbers ⟨r|. An integer relation is found if one of the entries of the product ⟨r|B is vanishing. A solution m₁, m₂, ... m_k can be read off from the corresponding column of the matrix B.

The μEuclidean algorithm can be used to determine multi-dimensional continued fraction expansions. Set r₁=1. An approximation of the remaining input numbers by fractions with a common denominator

r₂ ≈ n₂ / n₁, ... r_k ≈ n_k / n₁

can be extracted from the numbers n₁, n₂, ... n_k of any of the rows of the matrix B^-1, the inverse of the matrix B. The error associated to the ith row of B^-1 is stored in the ith component of the vector |Δ⟩. (The error is the maximum of |r_i - n_i /n₁|, i=1,...k.)


Input
Choose at least 2 input numbers (comma-separated):

⟨r| =
and the number of iterations:

Optionally, in the case of r₁= 1 and if the other input numbers are logarithms with a common basis a i.e. of the form r_i= log_a p_i =log p_i / log a, the basis may be noted here: a= Then, the errors in |Δ⟩ are given in units of Cent.

 

Output
To visualize integer relations vanishing entries of ⟨r|B are marked by a star (*) instead of a number i.e., more precisely, the corresponding absolute value ⟨r|B B^T|r⟩^½ is smaller than 10^-10.

⟨r|B=

B =


B^-1 =


|Δ⟩ =

Remarks
The mathematical constants and functions defined in JavaScript [e.g. PI, E, +, -, *, /, log(x), exp(x), sin(x), cos(x), pow(x,n)] can be used to specify the input numbers. For example, the input numbers

⟨r| = 1, log(5/4)/log(7/4), log(2/1)/log(7/4)

are relevant for representing the major third (5/4), the harmonic seventh (7/4), and octaves (2/1) by integer intervals within an equal temperament (ET) scale. After 10 iterations the second row of B^-1 consists of the numbers 25, 10, 31, i.e. log(5/4)/log(7/4)=0.399... ≈ 10/25=0.4 and log(2/1)/log(7/4)=1.239... ≈ 31/25=1.24 or, in other words, Huygens' 31-ET scale is recoverd where the third is represented by the 10th interval, the harmonic seventh by the 25th interval and the octave by the 31th interval. The ratio (-6)/(-5)=6/5=1.2 obtained from the first row is a less precise approximation of the last input number log(2/1)/log(7/4). If the basis in the input field is specified, a=7/4, the entries in |Δ⟩ are given in units of Cent: the error of the 31-ET scale turns out to be only 1.344 Cent (second line of |Δ⟩).

The internal accuracy of JavaScript (16 decimal digits) may limit the number of iterations. The results are biased by rounding errors if, as a rule of thumb, the size of any of the elements of the matrix B^-1 exceeds 10 digits.


Reference
[1] H. Heßling, On the Euler Scale and the μEuclidean Integer Relation Algorithm, Journal of Mathematics and Music 5:3, 195-215 (2011). Preprint (fixed a few misprints in the journal).