mk-mode BLOG

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

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

Ruby - 多倍長整数の大小比較!

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

こんばんは。

前回は、C++ による多桁(多倍長)整数同士の大小の比較について紹介しました。

今回は、同じことを Ruby で試してみました。
Ruby では多倍長数はメモリの許す限り使用可能ですが、配列を使った考え方も必要になる局面もあると思います。

0. 前提条件

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

1. 考え方

  • 整数の1桁を1個の配列をみなして考える。
  • 今回は、符号は考慮しない。
  • 通常、2つの整数のうち桁数が大きい方が大きな整数ではあるが、配列を使用しているため最上位の桁にゼロが格納されることもある。よって、それも考慮する。
    つまり、9桁の 234567890 と10桁の 0123456789 の場合は、234567890 > 0123456789 と判定できるようにするということ。

2. Ruby スクリプト作成

例として、以下のようにスクリプトを作成した。

compare_big_digits.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
#*********************************************
# 多倍長整数の大小比較
# ( 符号は考慮しない。1桁1配列 )
#*********************************************
#
D_L = 1000  # 多倍長整数桁数 ( 左辺 )
D_R = 1001  # 多倍長整数桁数 ( 右辺 )

class CompareBigDigits
  def initialize
    # 使用する被加減乗除数・加減乗除数を設定(テストなので乱数を使用)
    @l_0 = Array.new
    @r_0 = Array.new
    0.upto(D_L - 1) {|i| @l_0 << rand(10)}
    0.upto(D_R - 1) {|i| @r_0 << rand(10)}
  end

  # 実処理
  def proc_main
    # 初期設定
    l = Array.new  # 左辺配列
    @l_0.each {|e| l << e}
    r = Array.new  # 右辺配列
    @r_0.each {|e| r << e}

    # 大小比較
    s = compare(l, r)

    # 結果出力
    display(l, r, s)
  end

  # 大小比較
  #
  #   - 引数   : a(多倍長整数・左辺), b(多倍長整数・右辺)
  #   - 返り値 : 1: l > r
  #              0: l = r
  #             -1: l < r
  def compare(l, r)
    # 配列サイズ取得
    size_l = l.size
    size_r = r.size

    # 左辺の右辺より大きい部分
    if size_l > size_r
      (size_l - 1).downto(size_r) do |i|
        return  1 unless l[i] == 0
      end
    end
    # 右辺の左辺より大きい部分
    if size_l < size_r
      (size_r - 1).downto(size_l) do |i|
        return -1 unless r[i] == 0
      end
    end

    # 桁数が同じ場合か、桁数が異なる場合の桁がダブる部分
    ([size_l, size_r].min - 1).downto(0) do |i|
        return  1 if l[i] > r[i]
        return -1 if l[i] < r[i]
    end

    # 等しい場合
    return 0
  end

  # 結果出力
  def display(l, r, s)
    # 左辺
    puts "[LEFT] ="
    (D_L - 1).downto(0) do |i|
        print l[i]
        print " " if (D_L - i) % 10 == 0
        puts      if (D_L - i) % 50 == 0
    end
    puts

    # 右辺
    puts "[RIGHT] ="
    (D_R - 1).downto(0) do |i|
        print r[i]
        print " " if (D_R - i) % 10 == 0
        puts      if (D_R - i) % 50 == 0
    end
    puts

    # 大小比較結果
    puts "[LEFT] #{s == 0 ? "=" : (s > 0 ? ">" : "<")} [RIGHT]"
  end
end

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

  # 実処理
  obj_calc.proc_main
rescue => e
  # エラーメッセージ
  puts "[例外発生] #{e}"
end

3. 実行

実際に実行して検証してみる。
以下は、1,000桁と1,001桁の整数の大小を比較したもの。

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
$ ruby compare_big_digits.rb
[LEFT] =
6120164926 0227028943 7489662756 6975344124 2961800452
7821321926 1700279704 4146880145 5623231169 8986252825
5419907450 5108229980 3004588698 8108361613 5383096319
8527332803 3754848782 8193326376 8120710920 9037526058
1178438953 4767180533 0479324929 8371749688 5681633252
0957327143 7793534501 5463915879 6929327711 6974332381
1399893496 8768573829 9465619243 6739444189 8927369048
1012747951 1770362944 2534643751 9639885653 8032025254
9174316027 1494799847 2915174164 8378336214 5301496956
7924060420 8469610227 0548452925 1445981647 6738871317
4962022114 6902132884 2540698072 5913240473 3752808831
3427338712 6554732275 7463613315 9138203669 4803368864
0833681333 2696755288 5774239515 2902626139 6180906473
5334451548 3616786066 8349662548 0341859561 8785059846
0323102983 1015506690 7549899939 5645132731 0289974751
1391606422 9382745000 7336261202 2372715820 7943707389
8456599966 2412561386 7631162401 5107120847 6796845245
9819558808 5409270648 3668892262 4809928242 9107004702
7503071458 2395578382 2051708990 8809364658 0558994575
1060831628 0814562605 3603502580 2990135693 1981353128

[RIGHT] =
0534954258 0564515901 0909055692 2411872756 5690208707
9657292752 2538565614 4028277510 5482424768 8698766064
1677549178 1604179602 0887312582 2839202381 9755182264
4729383375 8585585694 3434928000 2588134747 8700277795
6364264470 0072589393 2750524791 4684247797 0478152905
4714030254 2846369911 6087259587 6511676983 8790729096
2292247145 1067309877 4161769909 7074088545 0741339259
6213687728 8442274464 3994525011 1600469522 8530729548
9788828577 0839878507 7097276600 2649606712 5254307252
5441724853 7205856860 3840866172 8225738983 0574608079
9699134899 9397096207 8671475077 5326478800 1576742446
0066025107 1307183823 7761059783 2118427317 0553585139
1570257644 1045009054 5134843534 4702996345 6052678332
4146967366 2124258158 4177027402 1556677293 8727719000
6135915874 6790306950 5704949471 2884599840 1551437316
4467952960 0851642656 9436071425 5651326319 1751655268
8974499964 5870255119 7338594597 0379277798 9892591416
1365299766 2574934674 4737372226 7953495817 4782129723
0038481622 0241786716 0690670149 6625606880 8529800412
0960595250 9352225750 1839252795 4933684959 5314081427
9
[LEFT] > [RIGHT]

簡単な内容ですが、多倍長演算を行う際に必要になることもあるでしょう。

以上。

Comments