mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

Ruby - 多桁乗算(Toom-Cook 法 (3-way))!

[ プログラミング, 数学 ] [ Ruby ]

こんばんは。

前回は、C++ による「多桁乗算(Toom-Cook 法 (3-way))」のアルゴリズムを紹介しました。

今日は、同じアルゴリズムを Ruby で実現してみました。
Ruby では桁数(整数型の範囲)をあまり気にしなくても、メモリの許される限り計算できますが、それでも多桁同士の乗算では不都合になることもあるでしょう。 アルゴリズムについては、上記リンクの過去記事等を参照してください。

実際、ほとんど同じです。

以下、Ruby によるサンプルスクリプトです。

0. 前提条件

  • Linux Mint 14 Nadia (64bit) での作業を想定。
  • Ruby 2.0.0-p0 を使用。

1. Ruby スクリプト作成

今回作成した Ruby ソースは以下の通り。
スクリプト中の随所にあるテスト用コメントを解除すると、1ループあたりの乗算回数をカウントしたり、100 ループした場合の処理時間を計測するようになっている。
また、計算可能な最大桁数の設定を 3 のべき乗桁にしている。

multiply_toom_cook_3.rb
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
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
#*********************************************
# 多倍長乗算 ( by Toom-Cook 法 (3-way) )
#   - 多倍長 * 多倍長
#   - 最下位の桁を配列の先頭とする考え方
#*********************************************
#
D_MAX = 729  # 計算可能な最大桁数 ( 3 のべき乗 )
D     = 729  # 実際に計算する桁数 ( D_MAX 以下 )

class MultiplyToomCook3
  def initialize
    # ====================================== #
    # テストなので、被乗数・乗数は乱数を使用 #
    # ====================================== #
    @a_0 = Array.new
    @b_0 = Array.new
    rnd_a = Random.new(0)
    rnd_b = Random.new(1)

    # 被乗数・乗数桁数設定
    0.upto(D - 1) do |i|
      @a_0 << rnd_a.rand(10)
      @b_0 << rnd_b.rand(10)
    end
  end

  # 計算 ( Toom-Cook 法 )
  def calc_toom_cook
    # 配列初期設定 ( コンストラクタで生成した配列を使用 )
    a = @a_0       # 被乗数配列
    b = @b_0       # 乗数配列
    z = Array.new  # 計算結果用配列

    # 最大桁に満たない部分は 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)

    # 繰り上がり処理
    z = do_carry(z);
    # ====[ TEST ]===>
    # end
    # t2 = Time.now      # 計算終了時刻
    # @tt = t2 - t1      # 計算時間
    # <===[ TEST ]====

    # 結果出力
    display(a, b, z);
  end

  # 乗算 ( 標準(筆算)法 )
  def multiply_normal(a, b)
    # 配列サイズ取得
    a_len = a.size
    b_len = 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
  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_m2  = Array.new
    a_m1  = Array.new
    a_0   = Array.new
    a_1   = Array.new
    a_inf = Array.new
    b_m2  = Array.new
    b_m1  = Array.new
    b_0   = Array.new
    b_1   = Array.new
    b_inf = Array.new
    c_m2  = Array.new
    c_m1  = Array.new
    c_0   = Array.new
    c_1   = Array.new
    c_inf = Array.new
    c0    = Array.new
    c1    = Array.new
    c2    = Array.new
    c3    = Array.new
    c4    = Array.new

    # 配列サイズ取得
    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 シフト演算)
    0.upto(t_len / 3 - 1) 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
    0.upto(t_len / 3 - 1) 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 = a0
    b_0 = b0

    # a(1) = a2 + a1 + a0, b(1) = b2 + b1 + b0
    0.upto(t_len / 3 - 1) 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= a2
    b_inf= 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
    0.upto((t_len / 3) * 2 - 1) 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
    0.upto((t_len / 3) * 2 - 1) 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
    0.upto((t_len / 3) * 2 - 1) 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
    0.upto((t_len / 3) * 2 - 1) {|i| z[i + t_len / 3] += c1[i]}
    0.upto((t_len / 3) * 2 - 1) {|i| z[i + t_len    ] += c3[i]}

    return z
  end

  # 繰り上がり処理
  def do_carry(a)
    cr = 0  # 繰り上がり
    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
  end

  # 結果出力
  def display(a, b, z)
    # 上位桁の不要な 0 を削除するために、配列サイズを取得
    aLen = D_MAX; bLen = D_MAX; zLen = 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 ]====
  end
end

# メイン処理
begin
  # 計算クラスインスタンス化
  obj_calc = MultiplyToomCook3.new

  # 乗算 ( Toom-Cook 法 )
  obj_calc.calc_toom_cook
rescue => e
  # エラーメッセージ
  puts "[例外発生] #{e}"
end

2. 実行

実際に実行して検証してみる。

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
$ ruby multiply_toom_cook_3.rb
a =
4345367000 0015558046 5992851545 8392322526 6661657161
2940646222 3693630633 2878928428 2931075189 4459942962
0472047143 1713204503 7429609429 7320661140 5711218714
8538514523 9923578665 1579065598 3315649556 2636468353
2850188038 2090122465 2291725695 6708063266 7932721494
7942319492 9163030723 9638085573 9503746353 7468715593
8041892365 3487011431 2123396480 0444130541 4830691976
6375317951 4967144872 8029471638 9868078876 6991300561
7275325293 3147458058 7336424609 4074817783 0788334840
6091902995 9132761677 5255524121 1237390448 8301180552
0485182215 7793237999 7335435793 2856480756 3632388619
6682988756 9408135690 9580896340 3482838802 3288833606
0032864192 1432332927 2095702302 4210503951 0557348443
4464495302 7639971189 4148655400 2723740991 0733318320
5303498951 8776188674 253973305
b =
7501324065 2738206911 5039490164 4021680779 1593935265
4517107481 1563095300 4247865767 6579175671 6550946828
8849310928 2032373166 1809936890 4395890008 8505100323
3262151146 5641179972 5027654271 6778904491 2603452658
0104477210 0681082763 6231568633 0763932142 2664695603
6038377177 6784204672 5050316333 9319575588 5651066222
3741358300 5240023426 8409350815 7894695159 1170270888
7057292645 2461606103 7406689505 8225079836 1284499328
0452193943 0049246899 9592674603 6763426074 0219495812
5062777866 5259459760 8835743093 0760692006 9696613714
0412820715 7653833044 2353763341 8309248038 2706034215
3024307811 8585455729 8864419390 7598704512 1560641560
7726629062 7213289104 8971702094 7744875265 4680311778
0379772086 3954773968 9772940293 0418439156 3789388101
9679960719 7742425429 671005985
z =
3259600604 9558376990 1785049682 6721702532 5044456662
7821751560 5036432472 4374806508 0089563122 9955094382
1333781499 2055893283 6740957683 1430717530 3027924720
6720795606 4453432868 2206490351 5092735143 8650604451
9077876082 7869878408 8411792866 7296210361 5290067315
3875194716 5716569026 5501861714 0787645952 9360021510
7591546225 7321872079 8588558834 8221039668 1905946789
5755898057 2475290889 3925276026 1115682662 2595034942
1989465979 9459641436 1822383391 4701051731 6723842532
9085112016 0805208659 7380301971 0575139883 5276329813
9051257188 5386696747 9476206813 2405000008 5014000385
2228602411 7170667435 4071623256 2250293920 8872537198
9011614093 1973290891 6383126505 4534641138 9553720898
2096240322 2778414222 8348650739 7672465365 8649120844
4683221619 8595677967 5204218518 2006601879 7132768680
9939113203 3472472733 7952464367 0925045889 8276313966
4012354898 8510115703 2912673298 1529033667 5058577540
7142956305 7507040532 3467386175 8890359078 9911328777
6785349324 6971158815 4968664190 8788296990 4226330624
8768393813 4049426571 5426114747 1205478779 0601988669
8632035327 0009838500 9172310931 7743393092 6846552160
2161967107 5702127657 0750291819 1733614937 3394110123
6021198173 0409567089 7387534596 6112485570 8480721294
2320621217 6853778480 9999266165 8428469221 5392120811
5298716572 9275964985 1149125056 3067787170 4139504582
2131626469 1343571643 5438670288 6985060164 1273634363
7550116727 3486556597 9439666434 5684036730 1379710374
4199031303 4300325496 4186410270 3714149988 1526135971
2877396833 4115425352 6249841425 3502915946 8328043426
85230425

「標準(筆算)法」や「Karatsuba 法」で計算した結果と一致した。

3. 検証

上記のコードを利用して、乗算回数が何回になるか、計算(100回ループ)にどれくらい時間がかかるかを検証してみた。
参考のため「Karatsuba 法」での乗算テスト結果も掲載している。計算桁数が異なるため単純には比較できないが、1万桁を超えると乗算回数は「Karatsuba 法」より微減し、計算に要する時間も少しずつ短くなっているのが分かる。
だが、やはり C++ 版による計算より莫大に時間がかかっている。
ちなみに、C++ 版では 1000 回ループの時間を計測したが、Ruby 版では時間がかかりすぎるため 100 回ループの時間を計測した。

MULTIPLY_TOOMCOOK_RUBY


今のところ「Karatsuba 法」や「Toom-Cook 法」を使用する局面はありませんが、理解しておいて損にはならないでしょう。

以上。

Comments