はじめに
毎度おなじみJ言語です。
前回はライフゲームを作りました。
今回はみんな大好き、フィボナッチ数列を作ります。
フィボナッチ数列
フィボナッチ数列とは、次の漸化式で定義される数列です。
\begin{align}
F_0&=0\\
F_1&=1\\
F_n&=F_{n-1}+F_{n-2}(n\geq2)
\end{align}
つまり、それぞれの項が前の2つの項を和になっている数列です。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \cdots
愚直に実装
fib=:(($:_1+])+($:_2+]))`]@.(2>])"0
漸化式の定義通りに、再帰を使って実装しました。
ここではfibという動詞を定義しています。
J言語の「動詞」というのは、引数を受け取って何らかの計算をするもので、ほかの言語でいう「関数」のようなものです。
]は引数、$:はその動詞自身を示していて、@.は(偽のとき)`(真のとき)@.(条件)のように条件分岐に使います。
_（アンダーバー）は例によってマイナスの符号です。
"0は引数に配列が渡されたときに、配列の要素一つ一つにこの動詞を適用させるためのものです1。わからない人は飾りだと思ってください。
つまり、引数が2より小さい（2>]）ときは引数をそのまま（]）返し、そうでないときは引数に-2を足したものを自身に渡した結果と、引数に-1を足したものを自身に渡した結果を足したもの（($:_1+])+($:_2+])）を返します。
fib 10
55
fib 30
832040
fib i.15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
正しい結果が出ていますね。
……しかし、これを使うとめちゃめちゃ時間がかかります。
6!:2'fib 30'
0.96194
6!:2'fib 30'
0.95804
6!:2は実行時間を秒単位で返します。
第30項を計算するのに、1秒近く掛かっています。
この結果は環境によりますが、時間がかかるのは確かです。
メモ化
というわけで、メモ化してみます。
fib=:(($:_1+])+($:_2+]))`]@.(2>])M."0
できました。
J言語はM.の2文字でメモ化が実装できます。さすがJ言語。
6!:2'fib 30'
0.000216
6!:2'fib 10000'
0.16482
6!:2'fib 10000'
5.9e_5
第30項は余裕で計算できるようになりました。
第10000項も0.16秒ほどで計算できます。
メモ化されているので、2回目以降は爆速ですね。
……ただ、J言語では数値が64bit符号あり整数で表せる範囲を超えると浮動小数点数での計算になるので、ある程度の精度までしか計算されなくなってしまいます。
datatype fib 92
integer
datatype fib 93
floating
第93項から浮動小数点数になってしまっているようです。
fib 10000
_
第10000項を計算すると、_(無限大)になってしまいました。
調べてみると、第1477項から無限大になっていました。
早いと思ったらそういうことかっ！
任意精度
というわけで、任意精度にしてみます。
fib=:(($:_1+])+($:_2x+]))`]@.(2>])M."0
できました。
どちらかの数字にxの1文字をつけるだけで任意精度で扱えます。さすがJ言語。
fib 10000
3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551363373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386465273130008883026923567361313511757929743785441375213052050...
しっかり結果が整数で出ます。
6!:2'fib 10000'
0.227189
任意精度にすることで少し遅くはなりましたが、十分早いです。
……しかし、再帰しすぎるとstack errorが出てしまいます。
fib 100000
|stack error: fib
| fib 100000
私の環境では第22204項が限界でした。
これは困った。
再帰なし
というわけで、再帰なしで実装します。
fib=:1{"1(]{:,+/)^:[&1 0x
できました。
問題を解決するついでに、コードが短くなりました。さすがJ(ry
fib 100000
2597406934722172416615503402127591541488048538651769658472477070395253454351127368626555677283671674475463758722307443211163839947387509103096569738218830449305228763853133492135302679278956701051276578271635608073050532200243233114383986516137827238124777...
再帰をしていないので、stack errorが出ることはありません！
6!:2'fib 10000'
0.070119
メモ化はしていませんが、メモ化したものより早いです！
軽く解説
&1 0x
最初に$\{1,0\}$といった任意精度整数の配列を用意し、&で左の動詞の右引数としてバインドします。
(] {: , +/)^:[
引数回だけ、「後ろの要素と総和を連結する」作業を繰り返します。
^:は繰り返しの演算子で、(繰り返す処理)^:(繰り返す回数)のように使います。
[は与えられる引数です。2
+/は総和、{:は一番後ろの要素を求め、,はそれらを連結します。
]はここでは左引数を無視することを意味します。3
1 {"1
最後に後ろの要素、つまり($0$始まりで)$1$番目の要素を取ります。
"1は引数に配列を渡されたときに対応するために書きます。
たとえば10を渡されたときは、$\{1,0\}$の後ろの要素の$0$と総和の$1$を連結して$\{0,1\}$になり、$\{0,1\}$の後ろの要素の$1$と総和の$1$を連結して$\{1,1\}$になり、という操作を10回繰り返します。
$\{1,0\}$→$\{0,1\}$→$\{1,1\}$→$\{1,2\}$→$\{2,3\}$→$\{3,5\}$→$\{5,8\}$→$\{8,13\}$→$\{13,21\}$→$\{21,34\}$→$\{34,55\}$
このとき、出来上がった配列の後ろの要素の$55$が答えです。
ちなみに
今までやっていたものは、動詞の合成というものです。
これは、暗黙(tacit)の定義ともいわれます。
暗黙の定義といわれるということは、明示的(explicit)な定義もあります。
fib=: {{
if. 2 > y do.
y
else.
(fib y-2) + fib y-1
end.
}}
こっちのほうがわかりやすい。
おわりに
J言語はとっても便利でステキなプログラミング言語です。
とんでもなく短いコードで動いちゃうのが魅力です。
皆さんもぜひ使ってみてください。