■ HOME

■ 千年後に兎が何羽いるかフィボナッチさんに答える
     Answer to Fibonacci how many rabbits will be 1000 years later

「フィボナッチ数」とか「フィボナッチ数列」というのを聞いたことがあるだろうか

私も巻貝でよく出てくるけど。。。よく分からんな。。。
数列って何だよ？素数って数列なのかな？ぐらいのレベルです

  巻貝の螺旋を描いた美しい渦
  ヒマワリの花の中心部分や
  ロマネスコの渦が並んだ吸い込まれるような美しい模様

この美しい螺旋がフィボナッチ数列と同じもの。
ということらしいです。

はるか昔2005年に3Dの「巻き貝」を作成するにあたって
ベルヌーイの螺旋(Daniel Bernoulli's Spiral)を使った事はありましたが。。。

他にも色々当てはまるものがあるようです
ちょっと調べます。。。

■フィボナッチ数のウィキペディア（Wikipedia）
https://ja.wikipedia.org/wiki/フィボナッチ数

を見ると。。。（2020年）
イタリアの数学者レオナルド・フィボナッチ（ピサのレオナルド）に因んで名付けられた数である。

数学者の名前だったんですねー

でも、インド学者ヘーマチャンドラ (Hemachandra) の方が50年くらい前に書していたようです
早かったにもかかわらず
「フィボナッチ数」が普及してしまった現在
今更「ヘーマチャンドラ数」にはならないのがちょっと可哀そうな気もします。。。

ここでフィボナッチが出した問題が
この「フィボナッチ数」が生まれた元になっているようです。
引用です。Wikipedia を見た方はすっとばしてください

-------------------------------------------------------------------
■ 兎の問題
レオナルド・フィボナッチは次の問題を考案した。
・ 1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。
・ 兎が死ぬことはない。
・この条件の下で、産まれたばかりの1つがいの兎は1年の間に何つがいの兎になるか？

つがいの数は次の表のようになる。どの月のつがいの合計も、その前の2つの月での合計の和となり、フィボナッチ数が現れていることが分かる。

-------------------------------------------------------------------
表をみれば一目瞭然ですが12か月後の合計は233羽となります
問題の通りに上から順に数を埋めて足してゆけば数が分かります。

Wikipedia ではその下に丁寧にもその数を知るための 式 が書き込まれています
式 はいくつかあって表現をかえたものや見方をかえて求めたり色々です
中ほどには　プログラミング言語での実装　のサンプルソース例もあります。
ちょっとした関数や式で数値を求められるなら。。。ちょっと試してみよう
と思い立ったわけですね

再帰的処理の例としてよく紹介される。以下はPython言語での例。
例1（再帰的処理による実装例）
　関数
例2（ループ処理による実装例）
　関数
例3（一般項による実装例）
　関数は wikipedia でみてね

■再帰的処理。。。うみゅーなんのこっちゃｗ

出足からくじかれましたｗ　で、調べました。
例の後に書いてあるように実用的でないのでメモしながら処理をする。
でもまぁ大きな数字でなければOKみたいなので、とりあえずメモなしでやります
例は python なので C に直します。
といってもほぼ変わりませんが。。。

//■フィボナッチ数列：漸化式の定義
//再帰的処理による（同じ計算を何度もするので時間がかかる）
#include <stdio.h>
#include <math.h>
int fibonacci(int n) {
  if(n==0 || n==1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

なんて簡単なんでしょう！！

main 関数から下記のようなかんじで呼び出して f が 12ヵ月後の兎のつがいの数の答えです
int main() {
  int n = 12;//月
  int f;
  f = fibonacci(n);
  printf("fibonacci(%d) = %d\n", n, f);
  return 0;
}

で、試したくなるのがじゃあ 50 ヵ月後はどうなの？
ってやるとなかなか帰ってこない。。。遅い。。。
これは確かにアカン。。。

で、ならメモはどうなの？
ってか何をどうメモしてどう処理するの？
ググったらサンプルがあったので実行したら確かに速いです。
速いんですが。。。この再帰的処理って必要ある？
用途によってはあるようですが。。。「フィボナッチ数」で必要あるかなぁ。。。

ウィキペディアの表のところに書いてあった
　「どの月のつがいの合計も、その前の2つの月での合計の和となり、フィボナッチ数が現れていることが分かる。」
この見方が原因だな。。。だから再帰的処理とかやるんだ。。。
プログラムの最初から 0 なら 0 を返して、 1 なら 1 を返すってのが不自然極まりない

表に戻って最初に記載されているのは式だ

　フィボナッチ数列の一般項は次の式で表される
　　＜式は wikipedia で見てね＞
この式は1843年にビネ (Jacques Philippe Marie Binet) が発表したことからビネの公式と呼ばれるが、
　それ以前の1730年（ド・モアブル）・1765年（オイラー）にも発表されており、ビネは最初の発見者ではない。

って、ここでも最初の人じゃあないんだｗ。。。と思いつつ
この 式 を書けばいいんでは？
という単純発想で C にしてみる。。。

//■フィボナッチ数列：一般項の式
double fibonacci(int n) {
  double Fn;
  double fai = (1+sqrt(5.0))/2;
  Fn = (pow(fai, n)-pow((0-fai), 0-n))/sqrt(5.0);
  return Fn;
}

とても簡単だね。

ビネ、モアブル、オイラーさんありがとう！
しかも行ったり来たりしないから速いし！

と思ったのだが。べき乗や平方根を扱うので小数点が出る。。。
しかも double を使うから誤差や丸め込みが出る。。。
小さい数字なら問題ないが大きい数字になってくると正確な数字を出力できないかもしれない。。。
しかも double の桁数の限界もある
という危惧があった。。。

■ double の悩み

double の最大値 = 1.797693e+308
10の308乗まで計算
計算はするが表示桁数は頭から 19桁？long（8バイト）くらいまでで、更に計算となると桁数を落とさないとダメだ。。。
誤差を丸め込まれたまま計算したらおかしな数字になる

fibonacci(105) = 3928413764606871732000

こんな感じで末尾に 000 ゼロが3つにされ省略される。。。
桁数が大きくなったら e+ を付けらるだけでこのまま計算しても無意味だ
unsigned にしても同じ。。。

元々、一般項の式を作ったものの平方根を使ってる時点で
フィボナッチさんの問題にそったやり方ではない
兎の話をしているのに 24. 061963...羽 とかあり得ない。（数値は適当です）
「大体 24羽です」（PC）
そんな中途半端な兎はいないよ！！

仕切り直して

もっと単純で問題通り、順にやっていけばいい
頭から足していくだけなんだから。。。と思い作ってみる

誰だったか忘れたがプログラムは思想だ
と言っていたのを思い出す
その人のものの捉え方や考え方の思考によってどう処理されるか
それが反映されるという事なのだと思う

閑話休題

//フィボナッチ数列：順を追って繰り返しで足す（ループ処理だが例2とは違う）
double fibonacci(long n) {
  long m;//月
  double t0 = 0;//0か月産まれたばかりのつがい
  double t1 = 0;//1か月後
  double t2 = 1;//2か月後

  //最初のつがいを2か月後の産まれた月にする
  for (m = 0; m <= n; m++) {
    t2 = t2 + t1;
    t1 = t0;
    t0 = t2;
    printf("m=%ld月 t0= %.0f t1= %.0f t2= %.0f \n", m, t0, t1, t2);
  }
  return t2;
}

いいね。
シンプルで簡単です。これでいいんじゃないかな

頭の出足はちょっと悩みましたけど
for で足してるだけなので速いし
double は桁数確保のために使ってるけど、小数点とかないし

結果はこんな感じ

m=0月 t0= 1 t1= 0 t2= 1
m=1月 t0= 1 t1= 1 t2= 1
m=2月 t0= 2 t1= 1 t2= 2
m=3月 t0= 3 t1= 2 t2= 3
m=4月 t0= 5 t1= 3 t2= 5
m=5月 t0= 8 t1= 5 t2= 8
m=6月 t0= 13 t1= 8 t2= 13
m=7月 t0= 21 t1= 13 t2= 21
m=8月 t0= 34 t1= 21 t2= 34
m=9月 t0= 55 t1= 34 t2= 55
m=10月 t0= 89 t1= 55 t2= 89
m=11月 t0= 144 t1= 89 t2= 144
m=12月 t0= 233 t1= 144 t2= 233

ん？？？
んーーー・・・
結果の合計数は合ってるけど。。。なんか違う。。。
wikipedia の表を見て比較すれば一目瞭然だが。。。

■ 本来はこうだ

m=0月 t0= 1 t1= 0 t2= 0 al= 1
m=1月 t0= 0 t1= 1 t2= 0 al= 1
m=2月 t0= 1 t1= 0 t2= 1 al= 2
m=3月 t0= 1 t1= 1 t2= 1 al= 3
m=4月 t0= 2 t1= 1 t2= 2 al= 5
m=5月 t0= 3 t1= 2 t2= 3 al= 8
m=6月 t0= 5 t1= 3 t2= 5 al= 13
m=7月 t0= 8 t1= 5 t2= 8 al= 21
m=8月 t0= 13 t1= 8 t2= 13 al= 34
m=9月 t0= 21 t1= 13 t2= 21 al= 55
m=10月 t0= 34 t1= 21 t2= 34 al= 89
m=11月 t0= 55 t1= 34 t2= 55 al= 144
m=12月 t0= 89 t1= 55 t2= 89 al= 233

失敗した出力数値だと既に１か月目から違う。。。
まだ生まれてないのに１つがい生まれた事になってる？？？

つまり順に足していく考え方は合っているのだが。。。
２か月後に１つがいを産ませるためにあらかじめ
まだ生まれてない１つがいを用意して合計数値を出すためだけのプログラムになってしまった。

なので途中のきちんとした問題の条件の中での経緯が入ってない

どうすればいいんだろう？

出力の位置をずらせばいんじゃないの？
と、そこまで簡単な事ではないようです
2月前と3月前と同じ数字なんだからキープしておく？for文の中で？
何か根本的に違う気もします。。。
でも前の月の数値は必要な気がします。
先月の数値から今月を出しているのですから
これは今までのようにすぐにはできませんでしたが
ループの中で、、、1つずつ、順に、条件に合うよう、に組み込ませて。。。

。。。とりあえず出来ました
（流れの順が逆になりましたが上の ■本来はこうだ　がそうです）

興味のある人はアルゴリズムを考えてみて下さい
それほど難しくはないです
私は１日かかってしまいましたが。。。（汗）

が！

まだでっかい問題が残されてます（ARIAを思い出しますネ）
大きな数字の桁の表示ができない問題です。計算もです。

これはかなりググりました。

その前に
まず私の出力はどこまで計算できてるのだろう？
数値があってるかどうか分かりません。。。
ということで一覧を載せてるサイトを探して比べます

おーっ。ありました！

■「１番目から１０００番目までのフィボナッチ数列」
http://www.suguru.jp/Fibonacci/fib1-10000/fib1-1000.html

データしか載ってないシンプルなページですが十分です
という事で整合性を調べます

m=76月 t0= 2111485077978050 t1= 1304969544928657 t2= 2111485077978050 al= 5527939700884757
m=77月 t0= 3416454622906707 t1= 2111485077978050 t2= 3416454622906707 al= 8944394323791464
-------------ここから計算できてない。。。
m=78月 t0= 5527939700884757 t1= 3416454622906707 t2= 5527939700884757 al= 14472334024676220
m=79月 t0= 8944394323791464 t1= 5527939700884757 t2= 8944394323791464 al= 23416728348467684

76月まではちゃんと計算できてるみたいですが。。。
やはり桁の多い数字の大きい計算ができないとダメです

検索すると。。。
ここで「多倍長整数」なる全く耳にもした事もない単語があちこちで出てきます

■ 多倍長演算をする
なんのこっちゃ

ここでまたウィキペディアさんの解説を読む
https://ja.wikipedia.org/wiki/任意精度演算
任意精度演算

んーーー　んん？？？
。。。もう言葉”そのもの”が難しいです（汗）
書かれている文章もわけが分かりません。。。（滝汗）

こ、これは。。。
は…ハードルが高いな。。。
む、む、む、…無理かな。。。

何か別の方法は。。。
　「ruby や python は気にせず使える」とのコメント
やってるのが C なので。。。仕方ないから python 導入するか？
　「C言語族だと、GMP とかです」え？
あーまた新語。。。 GMP って何？
迷走します。。。

■ GMP(GNU Multiple Precision library)とは任意精度計算ライブラリの一つです

なるほどライブラリか
windows は多くのライブラリ関数を提供してるが、、、無いんだな。。。

https://gmplib.org/
ここからソースを落としてコンパイルして使う。。。
Linux になるなぁ 環境替えて Mingw64 上でやるか？
gcc は始めたばっかりだしなぁ
　「一応 windows でも使えるようにできるけど面倒だよ」というコメント。。。
環境替えた方が手っ取り早いという意見や勉強のために自分で作ってみるといい
とかが多い。。。

足し算でやることは数値を配列に格納して足したときに桁があふれたら上の要素に収めていく。。。
とシンプルなものですが、配列の構造も処理もよく分からん。。。
出力も面倒な感じだ。。。
勉強にためにとかの出題レベルなら簡単なのかなぁ

「千年後に兎が何羽いるかフィボナッチさんに答える」
と思い立ったが。。。あきらめるか（泣）T_T

最初に C を始めたときポインタの意味が分からなかったし
ポインタのポインタとか、なんでそんな分かりにくい事するんだよ！！
と思い、いまだにそうだが。。。

足し算だけでいいので windows で多倍演算できるサンプルソースありませんか（切実）！

「あった！！！　神！！！！！」

しかも引き算、掛け算、割り算まであって出力まである！！！
マジで嬉しい！！
本当に感謝！！！

足し算だけ使わせてもらいます m(_ _)m
あ。出力も

■ 神サイトは

プログラミング色々
http://7ujm.net/index.html
の、いなば さんです。

本当にありがとうございます！！！

■10進数で大きな桁数の計算を行う
http://7ujm.net/play/dcalc.html

これを使わせてもらって
関数の変数を配列に直して出力します

しかし配列用のサイズの設定をいくつにすればいいのか分からないので
どれくらいの桁になるか分からないから
勘でこのくらいかな？の設定でとりあえず SIZE 300 の 1000月 から始めて 2000月 、 4000月 と増やしてゆきます
大体1000月200くらいかな。。。
最初の頃は int でやっていて月数は増えているのに桁数が頭打ちになって、あー限界なんだなとすぐに分かりました
そうなる前からもう計算が怪しいです。なので大きめに設定をしておきます
確保したメモリはリリースするのが常道ですが、これのみで終了すれば開放されるのでまぁいいでしょう

しかしながら数値があってるか分かりません。。。
4000番目の数は合っているだろうか？

出力した 4000ヵ月後の数値です

836桁になりました（汗）

ここで先に紹介した
「１番目から１０００番目までのフィボナッチ数列」
のデータページから親ディレクトリを辿るとありがたいことに
なんと！
10000 番目まで記載されているではありませんか！！

ページタイトルは。。。

■ フィボナッチ数列と中学入試問題
http://www.suguru.jp/Fibonacci/

は？

中学入試問題？って小学校でやるの？？？
マジかｗｗｗ
どんな小学生だよ！！

焦ったところで、、、閑話休題2回目

数字は合ってますが、私の 3999番が 4000番 に相当するみたいで1番づつずれてます。。。
始めの月を0月とするか1月とするかの違いなのですがこれは
「産まれて2か月後から毎月1つがいずつの兎を産む。」
という文が曲者で12か月後ちょうどの時を含むのか未満なのかで1つズレます。
問題の文章からは明記されてないので、どちらでも取れるので数字が合ってれば問題ありません

一応 ウィキペディアさんの形でやってきたので修正なくそのままにします
4000ヵ月後は合っているみたいなので多分もう大丈夫でしょう
1000桁のサイズはバイト換算すればでると思いますが何桁になるか分からないし
オーバーフローするとやり直しになるので多めにサイズを取って実行します

「千年後の12000ヵ月後 の兎の数を出力です」

なぜ1000年なのかというと日本では千という数字に対して色々な意味づけがされています。
身近なところでは千切りとかｗもそうですし、なんで万じゃないの？とか思ったり
1000ヵ月という選択肢もありますが、ピンときません。「え？何年？」ってなりますｗ

「フィボナッチさん！
　1年後ではもの足りないです！千年後の兎の数です！！」

1万を超えるとなると結構時間がかかりますが。。。
SIZE 3000 で 12000 実行

1000年後＝12000ヵ月後 の計算結果です

2508桁になります

因みに無量大数は10の68乗だそうです

0が68個なので、、、あってるよね？　こんくらいの長さですね。。。以外に短いな（汗）
小学校の時、数え方が面白かったので「一十百。。。」と暗記したのを思い出します。その時は途方もない桁だなと思ったのですが。。。

世界人口 2019年で約 77億人

こんくらい。。。

千年も生きてねぇよ。
という突っ込みはフィボナッチさんの問題から既に除外されていますので却下です

「フィボナッチ数列 12000」「フィボナッチ数 12000」「Fibonacci number 12000」などで検索してみましたが。。。
検証できるところがすぐには見つかりません。。。

多分、合っているでしょうｗ（おぃ）

…に聞かれました「何の役に立つの？」

「分からんｗｗｗ」
（やってみたかっただけなんだよｗ）

crayonzen [2020-06-25]

おまけ動画・出力中のコマンドライン
https://youtu.be/39Lu66FiJD4

before  1280x720 120fps (MJPEG_240fps＞MP4_120fps)

after  Youtubeのエンコード 60fps

もうちょっと画質なんとかならんかなぁ。。。
https://onl.tw/LGUaKf4
一般的なフレームレートは 24、25、30、48、50、60 fps（1 秒あたりのフレーム数）ですが、それ以外のフレームレートも使用できます。
って書いてあったんだがなぁ。。。

因みに激遅いエンコードだが、 libaom-av1 の AV1 画像。「凄い」としかいいようがない
ffmpeg -i input.mp4 -vcodec libaom-av1 -b:v 7500k -cpu-used 5 -b:a 384k output.webm

fibonacci_12000_120fps_60fps_libaom-av1_7500kbps.webm
サイズ：260 MB (273,071,193 バイト)
time=00:05:25

Video: av1
1280x720
60 fps
bitrate: 6720 kb/s

Audio: opus
48000 Hz
stereo
bitrate= 397.2kbits/s

CPUフル稼働でエンコードの速い SVT-AV1 の AV1 もffmpeg4.4に実装されている libsvtav1 エンコーダー。画質は動画によるかもしれない