Euclidean Rhythm ユークリッドリズムとは
はじめに
ユークリッドリズムとは、2つの数字からとあるアルゴリズムにより生成されるリズムです。2004年にGodfried Toussaintによって発見され、論文『The Euclidean Algorithm Generates Traditional Musical Rhythms』で発表されました。そのリズムを生成するアルゴリズムとは、2つの数字の最大公約数を求めるユークリッド互除法と同じ構造をもつBjorklund’s algorithmと同じです。ユークリッドの互除法により、ユークリッドリズムの強拍は可能な限り均等に分布します。この論文では、世界の伝統的な音楽のリズムの多くはこのアルゴリズムによって生成されると説明しています。また、ユークリッドの互除法・ユークリッドリズム・Bjorklund’s algorithm・Euclidean stringsに共通する構造や、ユークリッドリズムはEuclidean stringsにより3つのグループに分類されることも説明しています。
ユークリッドリズムを体感する
ユークリッドリズムは、2つの数字から生成されるリズムです。それはどのようなリズムなのでしょうか？ だれでもユークリッドリズムを得られるようにWebページを作ってみました。
https://hhyyg.github.io/miso.5tone/pages/euclidean/index.html
マウスを縦横に動かすと、2つの数字（左上のE(a, b)と表示されている部分）を変更できます。クリックすると対応するリズムが1回だけ再生されます。
この実装のコードはGitHubにあります：https://github.com/hhyyg/miso.5tone
下の図は、例として3と8からユークリッドリズムを生成したときの図です。
2行目の[1, 0, 0, 1, 0, 0, 1, 0]は、生成されたリズムを1と0の2進数の数列で表したものです。8個の数列に、3個の1があります。リズム譜で表すと以下のようになります。
8/8拍子だと見慣れないかもしれません。これを2/4拍子にして、0 は休符または弱拍にすると、見慣れたリズムが現れます。
この3と8から生成されたリズムは、有名なリズムの1つであるハバネラです。
このように、ユークリッドリズムは2つの数字から2進数の数列を生成して得られます。それぞれの1は限りなく等間隔に配置されます。また、3と8、8と3のユークリッドリズムは同等です。
ユークリッドリズムはこのように表記します：E(3, 8) = [1, 0, 0, 1, 0, 0, 1, 0]。先の図1で表示されている"332"とは、1と1の間隔を表すベクトルの数列を表し、"Euclidean strings: No" はその"332"がEuclidean stringsではないことを表しています。これが何を意味するかは後述します。右側の円と多角形の図は、[1, 0, 0, 1, 0, 0, 1, 0] の点を12時の方向から等間隔に配置し、1をつないで多角形を描画しています。
さて、私が作ったWebサイトが鳴らす音はかっこよくありません…。"Euclidean Rhythm"をGoolgleやYouTubeで検索すると http://www.groovemechanics.com/euclid/ こちらのようにかっこいいリズムに出会えます。何か変わったリズムが欲しいときは、2つの多面サイコロを転がすのもいいかもしれません。
ユークリッドリズムの求め方
2進数の数列の長さをn、1の個数をkとして、[0, 1, 0, ...] という数列を生成する場合、1を限りなく等間隔に配置するためにはどうすればよいでしょうか？ この答えが、ユークリッドリズムの求め方です。
身近に例えると、期間10日間で4個のプリンを食べるとき、できるだけ楽しみ度を平坦にするには、何日置きに食べればよいか？ということです。こうやって食べるよりも：[1, 0, 1, 0, 1, 0, 1, 0, 0, 0]、こうやって食べた方が：[1, 0, 0, 1, 0, 1, 0, 0, 1, 0]、長く楽しめるよね最後の3日間辛いね、という話です。ブレゼンハムのアルゴリズムを思いついた方は正解です。
もしnがkで割り切れる場合、例えばn = 6, k = 2の場合は、答えは簡単です。6/2 = 3より、答えは[1, 0, 0, 1, 0, 0]で明らかです。
n, kが互いに素である場合は、以下のフローで求めます。
例として、 n = 8, k = 3とします。3つの1と、(8-3)つの0で構成される8 bitの数列を、先頭に1を詰めて作成します。
[1, 1, 1, 0, 0, 0, 0, 0]
0をそれぞれの1の後ろに左から配置します。
[1, 0] [1, 0] [1, 0] [0] [0]：（2 bit の数列が 5 つでき、1 bit の数列が 2 つあまりました）
余ったほうの数列を、それぞれの[1, 0] の後ろに配置します。
[1, 0, 0] [1, 0, 0] [1, 0]：（3 bit の数列が 2 つでき、2 bit の数列が 1 つあまりました）
あまりの数列が 1 つであるとき、またはあまりがない状態のとき、この処理を終了します。最後に、すべての数列を分解し、1 つの数列にします。
[1, 0, 0, 1, 0, 0, 1, 0] →①
これが8と3から生成されるユークリッドリズム：E(3, 8) = [1, 0, 0, 1, 0, 0, 1, 0] です。これを実装したコードはここにあります。
補足として、最後のあまりが 1 つである状態のときは、処理を終了せずにもう1回ステップを進めることもできますが、無駄な処理なので省きます。つまり、
[1, 0, 0] [1, 0, 0] [1, 0]：（3 bitの数列が2つでき、2 bitの数列が1つあまっている状態）
本当はここで終了しますが、さらに次の処理を進めることもできます。
[1, 0, 0, 1, 0] [1, 0, 0]：（5 bitの数列が1つでき、3 bitの数列が1つあまりました）
得られる数列は、[1, 0, 0, 1, 0, 1, 0, 0] です。これは、①の数列[1, 0, 0, 1, 0, 0, 1, 0] を回転したものなので、繰り返されるリズムの文脈では同じものです。なので、無駄な最後の処理は行わず、あまりが1か0になったときに処理を終了します。
この求め方は、核物理学の文脈における”Timing Systems in Neutron Accelerators” の問題を解決するBjorklund’s algorithmと同じものだそうですが、よくわかっていません。（これもまた等間隔にパルスを生成するとかなんとか）
ユークリッドの互除法との関係
先のユークリッドリズムの求め方（= Bjorklund’s algorithm）は、ユークリッドの互除法と同じ構造である、繰り返し減算形式の除法を使用します。ここで、ユークリッドの互除法のアルゴリズムを確認し、ユークリッドリズムを求めるステップと、ユークリッド互除法のステップから共通点を確認してみます。
ユークリッドの互除法は、2つの数字の最大公約数を求めるアルゴリズムです。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。 ユークリッドの互除法 - Wikipedia
a, bの最大公約数を求めるときは、a = q * b + rをrが0になるまで続けます。このとき、qを必ず1として計算したとき、つまりで除法はなく繰り返し減算形式で計算したとき、先のユークリッドリズムの求め方と同じ構造になります。
たとえば、a = 5, b = 3としてa, bの最大公約数を求める場合、a = q * b + r のステップは次のようになります。
5 = 1 * 3 + 2 3 = 1 * 2 + 1 2 = 1 * 2 + 0
このステップを、(a + b)とbのユークリッドリズム、つまり8と3のユークリッドリズムを求めるステップと照らし合わせると以下のようになります。
| 5と3の最大公約数を求めるステップ | 8(= 5+3)と3のユークリッドリズムを求めるステップ |
|---|---|
| （不要）8 = 1 * 5 + 3 | [1, 1, 1, 0, 0, 0, 0, 0] |
| 5 = 1 * 3 + 2 | [1, 0] [1, 0] [1, 0] [0] [0] |
| 3 = 1 * 2 + 1 | [1, 0, 0] [1, 0, 0] [1, 0] |
| 2 = 1 * 1 + 1 | （不要）[1, 0, 0, 1, 0] [1, 0, 0] |
| 1 = 1 * 1 + 0 | （不要）[1, 0, 0, 1, 0, 1, 0, 0] |
左の列の太字と、右の列の数列の数が対応していることがわかります。（不要）とあるステップは、本来は無駄なステップですがそれぞれのロジックに沿って処理したステップです。
おまけとして、7と4の場合は次のようになります。
| 7と4の最大公約数を求めるステップ | 11(= 7+4)と4のユークリッドを求めるステップ |
|---|---|
| （不要）11 = 1 * 7 + 4 | [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] |
| 7 = 1 * 4 + 3 | [1, 0] [1, 0] [1, 0] [1, 0] [0] [0] [0] |
| 4 = 1 * 3 + 1 | [1, 0, 0] [1, 0, 0] [1, 0, 0] [1, 0] |
| 3 = 1 * 1 + 2 | （不要）[1, 0, 0, 1, 0] [1, 0, 0] [1, 0, 0] |
| 2 = 1 * 1 + 1 | （不要）[1, 0, 0, 1, 0, 1, 0, 0] [1, 0, 0] |
| 1 = 1 * 1 + 0 | （不要）[1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0] |
このように、nとkのユークリッドリズムのアルゴリズムは、(n - k)とk の最大公約数を求めるユークリッドの互除法と同じ構造です。
本来ユークリッドの互除法は、繰り返し減算形式ではなく除法で最大公約数を求めます。同じようにユークリッドリズムも、先に示した求め方ではなく除法によりいくつかのステップを省略できます。例えば、9と2のユークリッドリズムを求めるときは、7個の0を1つずつ配置するのではなく、3つの0を一度で配置できるでしょう。
Euclidean stringsとの関係
ユークリッドリズムは、Euclidean stringsにより3つのグループに分けられます。論文ではその分類の結果を”a tantalizing pattern”と興味深いことを示していましたが、自分では、その分類の結果が何を表しているかを理解できませんでした。
その3つの分類は、以下のようになります。
- グループ1. Euclidean stringsであるユークリッドリズム
- グループ2. Euclidean stringsではないが、Euclidean stringsの逆順であるユークリッドリズム
- いろいろなところで広く使われている
- グループ3. Euclidean stringsでもなく、Euclidean stringsの逆順にも該当しないユークリッドリズム
- 西アフリカ、中部アフリカで使われる
この分類に該当するリズムについて私の解釈です。詳細は、論文の「6. Euclidean strings」にリストがあります。
ユークリッドリズムがEuclidean stringsであるかとはどういうことか？ まずEuclidean stringsについて説明します。
Euclidean stringsとは
おそらく数学の数の組み合わせの分野における言葉です。ある整数で構成される数列をPとし（例: P = 187345）、そのPにおいて、最初の数字を+1、最後の文字を-1した数列を T(P)とします（例: P = 187345 なら、T(P) = 287344）。このときPとT(P)が、回転すれば一致する数列である場合、そのPをEuclidean stringsといいます（187345と287344は回転させても一致しないので、187345はEuclidean stringsとは言えない）。
回転という操作の意味は、123456の場合、開始点1つ右にずらすこと、つまり234561にすることを意味します。345612は、123456を開始点を右に3つずらした数列です。
Euclidean stringsである例の1つは、1221222です。P=1221222のときT(P)=2221221となり、この2つの数列は回転すれば一致した文字列です。（1221222の開始点を右に4つずらせば2221221になる。）
Euclidean stringsの性質として、Euclidean stringsは Pの数列の和（例: P=1221222の場合は12）と、Pの数列の長さ（例: P=1221222の長さは7）が互いに素のときのみ存在し（例: 7と12は互いに素）、もしEuclidean stringsであるときはそれは唯一の数列である（つまり長さ7の数列であるEuclidean stringsは1221222しか存在しない）といいます。しかし、この性質の説明があっているかどうか自信がありません…。
ユークリッドリズムのどこをEuclidean stringsとして判別するか
ユークリッドリズムは、例えば7と12だと、E(7, 12)=[1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0]と1と0の数列ですが、この数列はEuclidean stringsかどうかの対象でありません。1と1の各距離の数値の数列を対象とします。例えばE(7, 12)=[1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0]の場合は、2122122です。これは、図形で表した場合の各辺の数値（のベクトル）の列です。
2122122はEuclidean stringsでもなく、逆順にしてもEuclidean stringsではないため（2122122と3122121は回転しても同じにならない）、7と12のユークリッドリズムはグループ3の「Euclidean stringsでもなく、Euclidean stringsの逆順にも該当しないユークリッドリズム」に属します。
グループ1の「Euclidean stringsである ユークリッドリズム」の例の1つはE(3, 7) = [1, 0, 1, 0, 1, 0, 0]の223です。グループ2の「逆順の Euclidean stringsであるユークリッドリズム」の例の1つは、E(3, 4) = [1, 0, 1, 1]の211です。211はEuclidean stringsではありませんが、逆にした112はEuclidean stringsです。
さいごに
ユークリッドリズムについて冒頭の論文を読んで分かったことを書きました。きっかけは、hundredrabbits/Orca: Esoteric Programming Language に u オペレーターとしてユークリッドリズムが実装されたことでした。この実装では、ブレゼンハムのアルゴリズムにより1行でユークリッドリズムを生成しています。
分からないこととしては、Bjorklund’s algorithmとEuclidean stringsについて、あまり情報を得られず、それの意味の理解が正しいかと、各分野での立ち位置の雰囲気が分かっていません。また、ライブコーディング（音楽）についてユークリッドリズムがどのような立ち位置であるかも知りたいところです。
