【Ruby】ChatGPTにフィボナッチ数列の一般項算出プログラムを書かせてみた



# はじめに
ChatGPTがすごいので少し遊んでみました

タイトルの通りフィボナッチ数列の一般項です


# フィボナッチ数列について簡単に
「フィボナッチ数列？何それおいしいの？」という方のために少し補足しておきます

フィボナッチ数列は、最初の2つの数が1である数列で、その後の項は前の2つの項の和となる数列のことです。
具体的には、1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...のように続きます。

数学的に一般項は次のようになります。

```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\}
```

# なんでChatGPT使うの？

上記の数式をそのままプログラムに書けば一般項算出できるでしょ？と思うかもしれないですね。
ただ、ルート5という数字が無理数であるため、誤差が生じてしまいます。
（気になる人は実際に100個目ぐらいの数字で誤差が出るか確認してみましょう）

再帰処理やループ処理を使えば誤差は無くせますが、それだと大きい数字になるにつれ計算回数が多くなり、時間が相当にかかってしまいます

ということでいい方法がないかなーということを聞いてみました（ちなみにGPT4です）

# やってみた

**ぼく**
rubyを使ってフィボナッチ数列の一般校を求めるプログラムを書いてください

**GPT**
Ruby言語でフィボナッチ数列を求める一般的なプログラムは、以下のように書くことができます。再帰を用いた方法とループを用いた方法の2種類を示します。

再帰を用いた方法:
```ruby
def fibonacci(n)
  return n if n <= 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

# フィボナッチ数列の第n項を求める
n = 10
puts fibonacci(n)
```

ループを用いた方法:
```ruby
def fibonacci(n)
  return n if n <= 1

  prev = 0
  curr = 1

  (n - 1).times do
    prev, curr = curr, prev + curr
  end

  curr
end

# フィボナッチ数列の第n項を求める
n = 10
puts fibonacci(n)
```
これらのプログラムは、フィボナッチ数列の第n項を求めることができます。適切な n の値を指定して、プログラムを実行してください。

**ぼく**
数字が大きくなるにつれて時間がかかってしまいます
これを改善する方法はありますか？

**GPT**
はい、実行時間を改善する方法がいくつかあります。ここでは、メモ化と行列累乗を用いた2つの方法を紹介します。

メモ化を用いた方法 (動的計画法):
メモ化は、以前に計算した結果をキャッシュに保存し、再利用する方法です。これにより、同じ計算を繰り返すことなく、効率的にフィボナッチ数列を計算できます。

```ruby
def fibonacci(n, memo = {})
  return n if n <= 1
  return memo[n] if memo.key?(n)

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
end

# フィボナッチ数列の第n項を求める
n = 100
puts fibonacci(n)
```

行列累乗を用いた方法:
行列累乗を用いることで、フィボナッチ数列を効率的に計算できます。この方法では、以下の行列式を利用します。

```
| F(n+1) |   | 1  1 |^n   | F(1) |
|        | = |      |   * |      |
| F(n)   |   | 1  0 |     | F(0) |
```

```ruby
def matrix_mult(a, b)
  result = Array.new(2) { Array.new(2, 0) }
  2.times do |i|
    2.times do |j|
      2.times do |k|
        result[i][j] += a[i][k] * b[k][j]
      end
    end
  end
  result
end

def matrix_pow(matrix, n)
  return [[1, 0], [0, 1]] if n == 0
  return matrix if n == 1

  if n % 2 == 0
    half_pow = matrix_pow(matrix, n / 2)
    matrix_mult(half_pow, half_pow)
  else
    matrix_mult(matrix, matrix_pow(matrix, n - 1))
  end
end

def fibonacci(n)
  return n if n <= 1

  matrix = [[1, 1], [1, 0]]
  fib_matrix = matrix_pow(matrix, n - 1)
  fib_matrix[0][0]
end

# フィボナッチ数列の第n項を求める
n = 100
puts fibonacci(n)
```
これらの方法は、計算時間を大幅に削減できるため、大きな数値に対しても高速にフィボナッチ数列を計算できます。どちらの方法も試してみて、実行時間を比較してみてください。

**ぼく心の声**
行列累乗・・？なんかすごそう

# 試してみた
どのくらい早くなったか試してみました

算出した数字をそのまま出力すると時間がかかるので桁数を出力に変えてました

こんな感じ
```ruby
require 'benchmark'

# ...

Benchmark.bm 10 do |r|
  r.report 'normal' do
    puts fibonacci(n).to_s.length
  end
end
```

ちなみに環境
* Apple M1 Pro
* メモリ 32GB
* Ruby v3.1.0

算出するnは1,000,000にしました

では結果です

↓通常版（最初に提示されたループの方法）
```bash
                 user     system      total        real
normal     208988
 11.276495   2.968675  14.245170 ( 14.313927)
```

↓改善版（行列累乗を用いた方法）
```bash
                 user     system      total        real
improvement208988
  0.453979   0.002245   0.456224 (  0.456325)
```

30倍くらい早くなった😇

# 感想

ChatGPTすごいです（小並感）

AIのおかげで色々なことが楽になりそうだ。たぶん圧縮された時間分また新たな仕事が増えていくんだろうけど
便利なことは便利なので使い倒していこう

-- 心の声 --
ChatGPT使って業務効率上がったとして僕らの給料は上がるのだろうか・・・
AIのおかげだよね？君の実力が上がったわけじゃないよね？とか思われそうで少し怖い笑