■フィボナッチ関連のネタは過去にもある。 「LLまつりでシェル芸人をジェネレートしてきた」を参加していないのに解いてみた。 http://labunix.hateblo.jp/entry/20130915/1379249444 bashとclispとawkで小学三年生レベルの等差数列の総和 http://d.hatena.ne.jp/labunix/20130114 ■フィボナッチ数列を30個。黄金比付き。 初期値F{0}=0,F{1}=1,F{n+2}=F{n}+F{n+1},n>=0 F{0}=a,F{1}=b,F{n+2}=cと置く。 $ a=0;b=1; \ for n in `seq 0 30`;do \ let c=$a+$b;echo "$a $b" | \ awk '{if($1!=0)printf "%8f %8d\n",$2/$1,$1;else printf "%17d\n",$1}'; \ a=$b;b=$c; \ done 0 1.000000 1 2.000000 1 1.500000 2 1.666667 3 1.600000 5 1.625000 8 1.615385 13 1.619048 21 1.617647 34 1.618182 55 1.617978 89 1.618056 144 1.618026 233 1.618037 377 1.618033 610 1.618034 987 1.618034 1597 1.618034 2584 1.618034 4181 1.618034 6765 1.618034 10946 1.618034 17711 1.618034 28657 1.618034 46368 1.618034 75025 1.618034 121393 1.618034 196418 1.618034 317811 1.618034 514229 1.618034 832040 ■リュカ数列30個。黄金比付き。 初期値L{0}=2,L{1}=1,L{n+2}=L{n}+L{n+1},n>=0 L{0}=a,L{1}=b,L{n+2}=cと置く。 $ a=2;b=1; \ for n in `seq 0 30`;do \ let c=$a+$b;echo "$a $b" | awk '{printf "%8f %8d\n",$2/$1,$1}'; \ a=$b;b=$c; \ done 0.500000 2 3.000000 1 1.333333 3 1.750000 4 1.571429 7 1.636364 11 1.611111 18 1.620690 29 1.617021 47 1.618421 76 1.617886 123 1.618090 199 1.618012 322 1.618042 521 1.618031 843 1.618035 1364 1.618034 2207 1.618034 3571 1.618034 5778 1.618034 9349 1.618034 15127 1.618034 24476 1.618034 39603 1.618034 64079 1.618034 103682 1.618034 167761 1.618034 271443 1.618034 439204 1.618034 710647 1.618034 1149851 1.618034 1860498 ■黄金比は無理数なので、フィボナッチ数からclispで桁を増やした黄金比を求めてみる。 $ a=1;b=1; \ for n in `seq 0 30`;do \ let c=$a+$b;echo "(setf (EXT:LONG-FLOAT-DIGITS) 240)(/ $b.0L0 $a)" | \ clisp -q | tail -1 | sed s/"L0"//g; \ a=$b;b=$c; \ done 1.0 2.0 1.5 1.66666666666666666666666666666666666666666666666666666666666666666666666666666 1.6 1.625 1.61538461538461538461538461538461538461538461538461538461538461538461538461539 1.61904761904761904761904761904761904761904761904761904761904761904761904761905 1.61764705882352941176470588235294117647058823529411764705882352941176470588235 1.61818181818181818181818181818181818181818181818181818181818181818181818181819 1.6179775280898876404494382022471910112359550561797752808988764044943820224719 1.61805555555555555555555555555555555555555555555555555555555555555555555555555 1.61802575107296137339055793991416309012875536480686695278969957081545064377683 1.61803713527851458885941644562334217506631299734748010610079575596816976127321 1.6180327868852459016393442622950819672131147540983606557377049180327868852459 1.61803444782168186423505572441742654508611955420466058763931104356636271529889 1.61803381340012523481527864746399499060738885410144020037570444583594239198496 1.61803405572755417956656346749226006191950464396284829721362229102167182662539 1.61803396316670652953838794546759148529060033484812245874192776847644104281273 1.6180339985218033998521803399852180339985218033998521803399852180339985218034 1.61803398501735793897314087337840306961447103964918691759546866435227480358122 1.6180339901755970865563773925808819377787815481903901530122522725989498052058 1.61803398820532505147084481976480441078968489374323899919740377569180304986566 1.61803398895790200138026224982746721877156659765355417529330572808833678398895 1.61803398867044318560479840053315561479506831056314561812729090303232255914696 1.61803398878024268285650737686687041262675772079114940729696110978392493801125 1.61803398873830300685273243796393405899662963679499842173324237086214094431264 1.6180339887543225376088304054925726296446630229916522713184880321952355330684 1.61803398874820362134379819107829391185639082976650480622446419785737482716845 1.61803398875054083938272198451997500120186529493774337772222489303398875054084 1.618033988749648101530971893432887483853524072826455931169773648505610691474 ■(√5+1)/2で求めた黄金比 $ echo "(setf (EXT:LONG-FLOAT-DIGITS) 240)(/ (+ (sqrt 5.0L0) 1) 2)" | \ clisp -q | tail -1 | sed s/"L0"//g 1.61803398874989484820458683436563811772030917980576286213544862270526046281891 ■四捨五入でn番目のリュカ数を予測。 まずは10番目。 $ n=10;echo "(- (expt 1.618033 $n) (expt -1.618033 -$n))" | clisp -q | tail -1 | \ awk '{printf "%d\n",$1+0.5}' 123 $ a=2;b=1; \ for n in `seq 0 10`;do \ let c=$a+$b;echo "$a"; \ a=$b;b=$c; \ done | tail -1 123 ■100番目。 letがオーバーフローしてる。 $ n=100;echo "(- (expt 1.618033 $n) (expt -1.618033 -$n))" | clisp -q | tail -1 | awk '{printf "%d\n",$1+0.5}' 792025799999999967232 $ a=2;b=1; \ for n in `seq 0 100`;do \ let c=$a+$b;echo "$a"; \ a=$b;b=$c; \ done | tail -1 -1139155321138466361 ■ちなみにletがオーバーフローするタイミングは2^63-1を超えたところ。 いわゆる64bitの「INTMAX_MAX」の値です。 $ let n="$((0x7FFFFFFFFFFFFFFF))";while true;do echo $n;test "$n" -le 0 && break;let n=$n+1;done 9223372036854775807 -9223372036854775808 $ echo "(- (expt 2 63) 1)" | clisp -q | tail -1 9223372036854775807 ■簡単に浮動小数点を扱うようclispに変更したが、 今度は黄金比の有効桁数が不足している様子。 $ a=2;b=1; \ for n in `seq 0 100`;do \ c=`echo "(+ $a $b)" | clisp -q |tail -1`;echo "$a"; \ a=$b;b=$c; \ done | tail -1 792070839848372253127 ■桁数を増やしてみるというより、黄金比の計算式をそのまま入れてみる。 うーむ。ちょっと残念な結果だけど、分からなくもない。。。 $ n=100;echo "(- (expt (/ (+ (sqrt 5.0L0) 1) 2) $n) \ (expt (/ (+ (sqrt 5.0L0) 1) 2) -$n))" | \ clisp -q | tail -1 | awk '{printf "%d\n",$1+0.5}' 792072340000000049152 $ n=100;echo "(setf (EXT:LONG-FLOAT-DIGITS) 240) \ (- (expt (/ (+ (sqrt 5.0L0) 1) 2) $n) \ (expt (/ (+ (sqrt 5.0L0) 1) 2) -$n))" | \ clisp -q | tail -1 | sed s/"L20"//g 7.9207083984837225312699999999999999999999747497332387231411562195458792078607 ■n=1000にしてみる。 なるほど。惜しいw。まあ、予測の範疇なので十分かと。。。 「INTMAX_MAX」を超える整数値には注意が必要なようです。。。 $ a=2;b=1; \ for n in `seq 0 1000`;do \ c=`echo "(+ $a $b)" | clisp -q |tail -1`;echo "$a"; \ a=$b;b=$c; \ done | tail -1 | sed s/"1..80"/"&\n"/g 97194177735908175207981982079326473737797879155345685082728081084772518818444815269 08061914904596829767957830540320934740116303690766057397174086246375180164120149028 4097309096322681531675707666695323797578127 $ n=1000; echo "(setf (EXT:LONG-FLOAT-DIGITS) 1200) \ (- (expt (/ (+ (sqrt 5.0L0) 1) 2) $n) \ (expt (/ (+ (sqrt 5.0L0) 1) 2) -$n))" | clisp -q | tail -1 | sed s/"L20"//g 9.7194177735908175207981982079326473737797879155345685082728081084772518818444815269 08061914904596829767957830540320934740116303690766057397174086246375180164120149028 40973090963226815316757076666953237975781270000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000005488