みんなの MATLAB プログラムを見て、セクシーな書き方を知っておこう（フィボナッチ）

# プログラムコンテストをやってみました。
　年に１回、MATLAB Expo っていう集会？みたいなのがあったので、そこでコンテストをやってみました。こんな UI を作って、「好きなの解いてね」って書いて、大量のパソコンを放置！
![contest_ui.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/475339/bbc0000c-e79a-e860-fe89-18b617edb699.png)

　正解かどうかは自動採点！


## 採点は「シンプルなプログラム」を評価します。

　シンプルって何なのさ。

　今回は、正解かどうかと、「ノードカウント」っていうのを使ってプログラムのシンプルさを評価しました。ここにプログラムの評価をするプログラムがあります。
https://jp.mathworks.com/matlabcentral/fileexchange/34754-calculate-size

たとえば、「入力に 1 を足して出力してくださいね」っていう問題だと、以下のような感じですね。

```matlab:12点
function y = plus_one(x)
      y = x+1;
end
```

```matlab:16点
function z = plus_one(x)
      z = x;
      y = z+1;
end
```

点数が「低い」ほうが優秀な成績なので、上のが優秀！

※ 空白やコメントや改行やセミコロンは、ノードカウントの評価対象外なので、安心して余白を開けましょう。


# 色んな人の正解を見てみよう！

例えばこんな問題がありました。みんな大好きフィボナッチです。

```
フィボナッチ数列： 1, 1, 2, 3, 5, ...

fib(1) --> 1
fib(5) --> 5
fib(50) --> 12586269025

となるような関数

f = fib(n)

を作成せよ。
```

採点は、1 から 50 までの入力に対して、1 から 12586269025 が正しく出てくるかどうかを見ています。

## 一番多かった再帰の解答（C 言語っぽい書き方）
　教科書とかでよく見る再帰ですね。これで30点。

```matlab:30点
function f = fib(n)

if n > 2
    f = fib(n-1) + fib(n-2);
else
    f = 1;
end
```

ただ、この書き方だと正解は出るけど計算が遅い。。
試しに時間計測。

```matlab
tic
f = fib(50);
toc

経過時間は 687.018277 秒です。
```

11分30秒！
MATLAB だと、あんまりこういう書き方しないほうがいいね。


## ループをグルグル回しちゃうパターン
　2番目に多い、FOR文とかWHILE文を使ったやつ。代表的な書き方がこれでした。

```matlab:38点
function f = fib(n)

f = 0;
f1 = 0;
f2 = 1;
for x = 1:n
    f = f1 + f2;
    f2 = f1;
    f1 = f;
end
```

点数は再帰より悪いけど、計算は速い。

```matlab
tic
for n = 1:10000
f = fib(50);
end
t = toc/10000

t =

   1.7706e-07
```

速すぎるから、10000 回計算させた平均値を取りましたが 0.17(μs) くらいですね。

## 一般式にしちゃうパターン

　丸め誤差が出るから round してますけど、計算が多いからスコアが良くない。

```matlab:37点
function f = fib(n)
f = round(((0.5+sqrt(5)/2)^n - (0.5-sqrt(5)/2)^n)/sqrt(5));
```

　こんな式ですね。

```math
F(n) = \frac{1}{\sqrt{5}}
\left(
\left( 
\frac{1+\sqrt{5}}{2} 
\right) ^n - 
\left( 
\frac{1-\sqrt{5}}{2}
\right) ^n 
\right)
```

　計算時間は 0.7 (μs) くらい。

（↑↑ 超ひさしぶりに $\TeX$ 書いた。。）


## 行列計算させちゃうパターン（セクシー）

　いい点数！24点！

```matlab:24点
function f = fib(n)
x = [1 1;1 0]^n;
f = x(2);
```

　行列計算は、こういう話ですね。

```math
   \left(
    \begin{array}{l}
      F_{n+2} \\
      F_{n+1}
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      F_{n+1} & F_n \\
      F_n & F_{n-1}
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      1 \\
      1
    \end{array}
  \right)
```

　具体的に書くと、$F_2 = 1,   F_1 = 1$ が初期値として、次の値はこうなります。

```math
   \left(
    \begin{array}{l}
      F_3 \\
      F_2
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      F_2 \\
      F_1
    \end{array}
  \right)
```

　$F_4$ のときはこうなって、

```math
   \left(
    \begin{array}{l}
      F_4 \\
      F_3
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      F_3 \\
      F_2
    \end{array}
  \right)
```

　つまり、$F_3, F_2$ に元の式を代入して [1 1;1 0] の２乗になると。

```math
   \left(
    \begin{array}{l}
      F_4 \\
      F_3
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      F_2 \\
      F_1
    \end{array}
  \right)
```


　なので、大きい数に応用するとこうなるんですが、

```math
   \left(
    \begin{array}{l}
      F_{52} \\
      F_{51}
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)^{50}
   \left(
    \begin{array}{l}
      F_2 \\
      F_1
    \end{array}
  \right)
```

　最初の式を見ると、真ん中の行列はこうなってるはずなので、左下の値を取ればいいですね。

```math
   \left(
    \begin{array}{cc}
      F_{51} & F_{50} \\
      F_{50} & F_{49}
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)^{50}
```

　計算時間も速くて、1 (μs) くらい！


## ツールボックス使っちゃうパターン（ベスト）
　ノードカウントはツールボックス関数の中身までは見ないので、Symbolic Math Toolbox を使ったやつ。

```matlab:12点
function f = fib(n)
f = fibonacci(n);
```

　12点！関数を知ってたらこれでいいね。

　ただ、エラーチェックとか冗長なコードがあるせいか、計算時間は 0.03 秒くらいで、他のよりちょっと遅い。


# いろんな人のプログラムを見るのは面白いね。
　とりあえず今のところ、ノードカウント観点でセクシーな MATLAB プログラムは、

- あったらツールボックスを使おう。
- 行列演算を使おう。

　ですね。あと、ここに Octave の書き方が書いてあるけど、多分こっちも行列っぽく書くといい速さになるかもね。
https://qiita.com/y_irabu/items/604b0987aa7c8ec52c65