mk-mode BLOG

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

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

Ruby - 多桁計算(その2)!

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

こんばんは。

前回は、C++ による「多桁計算」のアルゴリズム(筆算式)の改良版を紹介しました。

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

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

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

記録

0. 前提条件

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

1. Ruby スクリプト作成

今回作成した Ruby ソースは以下の通りです。

calc_big_digits_2.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
#*********************************************
# 多桁計算(筆算方式改良版)
# ( 符号は考慮しない。)
#*********************************************
#
N_A    = 1000                   # 計算桁数 ( 被加減乗除数 )
N_B    =  996                   # 計算桁数 ( 加減乗除数 )
LIMIT  =    4                   # 配列1つあたり桁数
SIZE_A = (N_A - 1) / LIMIT + 1  # 配列サイズ
SIZE_B = (N_B - 1) / LIMIT + 1  # 配列サイズ

class CalcBigDigits
  def initialize
    # 使用する被加減乗除数・加減乗除数を設定(テストなので乱数を使用)
    @a_0 = Array.new
    @b_0 = Array.new
    0.upto(SIZE_A - 1) {|i| @a_0 << rand(10 ** LIMIT)}
    0.upto(SIZE_B - 1) {|i| @b_0 << rand(10 ** LIMIT)}
    @c_0 = rand(10 ** LIMIT);
    puts "A ="; display(@a_0)
    puts "B ="; display(@b_0)
    printf("C =\n%04d\n\n", @c_0)
  end

  # 計算 ( 加算 )
  def calc_add
    # 初期設定
    a = Array.new  # 被加数配列
    @a_0.each {|e| a << e}
    b = Array.new  # 加数配列
    @b_0.each {|e| b << e}

    # 計算・結果出力
    puts "A + B ="
    display(long_add(a, b))
  end

  # 計算 ( 減算 )
  def calc_sub
    # 初期設定
    a = Array.new  # 被減数配列
    @a_0.each {|e| a << e}
    b = Array.new  # 減数配列
    @b_0.each {|e| b << e}

    # 計算・結果出力
    puts "A - B ="
    display(long_sub(a, b))
  end

  # 計算 ( 乗算 )
  def calc_mul
    # 初期設定
    a = Array.new  # 被乗数配列
    @a_0.each {|e| a << e}
    c = @c_0       # 乗数

    # 計算・結果出力
    puts "A * C ="
    display(long_mul(a, c))
  end

  # 計算 ( 除算 )
  def calc_div
    # 初期設定
    a = Array.new  # 被除数配列
    @a_0.each {|e| a << e}
    c = @c_0       # 除数

    # 計算・結果出力
    puts "A / C ="
    display(long_div(a, c))
  end

  # ロング + ロング
  def long_add(a, b)
    z = Array.new([a.size, b.size].max + 1, 0)
    0.upto(a.size - 1) {|i| z[i] = a[i]}
    0.upto(b.size - 1) do |i|
      z[i] += b[i]
      if z[i] >= 10 ** LIMIT
        z[i] -= 10 ** LIMIT
        z[i + 1] += 1
      end
    end
    return z
  end

  # ロング - ロング
  def long_sub(a, b)
    z = Array.new([a.size, b.size].max, 0)
    0.upto(a.size - 1) {|i| z[i] = a[i]}
    0.upto(b.size - 1) do |i|
      z[i] -= b[i]
      if z[i] < 0
        z[i] += 10 ** LIMIT
        z[i + 1] -= 1
      end
    end
    return z
  end

  # ロング * ショート
  def long_mul(a, c)
    z = Array.new(a.size + 1, 0)
    0.upto(a.size - 1) do |i|
      z[i] += a[i] * c
      if z[i] >= 10 ** LIMIT
        z[i + 1] += z[i] / 10 ** LIMIT
        z[i] %= 10 ** LIMIT
      end
    end
    return z
  end

  # ロング / ショート
  def long_div(a, c)
    z = Array.new(a.size, 0)
    (a.size - 1).downto(0) do |i|
      z[i] += a[i] / c
      a[i - 1] += (a[i] % c) * 10 ** LIMIT if i > 0
    end
    return z
  end

  # 結果出力
  def display(s)
    size = s.size
    # 最上位で繰り上がりが無かった場合の処置
     size -= 1 if (s[size - 1] == 0)

    # 1行に配列10個分出力
    (size - 1).downto(0) do |i|
      printf("%04d ", s[i])
      puts if (size - i) % 10 == 0 && i != 0
    end
    puts "\n\n"
  end
end

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

  # 計算 ( 加算 )
  obj_calc.calc_add

  # 計算 ( 減算 )
  obj_calc.calc_sub

  # 計算 ( 乗算 )
  obj_calc.calc_mul

  # 計算 ( 除算 )
  obj_calc.calc_div
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
65
66
67
68
69
$ ruby calc_big_digits_2.rb
A =
4099 5640 2306 3387 7913 8073 4827 5311 9874 6122
6769 9412 5626 6028 7805 0108 6658 6159 0658 1661
0433 6462 9924 7261 8630 4304 1666 0165 9021 6910
9162 0702 4146 5326 2994 4416 5252 5269 6229 2304
 ---< 途中省略 >---
7087 9478 4503 8093 2139 8126 2780 4947 8607 8261
9728 5060 6177 1939 9567 9046 3852 8949 2890 3043
4448 5525 2677 3836 9395 2423 0220 9490 0630 4487
5154 8610 9049 0698 6697 6947 3919 9510 2559 5474

B =
9340 7370 1831 7562 4559 2419 9614 0734 9203 2275
0962 7844 3019 2928 5936 5727 4566 9926 9720 7950
2468 4314 9800 8092 6529 9314 2127 2835 5527 0734
3251 5143 0801 7004 3486 9874 5407 9562 0674 4537
 ---< 途中省略 >---
7626 6646 5134 4249 5754 4515 9821 6929 9567 0233
6349 2579 5409 6974 2750 3457 6046 7234 2261 3675
5632 2258 0597 8003 9226 7030 2072 4437 5867 8464
5730 1298 6182 2091 0157 9887 7813 7704 2595

C =
8498

A + B =
4100 4980 9676 5219 5476 2632 7247 4926 0609 5325
9045 0375 3470 9048 0733 6045 2386 0726 0585 1381
8383 8931 4239 7062 6723 0834 0980 2293 1857 2437
9896 3953 9289 6127 9998 7903 5127 0677 5791 2979
 ---< 途中省略 >---
3476 7105 1150 3227 6389 3880 7296 4769 5537 7828
9962 1409 8756 7349 6542 1796 7310 4996 0124 5304
8124 1157 4935 4434 7399 1649 7251 1562 5068 0355
3619 4341 0347 6880 8788 7105 3807 7324 0263 8069

A - B =
4098 6299 4936 1556 0351 3514 2407 5697 9139 6919
4494 8449 7782 3009 4876 4172 0931 1592 0731 1940
2483 3994 5609 7461 0537 7774 2351 8038 6186 1383
8427 7450 9003 4524 5990 0929 5377 9861 6667 1630
 ---< 途中省略 >---
0699 1851 7857 2958 7890 2371 8264 5126 1677 8694
9494 8711 3597 6530 2593 6296 0395 2902 5656 0782
0772 9893 0419 3239 1391 3196 3190 7417 6192 8619
6690 2880 7750 4516 4606 6789 4032 1696 4855 2879

A * C =
3483 8095 0679 9266 9451 1534 8456 4360 1269 4455
0509 0960 7957 4871 2576 6982 3442 4917 9741 3095
5546 5126 2510 0323 1312 1397 6807 7808 9836 6330
8965 9272 9119 7234 2892 6765 1631 5974 1255 6000
 ---< 途中省略 >---
0245 2844 5129 3794 5752 8053 6182 1901 1058 1806
3194 3799 3725 2406 6312 0769 0841 7624 6555 7553
4906 6009 5469 8995 7295 7009 8937 1743 8155 1033
8052

A / C =
4824 1515 9221 3918 3235 8288 4005 0967 2716 6536
4520 9946 5317 2545 0464 8280 3787 4981 2494 9000
9924 2719 4545 4532 6700 9065 8585 5690 6356 4263
2574 8061 2081 1162 9788 7051 6889 2997 9088 2919
 ---< 途中省略 >---
8947 9263 8860 6840 6848 4497 8560 2433 3499 4424
5385 3919 2959 7481 7095 6750 2768 7631 5474 5873
6701 0502 7862 3013 5791 0594 2834 7246 4851 0811
3856 0379 9775 3234 4901 9707 4511 5921 6944

部分的に電卓で計算してみた結果、計算は合っているようだ。


Ruby の場合、今回のような加減乗除は普通にできますが、もっと大きな数字を扱うような場合(円周率計算等)には、今回のようなアルゴリズムを意識しないといけないでしょう。

ただ、多桁同士の乗算・除算を行う場合は、今回のような筆算方式のアルゴリズムではなく、別のアルゴリズムを使用するようですが。

以上。

Comments