5
\$\begingroup\$

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
\$\endgroup\$

closed as unclear what you're asking by Erik the Outgolfer, ETHproductions, betseg, Cows quack, Rɪᴋᴇʀ Dec 20 '16 at 19:19

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Inbuilt functions disallowed? (f=pow would work in Python). \$\endgroup\$ – Dogbert Feb 11 '11 at 21:41
  • \$\begingroup\$ Is division allowed in this one? What the input? Is it always positive? \$\endgroup\$ – Juan Feb 11 '11 at 21:42
  • \$\begingroup\$ He sets no more restrictions, so there should be no restrictions. \$\endgroup\$ – FUZxxl Feb 11 '11 at 22:03
  • \$\begingroup\$ @Dogbert, @Juan: as FUZxxl said, there are no more restrictions; you can assume that the input is always positive if that helps you. \$\endgroup\$ – Eelvex Feb 11 '11 at 22:19
  • \$\begingroup\$ @Dogbert: I thought you meant pow(x,y) but now it's too late to take it back :) \$\endgroup\$ – Eelvex Feb 11 '11 at 22:37
3
\$\begingroup\$

dc 1 or 5 chars

In 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.

\$\endgroup\$
2
\$\begingroup\$

Python - 5 chars

f=pow

Test

>>> f(10**50, 10**50, 54123)
46555L
>>> f(5**99, 10**99, 777)
1L
\$\endgroup\$
  • \$\begingroup\$ On the one hand, it is implicit that build-in functions that exactly solve the problem should not be used; on the other hand, I learned a new option of pow. \$\endgroup\$ – Eelvex Feb 11 '11 at 22:36
2
\$\begingroup\$

Haskell, 65

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
\$\endgroup\$
2
\$\begingroup\$

Java 56 chars

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"));
\$\endgroup\$
1
\$\begingroup\$

Haskell (54)

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:

  1. let d = a
  2. while b > 0:
    • d <- (d*a)%c
    • b --
  3. Return d%b
\$\endgroup\$
  • \$\begingroup\$ Not sure that algo can handle b=10^50 in less than 10 seconds. \$\endgroup\$ – J B Feb 11 '11 at 23:33
1
\$\begingroup\$

Ruby, 15 bytes

->a,b,c{a**b%c}

Finishes in 0.114s for a=10, b=100, c=10000

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Nice solution but not "golfy" enough for an upvote. \$\endgroup\$ – Eelvex Feb 12 '11 at 22:30
0
\$\begingroup\$

PHP, 8 bytes

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.