Naren: Create page

2026-10-16T19:28:18Z

Create page

New page

'''Brun's algorithm''' is an extension of continued fractions to more than one number.<ref name="brun1964euclidean"/><ref name="mandelbaum1961multiple"/>
It can be used to find [[EDO]]s that contain good approximations to given [[just]] ratios.

== Algorithm ==
Say we would like to find EDOs which have good approximations of 5/4, 3/2, and 2/1.
First, write the corresponding cents values, largest to smallest, in a vector <math>A_{0}</math>,

<math display="block">
A_{0} =
\begin{bmatrix}
1200.00 \\
701.96 \\
386.31
\end{bmatrix}
</math>

Now write <math>XA = A_{0}</math>, where to begin with <math>X</math> is the identity matrix and <math>A = A_{0}</math>,

<math display="block">
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1200.00 \\
701.96 \\
386.31
\end{bmatrix} \\
=
\begin{bmatrix}
1200.00 \\
701.96 \\
386.31
\end{bmatrix}
</math>

Each iteration of the algorithm transforms <math>X</math> and <math>A</math> such that
* We preserve <math>X A = A_{0}</math>
* The elements of <math>A</math> get smaller
* The first column of <math>X</math> gives a better EDO approximation of <math>A_{0}</math>

To do one iteration of the algorithm,
firstly subtract the second element from the first element in the cents vector <math>A</math>
and add the first column to the second column in the matrix <math>X</math>, giving

<math display="block">
\begin{bmatrix}
1 & 0 + 1 & 0 \\
0 & 1 + 0 & 0 \\
0 & 0 + 0 & 1
\end{bmatrix}
\begin{bmatrix}
1200.00 - 701.96 \\
701.96 \\
386.31
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
498.04 \\
701.96 \\
386.31
\end{bmatrix}
</math>

Secondly, sort the cents vector <math>A</math> and rearrange the columns of <math>X</math> in the corresponding order, giving

<math display="block">
\begin{bmatrix}
1 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
701.96 \\
498.04 \\
386.31
\end{bmatrix}
</math>

Repeating this process gives:

{| class="wikitable"
! <math>X</math> !! <math>A</math> !! Ratios
|-
| <math>\begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}</math>
| <math>\begin{bmatrix}1200.00 \\ 701.96 \\ 386.31\end{bmatrix}</math>
| <math>\begin{bmatrix}2/1 \\ 3/2 \\ 5/4\end{bmatrix}</math>
|-
| <math>\begin{bmatrix}1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}</math>
| <math>\begin{bmatrix}701.96 \\ 498.04 \\ 386.31\end{bmatrix}</math>
| <math>\begin{bmatrix}3/2 \\ 4/3 \\ 5/4\end{bmatrix}</math>
|-
| <math>\begin{bmatrix}2 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0\end{bmatrix}</math>
| <math>\begin{bmatrix}498.04 \\ 386.31 \\ 203.91\end{bmatrix}</math>
| <math>\begin{bmatrix}4/3 \\ 5/4 \\ 9/8\end{bmatrix}</math>
|-
| <math>\begin{bmatrix}2 & 1 & 2 \\ 1 & 1 & 1 \\ 1 & 0 & 0\end{bmatrix}</math>
| <math>\begin{bmatrix}386.31 \\ 203.91 \\ 111.73\end{bmatrix}</math>
| <math>\begin{bmatrix}5/4 \\ 9/8 \\ 16/15\end{bmatrix}</math>
|-
| <math>\begin{bmatrix}3 & 2 & 2 \\ 2 & 1 & 1 \\ 1 & 1 & 0\end{bmatrix}</math>
| <math>\begin{bmatrix}203.91 \\ 182.40 \\ 111.73\end{bmatrix}</math>
| <math>\begin{bmatrix}9/8 \\ 10/9 \\ 16/15\end{bmatrix}</math>
|-
| <math>\begin{bmatrix}5 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 0 & 1\end{bmatrix}</math>
| <math>\begin{bmatrix}182.40 \\ 111.73 \\ 21.51\end{bmatrix}</math>
| <math>\begin{bmatrix}10/9 \\ 16/15 \\ 81/80\end{bmatrix}</math>
|-
| <math>\begin{bmatrix}7 & 5 & 3 \\ 4 & 3 & 2 \\ 2 & 2 & 1\end{bmatrix}</math>
| <math>\begin{bmatrix}111.73 \\ 70.67 \\ 21.51\end{bmatrix}</math>
| <math>\begin{bmatrix}16/15 \\ 25/24 \\ 81/80\end{bmatrix}</math>
|-
| <math>\begin{bmatrix}12 & 7 & 3 \\ 7 & 4 & 2 \\ 4 & 2 & 1\end{bmatrix}</math>
| <math>\begin{bmatrix}70.67 \\ 41.06 \\ 21.51\end{bmatrix}</math>
| <math>\begin{bmatrix}25/24 \\ 128/125 \\ 81/80\end{bmatrix}</math>
|-
| <math>\begin{bmatrix}19 & 12 & 3 \\ 11 & 7 & 2 \\ 6 & 4 & 1\end{bmatrix}</math>
| <math>\begin{bmatrix}41.06 \\ 29.61 \\ 21.51\end{bmatrix}</math>
| <math>\begin{bmatrix}128/125 \\ 3125/3072 \\ 81/80\end{bmatrix}</math>
|-
| <math>\begin{bmatrix}31 & 3 & 19 \\ 18 & 2 & 11 \\ 10 & 1 & 6\end{bmatrix}</math>
| <math>\begin{bmatrix}29.61 \\ 21.51 \\ 11.45\end{bmatrix}</math>
| <math>\begin{bmatrix}3125/3072 \\ 81/80 \\ 393216/390625\end{bmatrix}</math>
|}

Here each row shows one iteration of the algorithm.
The Ratios column shows the ratios corresponding to the cents values in <math>A</math>
(from dividing ratios each time we subtract cents values).

The first column of each matrix <math>X</math> gives an EDO approximation to <math>A_{0}</math>.
For example, the matrix with first column <math>[31, 18, 10]</math> gives

<math display="block">
\begin{aligned}
\frac{1200}{31}
\begin{bmatrix}
31 \\
18 \\
10
\end{bmatrix}
&=
\begin{bmatrix}
1200.00 \\
696.77 \\
387.10
\end{bmatrix} \\
&\approx
\begin{bmatrix}
1200.00 \\
701.96 \\
386.31
\end{bmatrix}
\end{aligned}
</math>

== Code ==
The following Python code implements Brun's algorithm.

<syntaxhighlight lang="python">
import numpy as np

target_ratios = [5/4, 3/2, 2/1]

A = 1200 * np.log2(sorted(target_ratios, reverse=True))
X = np.identity(len(A), dtype=np.int64)

while X.max() <= 100:
print(f"{X}\n{A}\n")
A[0] -= A[1]
X[:, 1] += X[:, 0]
i = np.argsort(-A)
A = A[i]
X = X[:, i]
</syntaxhighlight>

== Other applications ==
[[Erv Wilson]] used the intervals generated by Brun's algorithm to construct scales.<ref name="wilson1995brun"/>

== References ==
<references>
<ref name="brun1964euclidean">
Viggo Brun, [https://www.anaphoria.com/brun-euclideanalgo.pdf Euclidean Algorithms and Musical Theory]. L'Enseignement Mathématique 10, 1964.
</ref>
<ref name="mandelbaum1961multiple">
[[Joel Mandelbaum]], [https://anaphoria.com/mandelbaum.html Multiple Division of the Octave and the Tonal Resources of 19-tone Temperament], Chapter 13, page 370. 1961.
</ref>
<ref name="wilson1995brun">
[[Erv Wilson]], [https://www.anaphoria.com/viggo3.pdf A Sequence of Constant Structures as Predicted by Brun's Algorithm]. 1995.
</ref>
</references>

== External links ==
* [https://narenratan.com/tools/bruntosaur/ bruntosaur] - Online Brun's algorithm calculator

Brun's algorithm - Revision history

Naren: Create page