Power With a Huge Exponent
Problem
A checksum scheme needs a^b mod 1337, where a is a positive integer up to 2^31 - 1 and the exponent b is so large it arrives as a list of its decimal digits, most significant first, up to 2,000 digits long. Return the result. Turning the digit list into one integer and calling a general power routine is not allowed; work from the digits directly.
Examples
Input: a = 2, b = [3]
Output: 8Input: a = 2, b = [1, 0]
Output: 1024
Why: the exponent is 10, and 2^10 = 1024 is still below 1337Input: a = 1, b = [4, 3, 3, 8, 5, 2]
Output: 1
Why: edge case, 1 to any power is 1Hints
0 / 3
Reading the digits left to right builds the exponent as e = 10 * e + d. What does that step do to a^e?
a^(10e + d) = (a^e)^10 * a^d. So if you already know a^e mod 1337, one more digit costs one tenth power and one small power.
Keep result = a^(prefix of b) mod 1337. For each digit d, set result = power(result, 10) * power(a, d) mod 1337, where power is fast exponentiation by squaring that reduces mod 1337 after every multiply.
Solution
The exponent is never built. Reading its digits left to right, each new digit d turns the exponent e into 10e + d, and the power follows the same rule: a^(10e + d) = (a^e)^10 · a^d. So the running result only needs to be raised to the tenth power and multiplied by a^d, both done with square-and-multiply, and every product is reduced modulo 1337 so the numbers stay small. Each digit costs a constant number of multiplications, so time is O(len(b)), and space is O(1).
MOD = 1337
def fast_pow(x, e):
x %= MOD
out = 1
while e:
if e & 1:
out = out * x % MOD
x = x * x % MOD # square for the next bit
e >>= 1
return out
def huge_power(a, digits):
result = 1
for d in digits: # exponent e becomes 10e + d
result = fast_pow(result, 10) * fast_pow(a, d) % MOD
return result
print(huge_power(2, [3])) # -> 8
print(huge_power(2, [1, 0])) # -> 1024
print(huge_power(1, [4, 3, 3, 8, 5, 2])) # -> 1
print(huge_power(2147483647, [2, 0, 0])) # -> 1198Stuck on the idea rather than the code? Fast Exponentiation covers it.