gistfile1.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

"""
    任意精度整数
        加減
            演算子オーバーロードから受けた左辺と右辺の正負と大小
            から、演算結果の正負を予測し addition や subtraction
            に割り振る
        乗算
            整数リストを乗算し、桁整理した後に双方の符号を乗算します
        除算
            桁を合わせて減算を繰り返す
"""

import unittest


class TestBigInt(unittest.TestCase):

    def testBigInt(self):
        from random import random

        # ランダム値の範囲
        t = 10000000000

        for _ in xrange(100):
            pre = int((random() * t) - t / 2)
            prebig = BigInt(pre)

            post = int((random() * t) - t / 2)
            postbig = BigInt(post)

            # add
            self.assertEqual(prebig + postbig, pre + post)
            # sub
            self.assertEqual(prebig - postbig, pre - post)
            # mul
            self.assertEqual(prebig * postbig, pre * post)
            # div
            if post != 0:
                if prebig.sign * postbig.sign < 0 and pre % post != 0:
                    # python2 では割り切れない long / -long において
                    # 値が繰り下がる現象が発生する
                    self.assertEqual(prebig / postbig, pre / post + 1)
                else:
                    self.assertEqual(prebig / postbig, pre / post)


# split string to N length
def split_at_nth(string, n, mapping=None):
    if mapping:
        return [mapping(string[pos:pos+n]) for pos in range(0, len(string), n)]
    else:
       return [string[pos:pos+n] for pos in range(0, len(string), n)]


class BigInt(object):
    """
        任意精度整数クラス

        sign: このクラスの符号
        integers: リトルエンディアンの整数リスト
    """
    _SLICE_DIGIT = 10000

    def __init__(self, value, sign=1):
        self.sign = 1
        self.integers = []

        if isinstance(value, (int, long)):
            if sign == -1 or value < 0:
                self.sign = -1
                value = abs(value)
            if value == 0:
                self.sign = 1
                self.integers.append(0)
            while value:
                self.integers.append(value % BigInt._SLICE_DIGIT)
                value /= BigInt._SLICE_DIGIT
        elif isinstance(value, list):
            self.sign = sign
            self.integers = value[:]

            if value == [0]:
                self.sign = 1

        elif isinstance(value, BigInt):
            self.sign = value.sign
            self.integers = value.integers[:]
        else:
            # 文字列などは実装しません
            pass
        self.organizedigit(self.integers)

    def __repr__(self):
        s = ''
        if self.sign == -1:
            s += '-'
        return s + BigInt.tostring(self.integers)

    def __eq__(self, other):

        v1 = self.integers

        if isinstance(other, BigInt):
            v2 = other.integers
        elif isinstance(other, (int, long)):
            v2 = BigInt(other).integers
        else:
            return False
        
        if len(v1) != len(v2):
            return False

        for i in xrange(len(v1)):
            if v1[i] != v2[i]:
                return False

        return True

    @staticmethod
    def tostring(values):
        """ 整数リストを文字列に変換します """

        s = str(values[-1])

        for i in xrange(len(values) - 2, -1, -1):
            s += '%04d' % values[i]

        return s

    @staticmethod
    def organizedigit(v):
        """ 繰り上げと繰り下げをします """

        values = v[:]

        # 繰り上げ
        for i, value in enumerate(values):
            overflow = value / BigInt._SLICE_DIGIT
            if overflow:
                while i + 1 >= len(values):
                    values.append(0)
                values[i] %= BigInt._SLICE_DIGIT
                values[i + 1] += overflow

        # 繰り下げ
        for i in xrange(len(values)):
            if values[i] < 0:
                values[i+1] -= 1
                values[i] += BigInt._SLICE_DIGIT

        # 最上位桁に 0 があれば消去します
        for i in range(1, len(values))[::-1]:
            if values[i]:
                break
            values.pop()

        return values

    @staticmethod
    def bigabslt(b1, b2):
        """ BigInt の絶対値について b1 > b2 を行います """
        return BigInt.abslt(b1.integers, b2.integers)

    @staticmethod
    def bigabsle(b1, b2):
        """ BigInt の絶対値について b1 >= b2 を行います """
        return BigInt.absle(b1.integers, b2.integers)

    @staticmethod
    def abslt(v1, v2):
        """ 整数リストについて v1 > v2 を行います """

        if len(v1) > len(v2):
            return True
        elif len(v1) < len(v2):
            return False

        for i in range(len(v1))[::-1]:
            if v1[i] != v2[i]:
                return v1[i] > v2[i]

        return False

    @staticmethod
    def absle(v1, v2):
        """ 整数リストについて v1 >= v2 の比較を行います """

        if v1 == v2:
            return True

        return BigInt.abslt(v1, v2)

    @staticmethod
    def addition(v1, v2):
        """ 整数リスト v1, v2 を加算します """

        if len(v1) >= len(v2):
            result, other = v1[:], v2
        else:
            result, other = v2[:], v1

        for i in xrange(len(other)):
            result[i] += other[i]

        return BigInt.organizedigit(result)

    @staticmethod
    def subtraction(v1, v2):
        """ 整数リスト v1, v2 を減算します """
        # Note: must be v1 >= v2

        result, other = v1[:], v2

        for i in xrange(len(other)):
            result[i] -= other[i]

        return BigInt.organizedigit(result)

    @staticmethod
    def multiplication(v1, v2):
        """ 整数リスト v1, v2 を乗算します """

        result = []

        for d1, value1 in enumerate(v1):
            for d2, value2 in enumerate(v2):
                tmp = value1 * value2
                if len(result) <= (d1 + d2):
                    result.append(0)
                result[d1 + d2] += tmp

        return BigInt.organizedigit(result)

    @staticmethod
    def division(v1, v2):
        """ 整数リストの除算 """
        # 1. 桁差を出します
        # 2. 桁を揃えます
        # 3. 減算を繰り返します
        # 4. 減算できなくなったら(2)に戻ります
        # 5. 分子<分母に到達したら終了

        s1 = BigInt.tostring(v1)
        s2 = BigInt.tostring(v2)

        diff = len(s1) - len(s2)

        if diff < 0:
            return [0]

        quotient = BigInt(0)
        values = v1[:]

        for p in range(diff + 1)[::-1]:
            s = '1' + ('0' * p)
            l = split_at_nth(s, 4, int)[::-1]
            sub = BigInt.multiplication(v2, l)

            while BigInt.absle(values, sub):
                values = BigInt.subtraction(values, sub)
                quotient = quotient + BigInt(l)

        return BigInt.organizedigit(quotient.integers)

    # 以下演算子オーバーロード
    def __add__(self, other):
        if self.sign == other.sign > 0:
            # (+self) + (+other)
            values = BigInt.addition(self.integers, other.integers)
            return BigInt(values)
        elif self.sign * other.sign < 0:
            # (-self) + (+other) or (+self) + (-other)
            if self.integers == other.integers:
                return BigInt(0)
            bigger, smaller = (self, other) if BigInt.bigabslt(self, other) \
                                else (other, self)
            values = BigInt.subtraction(bigger.integers, smaller.integers)
            return BigInt(values, bigger.sign)
        else:
            # (-self) + (-other)
            values = self.addition(self.integers, other.integers)
            return BigInt(values, -1)

    def __sub__(self, other):
        if self.sign > other.sign:
            # (+self) - (-other)
            values = BigInt.addition(self.integers, other.integers)
            return BigInt(values)
        elif self.sign < other.sign:
            # (-self) - (+other)
            values = BigInt.addition(self.integers, other.integers)
            return BigInt(values, -1)
        else:
            if self.integers == other.integers:
                return BigInt(0)
            elif self.sign == 1:
                if BigInt.bigabslt(self, other):
                    # (+self) - (+other) and self > other
                    values = BigInt.subtraction(self.integers, other.integers)
                    return BigInt(values)
                else:
                    # (+self) - (+other) and other > self
                    values = BigInt.subtraction(other.integers, self.integers)
                    return BigInt(values, -1)
            else:
                if BigInt.bigabslt(self, other):
                    # (-self) - (-other) and |self| > |other|
                    values = BigInt.subtraction(self.integers, other.integers)
                    return BigInt(values, -1)
                else:
                    # (-self) - (-other) and |other| > |self|
                    values = BigInt.subtraction(other.integers, self.integers)
                    return BigInt(values)

    def __mul__(self, other):
        # (self.sign * other.sign) * (self.integers * other.integers)
        values = BigInt.multiplication(self.integers, other.integers)
        return BigInt(values, self.sign * other.sign)

    def __div__(self, other):
        # (self.sign * other.sign) * (self.integers / other.integers)
        values = BigInt.division(self.integers, other.integers)
        return BigInt(values, self.sign * other.sign)


if __name__ == '__main__':
    unittest.main()