1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
| #! /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
# ９桁（配列９個）になった場合は標準乗算
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
|
