recursive power algorithm

Have a look at my (javascript) version of a O(log(n)) xn 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?

• other languages, which does it shorter are also welcome! Commented Mar 12, 2013 at 17:04
• Python, 4 chars: x**n Commented Mar 13, 2013 at 21:44
• this dosn't count, cause it's not a algo itself. It use an underlying algorithm. Commented Mar 14, 2013 at 12:04
• I think I win this one Commented Mar 15, 2013 at 2:22

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

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


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)

• nice, but it's not a real recursion cause of the glob. var.. but never mind its not bad! Commented Mar 11, 2013 at 20:05
• @ChrisTobba Well, it is recursive, the variable doesn't have to be global as the value is only used in the same invocation. It's just shorter to make it (implicitly) global. You could add "var t" before the return to make it local. Commented Mar 11, 2013 at 20:08
• Or if you don't want to use a global variable: return n?(n%2?x:1)*(x=pow(x,n>>1))*x:1 Commented Mar 11, 2013 at 20:10
• nice... good programmers out there! Commented Mar 11, 2013 at 20:12
• Or for one character less and a different perspective on the structure, return(n%2?x:1)*(x=n?pow(x,n>>1):1)*x Commented Mar 12, 2013 at 10:22
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)

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

• Love the :P at the end of the first one! Commented Apr 27, 2013 at 15:04

GolfScript - 33

This feels awfully clumsy but here it goes:

{.2/.{2$\P}{;1}if.*@@1&{*.}*;}:P;  Usage: 2 11P -> 2048 (Thanks Peter Taylor) • Simple ifs can often be replaced by bool{...}*. In the case of \1&{*}{\;}if (12 ch) observe that the * doesn't care about the order of its arguments, so could be \1&{\*}{\;}if (13 ch); now reorder things so that the common \  is unnecessary: a bit of work shows that @@1&{*}{;}if (12 ch) is equivalent. But now the else clause does virtually nothing; refactor via @@1&{*.}{}if; (13 ch) to @@1&{*.}*; (10 ch). I haven't checked whether a similar elimination can be performed on the first if. Commented Mar 14, 2013 at 9:44 • its unreadable for me.. but also nice! On golfscript.com i doesn't found an interpreter for that.. Is it only a pseudo code language? Commented Mar 14, 2013 at 12:09 • @ChrisTobba, the interpreter is at golfscript.com/golfscript/golfscript.rb (and requires Ruby). See also meta.codegolf.stackexchange.com/a/521/194 Commented Mar 14, 2013 at 13:29 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. C++, 44 characters int p(int x,int n){return !n?1:x*p(x,n-1);}  • This runs in O(n) time. Commented Oct 9, 2014 at 21:51 k4 (38) fairly straightforward port of the java solution {$[y;*/((y-2*r)#x),2#x .z.s/r:_y%2;1]}

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


x^0 = 1
x^2 = x * x
x^n | odd  x = x * x^(n-1)
| even x = x ^ (ddiv2) ^ 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


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.

• You have not written an algorithm as the question asks, you're using Python's builtin algorithms. In JS it can be done with Math.pow(), so this is in no way interesting... Commented Feb 1, 2014 at 23:22

PHP

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

• This doesn't compute powers (it instead computes x^(2^(n-1)) ) and isn't logarithmic time in n Commented Jun 8, 2013 at 16:48