Write a function f(a,b,c) that calculates a^b (mod c) in less than 10 seconds.
- a, b < 10^100
- c < 10000.
examples:
f(10^50, 10^50, 54123) = 46555
f(5^99, 10^99, 777) = 1
Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this communityIn GNU dc, there is the operator |
, doing exactly this. Quoted from the manual:
|
Pops three values and computes a modular exponentiation. The first value popped is used as the reduction modulus; this value must be a non-zero number, and should be an integer. The second popped is used as the exponent; this value must be a non-negative number, and any fractional part of this exponent will be ignored. The third value popped is the base which gets exponentiated, which should be an integer. For small integers this is like the sequence Sm^Lm%, but, unlike ^, this command will work with arbitrarily large exponents.
You may assign it to "function" as following:
[|]sf
(also 5 chars...) This assigns |
to f
. You may call it like lfx
.
f=pow
Test
>>> f(10**50, 10**50, 54123)
46555L
>>> f(5**99, 10**99, 777)
1L
Takes the liberty of taking the modulus only on set bits of binary b
, but given the range constraints that won't be a problem.
f a b c|b==0=1|odd b=mod(a*f a(b-1)c)c|0<1=f(mod(a^2)c)(div b 2)c
My humble attempt with Java.
Object a(BigInteger...a){return a[0].modPow(a[1],a[2]);}
How to use :
a(new BigInteger("95"), new BigInteger("56"), new BigInteger("67"));
f a=g a a
g d a b c|b>0=g(mod(d*a)c)a(b-1)c|True=mod d c
This is my algorithm:
->a,b,c{a**b%c}
Finishes in 0.114s for a=10, b=100, c=10000
Python 80 Characters
def f(a,b,c):
x=1;y=a
while b:
if b%2:x=(x*y)%c
y=(y*y)%c;b/=2
return x%c
bcpowmod
You can assign the function name to a variable for 11 bytes:
$f=bcpowmod;
Note: bcpowmod
requires libbcmath, which is built into PHP since version 4.0.4, but only enabled by default on Windows. On Linux you have to explicitly configure PHP with --enable-bcmath
.
f=pow
would work in Python). \$\endgroup\$