Skip to content

Instantly share code, notes, and snippets.

@komasaru
Last active April 19, 2018 05:12
Show Gist options
  • Save komasaru/5418386 to your computer and use it in GitHub Desktop.
Save komasaru/5418386 to your computer and use it in GitHub Desktop.
Ruby script to multiply big-digit values with Toom-Cook 3-way method.
#! /usr/local/bin/ruby
#*********************************************
# 多倍長乗算 ( by Toom-Cook 法 (3-way) )
# - 多倍長 * 多倍長
# - 最下位の桁を配列の先頭とする考え方
#*********************************************
#
class MultiplyToomCook3
D_MAX = 729 # 計算可能な最大桁数 ( 3 のべき乗 )
D = 729 # 実際に計算する桁数 ( D_MAX 以下 )
def initialize
# ====================================== #
# テストなので、被乗数・乗数は乱数を使用 #
# ====================================== #
@a, @b = Array.new, Array.new
rnd_a, rnd_b = Random.new(0), Random.new(1)
# 被乗数・乗数設定
0.upto(D - 1) do |i|
@a << rnd_a.rand(10)
@b << rnd_b.rand(10)
end
end
# 計算 ( Toom-Cook 法 )
def calc_toom_cook
# 配列初期設定 ( コンストラクタで生成した配列を使用 )
a, b = @a, @b # 被乗数配列、乗数配列
z = Array.new # 計算結果用配列
begin
# 最大桁に満たない部分は 0 を設定
(D_MAX - a.size).times { |i| a << 0 }
(D_MAX - b.size).times { |i| b << 0 }
# ====[ TEST ]===>
# t1 = Time.now # 計算開始時刻
# 100.times do |l| # 100 回 LOOP
# @cnt_mul = 0 # 乗算回数リセット
# <===[ TEST ]====
# 乗算 ( Toom-Cook 法 (3-way) )
z = multiply_toom_cook_3(a, b)
# ====[ TEST ]===>
# end
# t2 = Time.now # 計算終了時刻
# @tt = t2 - t1 # 計算時間
# <===[ TEST ]====
# 繰り上がり処理
z = do_carry(z)
# 結果出力
display(a, b, z)
rescue => e
raise
end
end
private
# 乗算 ( 標準(筆算)法 )
def multiply_normal(a, b)
# 配列サイズ取得
a_len, b_len = a.size, b.size
# 計算結果初期化
z = Array.new(a_len + b_len, 0)
# 各配列を各桁とみなして乗算
b_len.times do |j|
a_len.times do |i|
z[j + i] += a[i] * b[j]
# ====[ TEST ]===>
# @cnt_mul += 1 # 乗算カウント
# <===[ TEST ]====
end
end
return z
rescue => e
raise
end
# 乗算 ( Toom-Cook 法 (3-way) )
# 結果用配列は以下のように配置し、
# +----+----+----+----+----+----+----+----+----+----+
# | c0 | c2 | c4 | c1 | c3 |
# +----+----+----+----+----+----+----+----+----+----+
# 最後に、c1, c3 を所定の位置に加算する。
# +----+----+----+----+----+----+
# | c0 | c2 | c4 |
# +----+----+----+----+----+----+
# +----+----+----+----+
# | c1 | c3 |
# +----+----+----+----+
def multiply_toom_cook_3(a, b)
# 各種宣言
a_m1, a_m2 = Array.new, Array.new
a_0, a_1, a_inf = Array.new, Array.new, Array.new
b_m1, b_m2 = Array.new, Array.new
b_0, b_1, b_inf = Array.new, Array.new, Array.new
c_m1, c_m2 = Array.new, Array.new
c_0, c_1, c_inf = Array.new, Array.new, Array.new
c0, c1, c2 = Array.new, Array.new, Array.new
c3, c4 = Array.new, Array.new
begin
# 配列サイズ取得
t_len = a.size
# 9桁(配列9個)になった場合は標準乗算
return multiply_normal(a, b) if t_len <= 9
# 配列分割
a2 = a[(t_len * 2 / 3)..-1]
a1 = a[(t_len / 3)..(t_len * 2 / 3 - 1)]
a0 = a[0..(t_len / 3 - 1)]
b2 = b[(t_len * 2 / 3)..-1]
b1 = b[(t_len / 3)..(t_len * 2 / 3 - 1)]
b0 = b[0..(t_len / 3 - 1)]
# a(-2) = 4 * a2 - 2 * a1 + a0, b(1) = 4 * b2 - 2 * b1 + b0 (by シフト演算)
(t_len / 3).times do |i|
a_m2 << (a2[i] << 2) - (a1[i] << 1) + a0[i]
b_m2 << (b2[i] << 2) - (b1[i] << 1) + b0[i]
end
# a(-1) = a2 - a1 + a0, b(1) = b2 - b1 + b0
(t_len / 3).times do |i|
a_m1 << a2[i] - a1[i] + a0[i]
b_m1 << b2[i] - b1[i] + b0[i]
end
# a(0) = a0, b(0) = b0
a_0, b_0 = a0, b0
# a(1) = a2 + a1 + a0, b(1) = b2 + b1 + b0
(t_len / 3).times do |i|
a_1[i] = a2[i] + a1[i] + a0[i]
b_1[i] = b2[i] + b1[i] + b0[i]
end
# a(inf) = a2, b(inf) = b2
a_inf, b_inf= a2, b2
# c(-2) = a(-2) * b(-2)
c_m2 = multiply_toom_cook_3(a_m2, b_m2)
# c(-1) = a(-1) * b(-1)
c_m1 = multiply_toom_cook_3(a_m1, b_m1)
# c(0) = a(0) * b(0)
c_0 = multiply_toom_cook_3(a_0, b_0)
# c(1) = a(1) * b(1)
c_1 = multiply_toom_cook_3(a_1, b_1)
# c(inf) = a(inf) * b(inf)
c_inf = multiply_toom_cook_3(a_inf, b_inf)
# c4 = 6 * c(inf) / 6
c4 = c_inf
# c3 = -c(-2) + 3 * c(-1) - 3 * c(0) + c(1) + 12 * c(inf) / 6
((t_len / 3) * 2).times do |i|
c3[i] = -c_m2[i]
c3[i] += (c_m1[i] << 1) + c_m1[i]
c3[i] -= (c_0[i] << 1) + c_0[i]
c3[i] += c_1[i]
c3[i] += (c_inf[i] << 3) + (c_inf[i] << 2)
c3[i] /= 6
end
# c2 = 3 * c(-1) - 6 * c(0) + 3 * c(1) - 6 * c(inf) / 6
((t_len / 3) * 2).times do |i|
c2[i] = (c_m1[i] << 1) + c_m1[i]
c2[i] -= (c_0[i] << 2) + (c_0[i] << 1)
c2[i] += (c_1[i] << 1) + c_1[i]
c2[i] -= (c_inf[i] << 2) + (c_inf[i] << 1)
c2[i] /= 6
end
# c1 = c(-2) - 6 * c(-1) + 3 * c(0) + 2 * c(1) - 12 * c(inf) / 6
((t_len / 3) * 2).times do |i|
c1[i] = c_m2[i]
c1[i] -= (c_m1[i] << 2) + (c_m1[i] << 1)
c1[i] += (c_0[i] << 1) + c_0[i]
c1[i] += (c_1[i] << 1)
c1[i] -= (c_inf[i] << 3) + (c_inf[i] << 2)
c1[i] /= 6
end
# c0 = 6 * c(0) / 6
c0 = c_0
# z = c4 * x^4 + c3 * x^3 + c2 * x^2 + c1 * x + c0
z = c0 + c2 + c4
((t_len / 3) * 2).times { |i| z[i + t_len / 3] += c1[i] }
((t_len / 3) * 2).times { |i| z[i + t_len ] += c3[i] }
return z
rescue => e
raise
end
end
# 繰り上がり処理
def do_carry(a)
cr = 0 # 繰り上がり
begin
a.size.times do |i|
a[i] += cr
cr = a[i] / 10
a[i] -= cr * 10
end
# オーバーフロー時
puts "[ OVERFLOW!! ] #{cr}" unless cr == 0
return a
rescue => e
raise
end
end
# 結果出力
def display(a, b, z)
# 上位桁の不要な 0 を削除するために、配列サイズを取得
len_a, len_b, len_z = D_MAX, D_MAX, D_MAX * 2
while a[len_a - 1] == 0 do len_a -= 1 if a[len_a - 1] == 0 end
while b[len_b - 1] == 0 do len_b -= 1 if b[len_b - 1] == 0 end
while z[len_z - 1] == 0 do len_z -= 1 if z[len_z - 1] == 0 end
# a 値
puts "a ="
(len_a - 1).downto(0) do |i|
print a[i]
print " " if (len_a - i) % 10 == 0
puts if (len_a - i) % 50 == 0
end
puts
# b 値
puts "b ="
(len_b - 1).downto(0) do |i|
print b[i]
print " " if (len_b - i) % 10 == 0
puts if (len_b - i) % 50 == 0
end
puts
# z 値
puts "z ="
(len_z - 1).downto(0) do |i|
print z[i]
print " " if (len_z - i) % 10 == 0
puts if (len_z - i) % 50 == 0
end
puts; puts
# ====[ TEST ]====
# puts "Counts of multiply / 1 loop = #{@cnt_mul}" # 乗算回数
# puts "Total time of all loops = #{@tt} seconds" # 処理時間
# ====[ TEST ]====
rescue => e
raise
end
end
if __FILE__ == $0
begin
# 計算クラスインスタンス化
obj = MultiplyToomCook3.new
# 乗算 ( Toom-Cook 法 )
obj.calc_toom_cook
rescue => e
$stderr.puts "[#{e.class}] #{e.message}"
e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment