J言語でフィボナッチ数列を作る


# はじめに

毎度おなじみJ言語です。
[前回](https://qiita.com/Raclamusi/items/38212822904f5e52e546)はライフゲームを作りました。
今回はみんな大好き、**フィボナッチ数列**を作ります。

# フィボナッチ数列

フィボナッチ数列とは、次の漸化式で定義される数列です。

```math
\begin{align}
F_0&=0\\
F_1&=1\\
F_n&=F_{n-1}+F_{n-2}(n\geq2)
\end{align}
```

つまり、それぞれの項が前の2つの項を和になっている数列です。

```math
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \cdots
```

# 愚直に実装

```j
fib=:(($:_1+])+($:_2+]))`]@.(2>])"0
```

漸化式の定義通りに、再帰を使って実装しました。

ここでは`fib`という**動詞**を定義しています。
J言語の「動詞」というのは、引数を受け取って何らかの計算をするもので、ほかの言語でいう「関数」のようなものです。

`]`は引数、`$:`はその動詞自身を示していて、`@.`は``(偽のとき)`(真のとき)@.(条件)``のように条件分岐に使います。
`_`（アンダーバー）は例によってマイナスの符号です。
`"0`は引数に配列が渡されたときに、配列の要素一つ一つにこの動詞を適用させるためのものです[^rank0]。わからない人は飾りだと思ってください。

[^rank0]: J902からここでの`"0`が不要になりましたが、次のメモ化で必要なのでつけています。

つまり、引数が2より小さい（`2>]`）ときは引数をそのまま（`]`）返し、そうでないときは引数に-2を足したものを自身に渡した結果と、引数に-1を足したものを自身に渡した結果を足したもの（`($:_1+])+($:_2+])`）を返します。

```text:実行画面
   fib 10
55
   fib 30
832040
   fib i.15
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
   
```

正しい結果が出ていますね。

……しかし、これを使うと**めちゃめちゃ時間がかかります**。

```text:実行画面
   6!:2'fib 30'
0.96194
   6!:2'fib 30'
0.95804
   
```

`6!:2`は実行時間を秒単位で返します。
第30項を計算するのに、1秒近く掛かっています。
この結果は環境によりますが、時間がかかるのは確かです。

# メモ化

というわけで、メモ化してみます。

```j
fib=:(($:_1+])+($:_2+]))`]@.(2>])M."0
```

できました。
J言語は`M.`の**2文字**でメモ化が実装できます。さすがJ言語。

```text:実行画面
   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符号あり整数で表せる範囲を超えると浮動小数点数での計算になるので、ある程度の精度までしか計算されなくなってしまいます。

```text:実行画面
   datatype fib 92
integer
   datatype fib 93
floating
   
```

第93項から浮動小数点数になってしまっているようです。

```text:実行画面
   fib 10000
_
   
```

第10000項を計算すると、`_`(無限大)になってしまいました。

調べてみると、第1477項から無限大になっていました。
早いと思ったらそういうことかっ！

# 任意精度

というわけで、任意精度にしてみます。

```j
fib=:(($:_1+])+($:_2x+]))`]@.(2>])M."0
```

できました。
どちらかの数字に`x`の**1文字**をつけるだけで任意精度で扱えます。さすがJ言語。

```text:実行画面
   fib 10000
3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551363373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386465273130008883026923567361313511757929743785441375213052050...
   
```

しっかり結果が整数で出ます。

```text:実行画面
   6!:2'fib 10000'
0.227189
   
```

任意精度にすることで少し遅くはなりましたが、十分早いです。

……しかし、再帰しすぎると`stack error`が出てしまいます。

```text:実行画面
   fib 100000
|stack error: fib
|       fib 100000
   
```

私の環境では第22204項が限界でした。
これは困った。

# 再帰なし

というわけで、再帰なしで実装します。

```j
fib=:1{"1(]{:,+/)^:[&1 0x
```

できました。
問題を解決するついでに、コードが短くなりました。さすがJ(ry

```text:実行画面
   fib 100000
2597406934722172416615503402127591541488048538651769658472477070395253454351127368626555677283671674475463758722307443211163839947387509103096569738218830449305228763853133492135302679278956701051276578271635608073050532200243233114383986516137827238124777...
   
```

再帰をしていないので、`stack error`が出ることはありません！

```text:実行画面
   6!:2'fib 10000'
0.070119
   
```

メモ化はしていませんが、メモ化したものより早いです！

### 軽く解説

**`&1 0x`**
最初に$\\{1,0\\}$といった任意精度整数の配列を用意し、`&`で左の動詞の右引数としてバインドします。

**`(] {: , +/)^:[`**
**引数回だけ、「後ろの要素と総和を連結する」作業を繰り返します。**
`^:`は繰り返しの演算子で、`(繰り返す処理)^:(繰り返す回数)`のように使います。
`[`は与えられる引数です。[^really?]
`+/`は総和、`{:`は一番後ろの要素を求め、`,`はそれらを連結します。
`]`はここでは左引数を無視することを意味します。[^why_ignore]

[^really?]: 正確には`[`は左引数です。右に`1 0x`がバインドされているので、ユーザが与える引数は左から渡されることになります。
[^why_ignore]: 左引数はループ回数を表しているだけなので、計算には必要ありません。むしろ介入してほしくないのです。

**`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)な定義**もあります。

```j
fib=: {{
  if. 2 > y do.
    y
  else.
    (fib y-2) + fib y-1
  end.
}}
```

~~こっちのほうがわかりやすい。~~



# おわりに

J言語はとっても便利でステキなプログラミング言語です。
とんでもなく短いコードで動いちゃうのが魅力です。
皆さんもぜひ使ってみてください。