Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
other languages, which does it shorter are also welcome! – Chris Tobba Mar 12 at 17:04
1  
Python, 4 chars: x**n – Keith Randall Mar 13 at 21:44
this dosn't count, cause it's not a algo itself. It use an underlying algorithm. – Chris Tobba Mar 14 at 12:04
I think I win this one – dspyz Mar 15 at 2:22

8 Answers

up vote 3 down vote accepted

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)
share|improve this answer
nice, but it's not a real recursion cause of the glob. var.. but never mind its not bad! – Chris Tobba Mar 11 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. – aditsu Mar 11 at 20:08
2  
Or if you don't want to use a global variable: return n?(n%2?x:1)*(x=pow(x,n>>1))*x:1 – Howard Mar 11 at 20:10
nice... good programmers out there! – Chris Tobba Mar 11 at 20:12
1  
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 – Peter Taylor Mar 12 at 10:22
show 9 more comments
up vote 2 down vote 
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)

share|improve this answer
up vote 2 down vote

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

share|improve this answer
Love the :P at the end of the first one! – Soham Chowdhury Apr 27 at 15:04
up vote 2 down vote

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

>,--------------------------------[--------------->,--------------------------------]<[<]>>[<-[->++++++++++<]>>]<->+>>>>>,----------[--------------------------------------<++++++++++<+>[-<[-<<<[->+>+<<]>[-<+>]>>]<[->+<]>>]<[-<+>]>>[-<<+>>]<<<<<[-]>>>[-<[-<<<[->+>+<<]>[-<+>]>>]<[->+<]>>]<[-<<+>>]>>>,----------]>>+<<+<<+<<+<<[-]>[->[>+----------[>-<[-<+>]]<-[->+<]+>++++++++++>]+<<[<----------<]>++++++++++]>[>++++++++++++++++++++++++++++++++++++++++++++++++>]<<<<[>.<<<]++++++++++.
share|improve this answer
1  
My brain is totally fucked up – Hugo Dozois Mar 17 at 18:12
up vote 0 down vote

GolfScript - 33

This feels awfully clumsy but here it goes:

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

Usage: 2 11P -> 2048

(Thanks Peter Taylor)

share|improve this answer
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. – Peter Taylor Mar 14 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? – Chris Tobba Mar 14 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 – Peter Taylor Mar 14 at 13:29
up vote 0 down vote

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.

share|improve this answer
up vote 0 down vote

Tcl

proc pow a\ b {set c $a;while {[incr b -1]} {set a [expr $a*$c]};set a}
share|improve this answer
up vote 0 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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