Amazon.co.jp ウィジェット
スポンサードリンク

2010年02月06日

nの階乗計算(nは任意)[2]

Python の long がそんなに賢くなかった場合どうやるべきか、ちょっと考えてみました。計算可能な数(ここでは分かりやすく10進4桁)ごとに桁を区切って計算します。

なお、階乗計算をやってみたかっただけなので加算・乗算しか定義していません。


# -*- coding: utf-8 -*-

import copy
import operator

class MyLong(object):
    """ 10進数で4桁ごとに値を保持するオリジナル数値型 """

    def __init__(self, value):
        """ 初期化
         * リスト: 4桁ずつの値リストとして扱う
         * 文字列: 数値文字列として扱う
         * 数値: 与えられた数値と同じ数として扱う
        """
        if isinstance(value, list) and self._is_valid(value):
            self.value = value
        elif isinstance(value, basestring):
            vals = []
            while value:
                if value:
                    vals.append(int(value[-4:]))
                    value = value[:-4]
            self.value = list(reversed(vals))
        elif isinstance(value, int) or isinstance(value, long):
            vals = []
            while value:
                value, val = value / 10000, value % 10000
                vals.append(val)
            self.value = list(reversed(vals))
        else:
            raise ValueError

    def _is_valid(self, val):
        """ self.value 値として妥当かチェック """
        if not isinstance(val, list):
            return False
        for v in val:
            if not isinstance(v, int):
                return False
            if i<0 or i>=10000:
                return False
        return True

    def __str__(self):
        return str(self.value[0]) + "".join(["%04d" % v for v in self.value[1:]])

    def __repr__(self):
        return "%sML" % str(self)

    def __len__(self):
        return len(self.value)

    def __add__(self, other):
        result = []
        nd = max(len(self), len(other))
        lhs = copy.copy(self.value)
        rhs = copy.copy(other.value)
        car = 0
        for i in xrange(nd):
            try:
                a = lhs.pop()
            except IndexError:
                a = 0
            try:
                b = rhs.pop()
            except IndexError:
                b = 0
            sum, car = (a+b+car) % 10000, (a+b+car) / 10000
            result.append(sum)
        if car:
            result.append(car)
        return MyLong(list(reversed(result)))

    def __mul__(self, other):
        lhs = copy.copy(self.value)
        rhs = copy.copy(other.value)

        # 筆算の各段の計算
        car = 0
        lines = []
        for i, a in enumerate(reversed(rhs)):
            lines.append([])
            for b in reversed(lhs):
                mul, car = (a*b+car) % 10000, (a*b+car) / 10000
                lines[i].append(mul)
            if car:
                lines[i].append(car)
            lines[i].reverse()
            # 次の計算のための桁揃え
            for ii in xrange(i):
                lines[i].append(0)

        # 集計(各段の和をとる)
        return reduce(operator.add, [MyLong(l) for l in lines])

    @classmethod
    def factorial(cls, n):
        """ 階乗計算 """
        return reduce(operator.mul, [cls(i) for i in xrange(1, n+1)])

こんな感じで計算できます。


    >>> foo = MyLong('123456789')
    >>> print foo
    123456789
    >>> foo.value
    [1, 2345, 6789]
    >>> a = MyLong("10000")
    >>> a.value
    [1, 0]
    >>> a
    10000ML
    >>> a+a
    20000ML
    >>> b = MyLong("123456789")
    >>> a+b
    123466789ML
    >>> a*b
    1234567890000ML
    >>> MyLong.factorial(10)
    3628800ML
    >>> MyLong.factorial(20)
    2432902008176640000ML
    >>> MyLong.factorial(30).value
    [2, 6525, 2859, 8121, 9105, 8636, 3084, 8000, 0]

ちゃんと計算できているみたいですね!

タグ:Python
posted by junya at 11:23 | Comment(0) | TrackBack(0) | 日記 | このブログの読者になる | 更新情報をチェックする

nの階乗計算(nは任意)

n の階乗を求めよ(nは任意)

このクイズを見たとき、「ワンライナーで書けるじゃん」と思いました。


>>> import operator
>>> factorial = lambda n: n==0 and 1 or reduce(operator.mul, xrange(1, n+1))
>>> factorial(10)
3628800

でも、階乗は結果が指数関数的に増大します。 int をオーバーフローしたらどうなるのでしょうか。


>>> factorial(100)
933262154439441526816992388562667004907159682643
816214685929638952175999932299156089414639761565
182862536979208272237582511852109168640000000000
00000000000000L

maxint を超えたら自動的に long になるのは良いとしても、 64 bit 長整数型の最大値も 9223372036854775807 のはず。とっくに超えているのにエラーが発生せず、どうやら正しい結果が出ています。上記の値は何型で保存され、オブジェクトサイズはどのくらいなのでしょうか。調べてみます。


>>> for i in xrange(50):
...   r = factorial(i)
...   print i, sys.getsizeof(r), type(r), r
...
0 12 <type 'int'> 1
1 12 <type 'int'> 1
2 12 <type 'int'> 2
3 12 <type 'int'> 6
4 12 <type 'int'> 24
5 12 <type 'int'> 120
6 12 <type 'int'> 720
7 12 <type 'int'> 5040
8 12 <type 'int'> 40320
9 12 <type 'int'> 362880
10 12 <type 'int'> 3628800
11 12 <type 'int'> 39916800
12 12 <type 'int'> 479001600
13 20 <type 'long'> 6227020800
14 20 <type 'long'> 87178291200
15 20 <type 'long'> 1307674368000
16 20 <type 'long'> 20922789888000
17 22 <type 'long'> 355687428096000
18 22 <type 'long'> 6402373705728000
19 22 <type 'long'> 121645100408832000
20 24 <type 'long'> 2432902008176640000
21 24 <type 'long'> 51090942171709440000
22 24 <type 'long'> 1124000727777607680000
23 24 <type 'long'> 25852016738884976640000
24 26 <type 'long'> 620448401733239439360000
25 26 <type 'long'> 15511210043330985984000000
26 26 <type 'long'> 403291461126605635584000000
27 28 <type 'long'> 10888869450418352160768000000
28 28 <type 'long'> 304888344611713860501504000000
29 28 <type 'long'> 8841761993739701954543616000000
30 30 <type 'long'> 265252859812191058636308480000000
31 30 <type 'long'> 8222838654177922817725562880000000
32 30 <type 'long'> 263130836933693530167218012160000000
33 32 <type 'long'> 8683317618811886495518194401280000000
34 32 <type 'long'> 295232799039604140847618609643520000000
35 32 <type 'long'> 10333147966386144929666651337523200000000
36 34 <type 'long'> 371993326789901217467999448150835200000000
37 34 <type 'long'> 13763753091226345046315979581580902400000000
38 34 <type 'long'> 523022617466601111760007224100074291200000000
39 36 <type 'long'> 20397882081197443358640281739902897356800000000
40 36 <type 'long'> 815915283247897734345611269596115894272000000000
41 36 <type 'long'> 33452526613163807108170062053440751665152000000000
42 38 <type 'long'> 1405006117752879898543142606244511569936384000000000
43 38 <type 'long'> 60415263063373835637355132068513997507264512000000000
44 40 <type 'long'> 2658271574788448768043625811014615890319638528000000000
45 40 <type 'long'> 119622220865480194561963161495657715064383733760000000000
46 40 <type 'long'> 5502622159812088949850305428800254892961651752960000000000
47 42 <type 'long'> 258623241511168180642964355153611979969197632389120000000000
48 42 <type 'long'> 12413915592536072670862289047373375038521486354677760000000000
49 42 <type 'long'> 608281864034267560872252163321295376887552831379210240000000000

おお、long 型でありながらサイズが少しずつ増えている!

Python マニュアルを見ると以下のように書かれています。

Plain integers (also just called integers) are implemented using long in C, which gives them at least 32 bits of precision (sys.maxint is always set to the maximum plain integer value for the current platform, the minimum value is -sys.maxint - 1). Long integers have unlimited precision. Floating point numbers are implemented using double in C. All bets on their precision are off unless you happen to know the machine you are working with.

"Long integers have unlimited precision" だなんて素晴らしい気遣い。いくらでも大きな値を扱えるんですね。結局、はじめに示した factorial 関数はそのままで良いようです。

posted by junya at 08:26 | Comment(0) | TrackBack(0) | 日記 | このブログの読者になる | 更新情報をチェックする
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。