黄金比率とフィボナッチ数列 part2
フィボナッチと黄金比率
さて、このフィボナッチ数列は、応用コーナーのウサギとフィボナッチで取り上げましたが、フィボナッチ数列の数字と数字の比率を計算すると面白いことが分かります。まずはフィボナッチ数列を生成してみましょう。
1 1 2 3 5 8 13 21 34 55 89
このフィボナッチ数列の隣り合う数字を除算してみます。
2÷1＝2
3÷2＝1.5
5÷3＝1.66667
8÷5＝1.6
13÷8＝1.625
:
何だかある数字に近づいているようです。面倒なのでrpnで計算させてみましょう。
1
2
1.5
1.66667
1.6
1.625
1.61538
1.61905
1.61765
1.61818
やはり、どこかで見た数字じゃありませんか？そうです。黄金比率にそっくりですね。それでは、計算した結果がどのように収束していくのかグラフで確かめて見ましょう。
>rpn 1 -c rownum <tmp | xyp -x,10 -y1.5,1.7 -s1,.1 -m | npd
^y 1.7
|
| *
|
|
| *
|･･････････････････････････*･･･*･･･*･･･* 黄金比率(τ)
- 1.6 *
|
|
|
|
|
| x
| 10
+1.5---|---*---|---|---|---|---|---|--->
急速に黄金比率に近づいているのが分かります。最終的にどのような値になるのか、20項目まで繰り返し計算してみましょう。
1
2
1.5
1.66667
1.6
1.625
1.61538
1.61905
1.61765
1.61818
1.61798
1.61806
1.61803
1.61804
1.61803
1.61803
1.61803
1.61803
1.61803
1.61803
大体15項目くらいで、黄金比率の1.61803に収束しているようです。フィボナッチと黄金比率は一見関係がなさそうに思えますが、互いに関連しあっていたのですね。
黄金比率は美しいという感覚を与えてくれるだけではありません。植物が葉を出す方向も黄金比率に従っています。植物にとっては光合成は死活問題ですから、葉の出す方向は大切です。円周を1対1.618に分割した部分から葉を出すのが最も葉が重ならずに日光を多く受けることができるのだそうです。そして、植物が生長して幹を伸ばし葉を広げていきます。上からその植物を見ると、葉の位置は螺旋構造になっているというから驚きです。
黄金比率を使った探索
最後に現実的な話です。黄金比率は様々な業種で応用されているようで、面白いものに水道管の水漏れ調査があるそうです。A地点からB地点まで延びている水道管のどこかに水漏れがあるとします。その場所を探し当てるにはどのようにして探すのが一番効率的かを考えます。
A どこかで水漏れ B
AからBまで順に調べていくのは最も効率が悪く、たまたま水漏れ箇所がAに近ければいいですが、逆にBに近いと一番遅く発見することになります。通常、このような場合にはバイナリーサーチ(2分探索法)が使われます。
AとBの真ん中をCと決めて、均等分割した左右のどちらに水漏れがあるかを探知します。左にあることが分かれば、次はAとCとの真ん中をDと決めて再度、左右をチェックします。これを水漏れ箇所が見つかるまで繰り返します。AからBまで100箇所調べるポイントがあるとすれば、最悪でも7回で水漏れ箇所が発見できます。
この手の探索では2分法が一番ベストなはずですが、AとBの分割地点を真ん中ではなく黄金比率に準じた区分けにすればより早く発見できるという話があります。
本来、黄金分割による探索法は単峰性のある関数の極大･極小値を探し出す方法なのですが、このようなケースにも効果はあるのでしょうか。シミュレーションしてみましょう。まずは均等分割による2分探索法です。
探索法の違いをシミュレーション
シミュレーション方法ですが、まず1から100までの数列を用意します。次に無作為に1から100までの数字を選んでから、2分探索で数字を何回で見つけられたかを記録します。100回シミュレーションして平均発見回数を計算することにします。最悪値は7回ですから、7回以下になるはずです。
ここで、binaryというrpnプログラムを用意します。binaryプログラムは与えられた昇順の数列から特定の数値を2分探索します。出力は以下のように探知した位置と探索回数になります。
3 7
上の例では、7回の探索で左から3番目の位置に発見したことを示しています。このプログラムを使って以下のように100回コマンド入力することで、ファイルのcount.binに100回分の探索結果が格納されます。
>rpn 100 -c seq' | rpn 1 100 100 ? -c binary >>count.bin
:
(中略)
:
>rpn 100 -c seq' | rpn 1 100 100 ? -c binary >>count.bin
次に均等分割による2分法ではなく黄金比率で分割して数字を探索します。上記と同様にgoldenというrpnプログラムを用意します。プログラムの仕様はbinaryと同じで、異なるのは探索時の分割方法だけです。
それでは、同様に100回繰り返します。
>rpn 100 -c seq' | rpn 1 100 100 ? -c golden >>count.gol
:
(中略)
:
>rpn 100 -c seq' | rpn 1 100 100 ? -c golden >>count.gol
これでファイルのcount.golに探索結果が格納されました。それぞれを横結合して、基本統計量を計算してみましょう。
デ ー タ 100 100
最 小 値 6 5
最 大 値 7 8
範 囲 1 3
合 計 値(Σ) 678 682
平 均 値(μ) 6.78 6.82
分 散 値(σ2) 0.1716 0.4676
標準偏差(σ) 0.414246 0.683813
分 散 値(ｓ2) 0.173333 0.472323
標準偏差(ｓ) 0.416333 0.687258
歪度(ａ3≒0) -1.35185 0.0573446
尖度(ａ4≒3) 2.82751 2.47542
変動係数(ν) 0.0614061 0.100771
均等分割の平均探索回数が6.78回に対し、黄金分割による方法が6.82回です。黄金分割のほうが探索に多くの回数が掛かっています。どうも話が違いますね。幹葉表示による分布形状で見てみましょう。
6 | 0000000000000000000000
7 | 0000000000000000000000000000000000000000000000000000000000000
00000000000000000
>rpn x _ <count.gol | rpn 10 * -c stemleaf
5 | 0
6 | 0000000000000000000000000000000
7 | 00000000000000000000000000000000000000000000000000000
8 | 000000000000000
均等分割による探索はほとんどが7回に集まったピークの高い分布です。対して、黄金分割による探索のほうは6回から8回に渡ってバラつきが大きく、なだらかな分布になっています。どうも黄金分割は当たり外れのある探索という感じは否めません。
このシミュレーションでは、均等分割による探索の78%が7回探索で、6回探索が22%です。黄金分割の場合、68%が7回以上の探索で、逆に32%が6回以下の探索です。
関連記事として、応用コーナーにウサギとフィボナッチがあります。興味のある人は閲覧ください。
rpnプログラムを実行するには、rpn試用版かrpn標準版が必要です(バージョンの違いはこちら)。
pasteは講座サポートで公開されています。fold, seq'はユーティリティーパッケージに同梱されています。statinfo, stemleafはrpnマイスターパッケージに同梱されています。nullはカレンダー・システムパッケージに同梱されています。rownumはカンタン分析パッケージに同梱されています。xypとnpdはrpnの姉妹ソフトウェアです。詳しくはプロダクトを参照ください。
/