2011年7月25日星期一

Modular exponentiation

這一篇也是預備材料,為了下一篇文章所準備的function。Modular exponentiation很簡單,如果要計

2 500000000000000000 mod 37
是多少呢?即使Python有不限長度的int(Python 3)/long(Python 2),但也受限於電腦速度和RAM。所以若要計算,可以先將exponent轉為二進制,每一digit皆是前digit的square,只要binary digit是1便乘和計mod。

>>> bin(500000000000000000)
'0b11011110000010110110101100111010011101100100000000000000000'

def mod_exp(base, exponent, mod):
    """Modular exponentiation through binary decomposition.

    >>> mod_exp(2, 12345678, 37)
    36
    >>> mod_exp(7, 10 **200000, 853)
    787
    """
    x = 1
    power = base % mod
    for i in bin(exponent)[:1:-1]:
        if i == '1':
            x = x * power % mod
        power = power ** 2 % mod
    return x

這個function很簡單,bin(exponent)[:1:-1]將exponent轉為binary string,因為要由power 0開始計,故step -1,然後read到第二個character(index 1) "b"便停(exclusive)。

>>> mod_exp(2, 500000000000000000, 37)
7

試過用C方法,loop住right shift計而不用bin,但反而更慢,可能因為Python int是obj,而不像C的int,是真的binary integer,所以採用這方法。

沒有留言:

發佈留言