recursive power algorithm

Question

Have a look at my (javascript) version of a O(log(n)) xⁿ algorithm:

function pow(x,n)
{
     return n==0?1:n==1?x:n==2?x*x:pow(pow(x,(n-n%2)/2),2)*(n%2==0?1:x);
}

Can you get it shorter?

Answer 1

If you don't mind using a global variable:

return n?(t=pow(x,n>>1))*t*(n%2?x:1):1

Through some ingenious trickery, Howard devised a clean alternative:

return n?(n%2?x:1)*(x=pow(x,n>>1))*x:1

And Peter Taylor managed to shave one character:

return(n%2?x:1)*(x=n?pow(x,n>>1):1)*x

Even shorter based on ratchet freak's idea:

return(n%2?x:1)*(n?pow(x*x,n>>1):1)

Answer 2

BrainFuck (482 characters)

Solution is modulo 256. Reads n in digit by digit. Each time it sees a new digit d, it raises the current value to the tenth power and then multiplies that by x^d Input must be x followed by single space, followed by n, followed by newline

>,--------------------------------[--------------->,--------------------------------]<[<]>>[<-[->++++++++++<]>>]<->+>>>>>,----------[--------------------------------------<++++++++++<+>[-<[-<<<[->+>+<<]>[-<+>]>>]<[->+<]>>]<[-<+>]>>[-<<+>>]<<<<<[-]>>>[-<[-<<<[->+>+<<]>[-<+>]>>]<[->+<]>>]<[-<<+>>]>>>,----------]>>+<<+<<+<<+<<[-]>[->[>+----------[>-<[-<+>]]<-[->+<]+>++++++++++>]+<<[<----------<]>++++++++++]>[>++++++++++++++++++++++++++++++++++++++++++++++++>]<<<<[>.<<<]++++++++++.

Answer 3

function pow(x,n)
{
     return n==0?1:n==1?x:pow(x*x,n>>1)*pow(x,n&1);
}

removed the n==2 case,

replaced the (n-n%2)/2 with n>>1 (you can also use n&-2)

used x*x instead of pow(pow(...),2)

replaced *(n%2==0?1:x) with *pow(x,n&1)

Answer 4

GolfScript (29 chars as function, 24 chars as block)

{1@@2base-1%{{.@*\}*.*}/;}:P;

without the function wrapper that's

1@@2base-1%{{.@*\}*.*}/;

It's not recursive, but it is O(lg n) time, using the binary decomposition of n. Essentially it takes the fact that the recursive pow can be made tail-recursive with an accumulator and pushes that to its conclusion:

# Stack: a n
1@@
# Stack: 1 a n
2base
# Stack: 1 a [bits of n]
# Reverse the bits so that we loop over them starting at the least significant
-1%
# foreach
{
    # Stack: accum x bit
    # where accum = a^(n%(2^i)) and x = a^(2^i)

    # If the bit is set, multiply the accumulator by x
    {.@*\}*

    # Square x
    .*
}/
# Pop the unwanted a^(2^(2+lg n)) and we're left with a^n
;

(There is also the built-in ? for one char, but I don't think that's in the spirit of this codegolf).

Answer 5

GolfScript - 33

This feels awfully clumsy but here it goes:

{.2/.{2$\P}{;1}if.*@@1&{*.}*;}:P;

Usage: 2 11P -> 2048

(Thanks Peter Taylor)

Answer 6

Java

int pow(int x, int n){
    int t=1;
    return n==0?1:(n%2==0?1:x)*(t=pow(x,n/2))*t;
}

And if t is an initialized class variable, you can remove the first line.

Answer 7

C++, 44 characters

int p(int x,int n){return !n?1:x*p(x,n-1);}

Answer 8

k4 (38)

fairly straightforward port of the java solution

{$[y;*/((y-2*r)#x),2#x .z.s/r:_y%2;1]}

Answer 9

Haskell, 49 characters

x^0=1;x^2=x*x;x^n|odd n=x*x^(n-1)|1>0=x^div n 2^2

readable version:

x^0 = 1
x^2 = x * x
x^n | odd  x = x * x^(n-1)
    | even x = x ^ (d`div`2) ^ 2

The idea to special-case x^2 shamelessly stolen from the asker.

Another 49-character version, requires common subexpression elimination (which GHCi doesn't do in this case) to be efficient:

x^0=1;x^n|odd n=x*x^(n-1)|1>0=x^div n 2*x^div n 2

Answer 10

In python we have 2 methods for doing this :

def p(x,n,l):
    print pow(x,n,l)
def p1(x,n):
    print x**n
p(10,5,52)
p1(10,5)

Output corresponding to it is:

4
100000

The best part in python function is that it helps in modular power also (which is faster than finding power and then mod).In pow (n,m,l) It produces : (n^m)%l as the output.

Answer 11

PHP

function p($x,$n){return($n>1)?p($x*$x,$n-1):$x}