Ruby - 階乗の多桁計算！

前回は、C++ による「階乗(n!)の多桁計算」のアルゴリズムを紹介しました。

• C++ - 階乗の多桁計算！

今日は、同じアルゴリズムを Ruby で実現してみました。
アルゴリズムについては、上記リンクの記事を参照してください。

実際、大体同じです。

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

0. 前提条件

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

1. Ruby スクリプト作成

File: calc_factorial.rb

#! /usr/local/bin/ruby
#*********************************************
# 階乗計算（1! - 49! 各 64 桁）
#*********************************************
#
class CalcFactorial
  L  = 64            # 計算桁数
  L2 = (L + 7 ) / 8  # 配列サイズ
  N  = 49            # 計算個数

  # 計算・結果出力
  def calc
    s = Array.new(L2, 0)
    s[-1] = 1
    1.upto(N) do |k|
      s = long_mul(s, k)
      printf("%2d!=", k)
      display(s)
    end
  rescue => e
    raise
  end

  private

  # ロング * ショート
  def long_mul(a, b)
    z = Array.new(L2, 0)
    carry = 0
    (L2 - 1).downto(0) do |i|
      w = a[i]
      z[i] = (w * b + carry) % 100000000
      carry = (w * b + carry) / 100000000
    end
    return z
  rescue => e
    raise
  end

  # 結果出力
  def display(s)
    0.upto(L2 - 1) do |i|
      printf("%08d", s[i])
    end
    printf("\n")
  rescue => e
    raise
  end
end

if __FILE__ == $0
  begin
    # 計算クラスインスタンス化
    obj = CalcFactorial.new
    # 階乗計算
    obj.calc
  rescue => e
    $stderr.puts "[#{e.class}] #{e.message}\n"
    e.backtrace.each{ |tr| $stderr.puts "\t#{tr}" }
  end
end

• Gist - Ruby script to compute factorials.

2. 実行

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

$ ruby calc_factorial.rb
 1!=0000000000000000000000000000000000000000000000000000000000000001
 2!=0000000000000000000000000000000000000000000000000000000000000002
 3!=0000000000000000000000000000000000000000000000000000000000000006
 4!=0000000000000000000000000000000000000000000000000000000000000024
 5!=0000000000000000000000000000000000000000000000000000000000000120
 6!=0000000000000000000000000000000000000000000000000000000000000720
 7!=0000000000000000000000000000000000000000000000000000000000005040
 8!=0000000000000000000000000000000000000000000000000000000000040320
 9!=0000000000000000000000000000000000000000000000000000000000362880
10!=0000000000000000000000000000000000000000000000000000000003628800
11!=0000000000000000000000000000000000000000000000000000000039916800
12!=0000000000000000000000000000000000000000000000000000000479001600
13!=0000000000000000000000000000000000000000000000000000006227020800
14!=0000000000000000000000000000000000000000000000000000087178291200
15!=0000000000000000000000000000000000000000000000000001307674368000
16!=0000000000000000000000000000000000000000000000000020922789888000
17!=0000000000000000000000000000000000000000000000000355687428096000
18!=0000000000000000000000000000000000000000000000006402373705728000
19!=0000000000000000000000000000000000000000000000121645100408832000
20!=0000000000000000000000000000000000000000000002432902008176640000
21!=0000000000000000000000000000000000000000000051090942171709440000
22!=0000000000000000000000000000000000000000001124000727777607680000
23!=0000000000000000000000000000000000000000025852016738884976640000
24!=0000000000000000000000000000000000000000620448401733239439360000
25!=0000000000000000000000000000000000000015511210043330985984000000
26!=0000000000000000000000000000000000000403291461126605635584000000
27!=0000000000000000000000000000000000010888869450418352160768000000
28!=0000000000000000000000000000000000304888344611713860501504000000
29!=0000000000000000000000000000000008841761993739701954543616000000
30!=0000000000000000000000000000000265252859812191058636308480000000
31!=0000000000000000000000000000008222838654177922817725562880000000
32!=0000000000000000000000000000263130836933693530167218012160000000
33!=0000000000000000000000000008683317618811886495518194401280000000
34!=0000000000000000000000000295232799039604140847618609643520000000
35!=0000000000000000000000010333147966386144929666651337523200000000
36!=0000000000000000000000371993326789901217467999448150835200000000
37!=0000000000000000000013763753091226345046315979581580902400000000
38!=0000000000000000000523022617466601111760007224100074291200000000
39!=0000000000000000020397882081197443358640281739902897356800000000
40!=0000000000000000815915283247897734345611269596115894272000000000
41!=0000000000000033452526613163807108170062053440751665152000000000
42!=0000000000001405006117752879898543142606244511569936384000000000
43!=0000000000060415263063373835637355132068513997507264512000000000
44!=0000000002658271574788448768043625811014615890319638528000000000
45!=0000000119622220865480194561963161495657715064383733760000000000
46!=0000005502622159812088949850305428800254892961651752960000000000
47!=0000258623241511168180642964355153611979969197632389120000000000
48!=0012413915592536072670862289047373375038521486354677760000000000
49!=0608281864034267560872252163321295376887552831379210240000000000

C++ 版と同じ結果が得られました。

---

以上。