Python - 階乗の多桁計算！

Python 3 で階乗(n!)を多桁計算する方法についての記録です。

0. 前提条件

• LMDE 2 (Linux Mint Debian Edition 2; 64bit) での作業を想定。
• Python 3.6.4 での作業を想定。
• 当方は他のバージョンとの共存環境であり、 python3.6, pip3.6 で 3.6 系を使用するようにしている。（適宜、置き換えて考えること）

1. アルゴリズムについて

当ブログ過去記事を参照。

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

2. Python スクリプトの作成

• 敢えてオブジェクト指向で作成している。
• Shebang ストリング（1行目）では、フルパスでコマンド指定している。（当方の慣習）
• 数値計算ライブラリ NumPy を使用しない。（この程度の計算では、逆に2倍程度時間がかかってしまうため）
• 必要であれば、スクリプト内の定数を変更する。
• 多桁計算のアルゴリズムは自前で実装。

File: calc_factorial.py

#! /usr/local/bin/python3.6
"""
Computation of factorials
"""
import sys
import traceback


class CalcFactorial:
    L  = 64                 # Digits of computation
    L2 = int((L + 7 ) / 8)  # Length of list
    N  = 49                 # Number of computation

    def compute(self):
        """ Computation of factorials """
        try:
            s = [0 for _ in range(self.L2)]
            s[-1] = 1
            for k in range(1, self.N + 1):
                s = self.__long_mul(s, k)
                self.__display(k, s)
        except Exception as e:
            raise

    def __long_mul(self, a, b):
        """ Computation of long * short

        :param  list a
        :param  list b
        :return list z
        """
        try:
            z = [0 for _ in range(self.L2)]
            carry = 0
            for i in reversed(range(self.L2)):
                w = a[i]
                z[i] = (w * b + carry) % 100000000
                carry = int((w * b + carry) / 100000000)
            return z
        except Exception as e:
            raise

    def __display(self, k, s):
        """ Display

        :param int  k
        :param list s
        """
        try:
            print("{:2d}!=".format(k), end="")
            for i in range(0, self.L2):
                print("{:08d}".format(s[i]), end="")
            print()
        except Exception as e:
            raise


if __name__ == '__main__':
    try:
        obj = CalcFactorial()
        obj.compute()
    except Exception as e:
        traceback.print_exc()
        sys.exit(1)

• Gist - Python script to compute factorials.

3. Python スクリプトの実行

まず、実行権限を付与。

$ chmod +x calc_factorial.py

そして、実行。

$ ./calc_factorial.py
 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

---

以上