Last active
April 19, 2018 05:13
-
-
Save komasaru/5370005 to your computer and use it in GitHub Desktop.
Ruby script to multiply big-digit values with Karatsuba method.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#! /usr/local/bin/ruby | |
#********************************************* | |
# 多倍長乗算 ( by Karatsuba 法 ) | |
# - 多倍長 * 多倍長 | |
# - 最下位の桁を配列の先頭とする考え方 | |
#********************************************* | |
# | |
class MultiplyKaratsuba | |
D_MAX = 1024 # 計算可能な最大桁数 ( 2のべき乗 ) | |
D = 1024 # 実際に計算する桁数 ( D_MAX 以下の 4 の倍数 ) | |
def initialize | |
# ====================================== # | |
# テストなので、被乗数・乗数は乱数を使用 # | |
# ====================================== # | |
@a, @b = Array.new, Array.new | |
rnd_a, rnd_b = Random.new(0), Random.new(1) | |
# 被乗数・乗数桁数設定 | |
D.times do |i| | |
@a << rnd_a.rand(10) | |
@b << rnd_b.rand(10) | |
end | |
end | |
# 計算 ( 標準(筆算)法 ) | |
def calc_karatsuba | |
# 配列初期設定 ( コンストラクタで生成した配列を使用 ) | |
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 ]==== | |
# 乗算 ( Karatsuba 法 ) | |
z = multiply_karatsuba(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 | |
# 乗算 ( Karatsuba 法 ) | |
def multiply_karatsuba(a, b) | |
# 配列サイズ取得 | |
t_len = a.size | |
# 4桁(配列4個)になった場合は標準乗算 | |
return multiply_normal(a, b) if t_len <= 4 | |
# 配列分割 | |
a_1 = a[(t_len / 2)..-1] | |
a_0 = a[0..(t_len / 2 - 1)] | |
b_1 = b[(t_len / 2)..-1] | |
b_0 = b[0..(t_len / 2 - 1)] | |
# v = a1 + a0, w = b1 + b0 | |
v, w = Array.new, Array.new | |
(t_len / 2).times do |i| | |
v << a_1[i] + a_0[i] | |
w << b_1[i] + b_0[i] | |
end | |
# x1 = a0 * b0 | |
x_1 = multiply_karatsuba(a_0, b_0) | |
# x2 = a1 * b1 | |
x_2 = multiply_karatsuba(a_1, b_1) | |
# x3 = (a1 + a0) * (b1 + b0) | |
x_3 = multiply_karatsuba(v, w) | |
# x3 = x3 - x1 - x2 | |
t_len.times { |i| x_3[i] -= x_1[i] + x_2[i] } | |
# z = x2 * R^2 + (x3 - x2 - x1) * R + x1 | |
z = x_1 + x_2 | |
t_len.times { |i| z[i + t_len / 2] += x_3[i] } | |
return z | |
rescue => e | |
raise | |
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 = MultiplyKaratsuba.new | |
# 乗算 ( Karatsuba 法 ) | |
obj.calc_karatsuba | |
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