Skip to content

Instantly share code, notes, and snippets.

@komasaru
Last active April 19, 2018 05:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save komasaru/5361556 to your computer and use it in GitHub Desktop.
Save komasaru/5361556 to your computer and use it in GitHub Desktop.
Ruby script to multiply big-digit values.
#! /usr/local/bin/ruby
#*********************************************
# 多倍長乗算 ( by 標準(筆算)方式 )
# - 多倍長 * 多倍長
# - 最下位の桁を配列の先頭とする考え方
#*********************************************
#
class MultiplyNormal
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)
# 被乗数・乗数桁数設定
0.upto(D - 1) do |i|
@a << rnd_a.rand(10)
@b << rnd_b.rand(10)
end
end
# 計算 ( 標準(筆算)法 )
def calc_normal
# 配列初期設定 ( コンストラクタで生成した配列を使用 )
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 ]====
# 乗算 ( 標準(筆算)法 )
z = multiply_normal(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)
# 各配列を各桁とみなして乗算
0.upto(b_len - 1) do |j|
0.upto(a_len - 1) do |i|
z[j + i] += a[i] * b[j]
# ====[ TEST ]===>
# @cnt_mul += 1 # 乗算カウント
# <===[ TEST ]====
end
end
return z
rescue => e
raise
end
# 繰り上がり処理
def do_carry(a)
cr = 0 # 繰り上がり
begin
0.upto(a.size - 1) 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 を削除するために、配列サイズを取得
aLen, bLen, zLen = D_MAX, D_MAX, D_MAX * 2
while a[aLen - 1] == 0 do aLen -= 1 if a[aLen - 1] == 0 end
while b[bLen - 1] == 0 do bLen -= 1 if b[bLen - 1] == 0 end
while z[zLen - 1] == 0 do zLen -= 1 if z[zLen - 1] == 0 end
# a 値
puts "a ="
(aLen - 1).downto(0) do |i|
print a[i]
print " " if (aLen - i) % 10 == 0
puts if (aLen - i) % 50 == 0
end
puts
# b 値
puts "b ="
(bLen - 1).downto(0) do |i|
print b[i]
print " " if (bLen - i) % 10 == 0
puts if (bLen - i) % 50 == 0
end
puts
# z 値
puts "z ="
(zLen - 1).downto(0) do |i|
print z[i]
print " " if (zLen - i) % 10 == 0
puts if (zLen - 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 = MultiplyNormal.new
# 乗算 ( 標準(筆算)法)
obj.calc_normal
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