はじめに
ChatGPTがすごいので少し遊んでみました
タイトルの通りフィボナッチ数列の一般項です
フィボナッチ数列について簡単に
「フィボナッチ数列？何それおいしいの？」という方のために少し補足しておきます
フィボナッチ数列は、最初の2つの数が1である数列で、その後の項は前の2つの項の和となる数列のことです。
具体的には、1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...のように続きます。
数学的に一般項は次のようになります。
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種類を示します。
再帰を用いた方法:
def fibonacci(n)
return n if n <= 1
fibonacci(n - 1) + fibonacci(n - 2)
end
# フィボナッチ数列の第n項を求める
n = 10
puts fibonacci(n)
ループを用いた方法:
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つの方法を紹介します。
メモ化を用いた方法 (動的計画法):
メモ化は、以前に計算した結果をキャッシュに保存し、再利用する方法です。これにより、同じ計算を繰り返すことなく、効率的にフィボナッチ数列を計算できます。
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) |
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)
これらの方法は、計算時間を大幅に削減できるため、大きな数値に対しても高速にフィボナッチ数列を計算できます。どちらの方法も試してみて、実行時間を比較してみてください。
ぼく心の声
行列累乗・・？なんかすごそう
試してみた
どのくらい早くなったか試してみました
算出した数字をそのまま出力すると時間がかかるので桁数を出力に変えてました
こんな感じ
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にしました
では結果です
↓通常版（最初に提示されたループの方法）
user system total real
normal 208988
11.276495 2.968675 14.245170 ( 14.313927)
↓改善版（行列累乗を用いた方法）
user system total real
improvement208988
0.453979 0.002245 0.456224 ( 0.456325)
30倍くらい早くなった😇
感想
ChatGPTすごいです（小並感）
AIのおかげで色々なことが楽になりそうだ。たぶん圧縮された時間分また新たな仕事が増えていくんだろうけど
便利なことは便利なので使い倒していこう
-- 心の声 --
ChatGPT使って業務効率上がったとして僕らの給料は上がるのだろうか・・・
AIのおかげだよね？君の実力が上がったわけじゃないよね？とか思われそうで少し怖い笑