10^e乗の計算法

昨日のProblem 405に関連するが解くのには必要のない情報。
10^e乗の剰余は、Pythonにはpow関数が用意されて簡単に計算できます。例えば、3の10¹⁰乗の123456789の剰余は、

pow(3, 10 ** 10, 123456789)

で求められます。しかし、指数が大きくなってくると段々厳しくなってきます。この関数は指数を計算しなければならないからです。そのため、pow(a, 10 ** e, D)はO(e^1.6)くらいかかると思われます。

もうちょっとなんとかならないでしょうか。

a¹⁰⁰ = (a¹⁰)¹⁰

となります。a^10eなら10乗の計算をe回繰り返せばよいです。このためO(e)程度で計算できるはずです。動かしてみると最初は少し前者の方が速いですが、e = 10⁶から逆転して差が広がります。

e	pow	自作
10^4	9ms	13ms
10^5	119ms	125ms
10^6	2.36s	1.25s
10^7	71.7s	12.4s

import time

def pow10(n, e, D):
    for _ in xrange(e):
        n2 = n * n
        n4 = n2 * n2
        n5 = n4 * n
        n = n5 * n5 % D
    return n

for E in xrange(4, 8):
    N = 10 ** E
    D = 123456789
    t0 = time.clock()
    print E, pow(3, 10 ** N, D), time.clock() - t0
    t0 = time.clock()
    print E, pow10(3, N, D), time.clock() - t0