読者です 読者をやめる 読者になる 読者になる

猫尾製作所

あまりアテにしないでね

Rubyによる連続する整数の積の多項式の展開

数学 Ruby プログラミング

前回の記事では、 (n+1)(n+2) \cdots (n+m-1)(n+m) という連続するいくつかの整数の積のかたちの多項式を展開したときの各項の係数を求める漸化式を導出しましたが、今回はそのプログラミング編です。

すなおに、漸化式を Ruby プログラムで実装すると次のようになるようです。
(あら、はてなブログでもプログラミングのコードが色つきで表示されるようになったのね)

#! ruby -Ks
require "kconv"

# Π_{k=1}^{m} (n+k) = (n+1)(n+2)(n+3)…(n+m) の係数を求める

# 漸化式で係数を求める
def a(m, k)
	if m == 0 && k == 0 then
		return 1
	end
	
	if k == m then
		return a(m-1, m-1)
	end
	
	if k == 0 then
		return (m * a(m-1, 0))
	end
	
	if 1 <= k && k <= m-1 then
		return (m * a(m-1, k) + a(m-1, k-1))
	end
end

# メイン部分

# m を与える
# hoge.to_i で 文字列 hoge を整数に変換
if ARGV.length == 1 then
	m = ARGV[0].to_i
else
	puts "Please give a positive integer."
	exit 1  # 異常終了
end

if m < 1 then
	puts "Please give a positive integer."
	exit 1  # 異常終了
end

for i in 0..(m-1) do
	puts "#{a(m, m-i)} n^#{m-i} + "
end

puts "#{a(m, 0)}"

しかし、この方法は実は効率がよくないのです。

 m=10 ぐらいだとすぐに求められますが、

% time ruby tenkai.rb 10
1 n^10 +
55 n^9 +
1320 n^8 +
18150 n^7 +
157773 n^6 +
902055 n^5 +
3416930 n^4 +
8409500 n^3 +
12753576 n^2 +
10628640 n^1 +
3628800

real    0m0.135s
user    0m0.000s
sys     0m0.046s

 m=20 ぐらいになると少し重くなり、

% time ruby tenkai.rb 20
1 n^20 +
210 n^19 +
20615 n^18 +
1256850 n^17 +
53327946 n^16 +
1672280820 n^15 +
40171771630 n^14 +
756111184500 n^13 +
11310276995381 n^12 +
135585182899530 n^11 +
1307535010540395 n^10 +
10142299865511450 n^9 +
63030812099294896 n^8 +
311333643161390640 n^7 +
1206647803780373360 n^6 +
3599979517947607200 n^5 +
8037811822645051776 n^4 +
12870931245150988800 n^3 +
13803759753640704000 n^2 +
8752948036761600000 n^1 +
2432902008176640000

real    0m4.843s
user    0m4.680s
sys     0m0.030s

 m=25 では

% time ruby tenkai.rb 25
1 n^25 +
325 n^24 +
50050 n^23 +
4858750 n^22 +
333685495 n^21 +
17247104875 n^20 +
696829576300 n^19 +
22563937825000 n^18 +
595667304367135 n^17 +
12972753318542875 n^16 +
234961569422786050 n^15 +
3557372853474553750 n^14 +
45145946926994481865 n^13 +
480544558742733545125 n^12 +
4284218746244111474800 n^11 +
31882014375298512782500 n^10 +
196928100451110820242880 n^9 +
1001369304512841374110000 n^8 +
4144457803247115877036800 n^7 +
13746468217967926978680000 n^6 +
35770355645907606826362624 n^5 +
70874145319837672677196800 n^4 +
102339530601744675672576000 n^3 +
100480171548351161548800000 n^2 +
59190128811701203599360000 n^1 +
15511210043330985984000000

real    2m42.796s
user    2m32.365s
sys     0m0.109s

 m=30 で求めようと思ったらマシンに負担がかかりすぎて。

どうも、プログラミングで再帰的な方法(漸化式を用いるような方法)でアルゴリズムを組むときには工夫が必要なことが多いようです。これは2011年4月3日にダイアリーでもフィボナッチ数を求めるときに云々と言及いたしました。

それで次のように書き換えますと。

#! ruby -Ks
require "kconv"

# Π_{k=1}^{m} (n+k) = (n+1)(n+2)(n+3)…(n+m) の係数を求める

# メイン部分

# m を与える
# hoge.to_i で 文字列 hoge を整数に変換
if ARGV.length == 1 then
	m = ARGV[0].to_i
else
	puts "Please give a positive integer."
	exit 1  # 異常終了
end

if m < 1 then
	puts "Please give a positive integer."
	exit 1  # 異常終了
end

a = Array.new()
b = Array.new()

a[0] = 1
b[0] = 1

for i in 1..m do
	b[0] = i * a[0]
	
	for j in 1..(i-1) do
		b[j] = i * a[j] + a[j-1]
	end
	
	b[i] = a[i-1]
	
	a = b.clone
end

for i in 0..(m-1) do
	puts "#{a[m-i]} n^#{m-i} + "
end

puts "#{a[0]}"

そうすると、

% time ruby tenkai1.rb 100

(結果略)

real    0m0.194s
user    0m0.015s
sys     0m0.077s

このようにうまくいくようです。

ちなみに、さらに書き換えて、 m = 1 から  100 までの結果を書き出すと、

% time ruby tenkai2.rb > 1.tmp

real    0m0.708s
user    0m0.592s
sys     0m0.046s

0.7秒ほどで書き出しが終わりました。

この結果を少し整形したものをテキストファイルとして上げました。