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

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

• 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 スクリプト作成

File: compare_big_digits.rb

#! /usr/local/bin/ruby
#*********************************************
# 多倍長整数の大小比較
# ( 符号は考慮しない。１桁１配列 )
#*********************************************
#
class CompareBigDigits
  D_L = 1000  # 多倍長整数桁数 ( 左辺 )
  D_R = 1001  # 多倍長整数桁数 ( 右辺 )

  def initialize
    # 使用する被加減乗除数・加減乗除数を設定（テストなので乱数を使用）
    @l, @r = Array.new, Array.new
    rnd_a, rnd_b = Random.new(0), Random.new(1)
    D_L.times { |_| @l << rand(10) }
    D_R.times { |_| @r << rand(10) }
  end

  # 実処理
  def proc_main
    # 大小比較
    s = compare(@l, @r)
    # 結果出力
    display(@l, @r, s)
  rescue => e
    raise
  end

  private

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

if __FILE__ == $0
  begin
    # 計算クラスインスタンス化
    obj = CompareBigDigits.new
    # 実処理
    obj.proc_main
  rescue => e
    $stderr.puts "[#{e.class}] #{e.message}"
    e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
  end
end

• Gist - Ruby script to compare big digits.

3. 実行

以下は、1,000桁と1,001桁の整数の大小を比較したもの。

$ ./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]

---

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

以上。