2
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?
2
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?
3
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! – Chris Tobba – 2013-03-11T20:05:06.723
@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 quit because SE is EVIL – 2013-03-11T20:08:09.070
2Or if you don't want to use a global variable: return n?(n%2?x:1)*(x=pow(x,n>>1))*x:1
– Howard – 2013-03-11T20:10:00.763
nice... good programmers out there! – Chris Tobba – 2013-03-11T20:12:30.970
may I ask how old you are(to code so beautiful)? I'm 28 – Chris Tobba – 2013-03-11T20:20:44.543
I'm 0b100010 :) – aditsu quit because SE is EVIL – 2013-03-11T20:24:51.137
1Or 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 – 2013-03-12T10:22:37.787
@peter nice! i love recursive algo`s.. so much logic in such a short form.. – Chris Tobba – 2013-03-12T11:13:14.743
@PeterTaylor don't you think you should post that as an answer? – aditsu quit because SE is EVIL – 2013-03-12T11:34:03.693
I'm not sure from memory whether it's been discussed on meta, but the general etiquette seems to be that for very small improvements by refactoring someone else's code we post a comment rather than an answer. – Peter Taylor – 2013-03-12T11:50:02.560
Ok I don't know much about etiquette, I credited you in my answer – aditsu quit because SE is EVIL – 2013-03-12T12:07:02.977
What am I missing here, why can you not just use the far more simple, literal return n?pow(x,n-1)*x:1
. Is that pow
function doing something more that I don't understand? – Billy Moon – 2013-03-12T13:21:40.150
hmmm... starting to notice difference when not using positive integers... what is that pow
function doing exactly? – Billy Moon – 2013-03-12T13:24:56.843
@BillyMoon n is assumed to be a non-negative integer, and your implementation runs in O(n) instead of O(log n) - compare pow(1, 1000000000). If you don't understand how it works, the basic idea is: x^(2k)=(x^k)^2 and x^(2k+1)=x*(x^k)^2 (^ = power in this context) – aditsu quit because SE is EVIL – 2013-03-12T15:15:21.133
4
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
>,--------------------------------[--------------->,--------------------------------]<[<]>>[<-[->++++++++++<]>>]<->+>>>>>,----------[--------------------------------------<++++++++++<+>[-<[-<<<[->+>+<<]>[-<+>]>>]<[->+<]>>]<[-<+>]>>[-<<+>>]<<<<<[-]>>>[-<[-<<<[->+>+<<]>[-<+>]>>]<[->+<]>>]<[-<<+>>]>>>,----------]>>+<<+<<+<<+<<[-]>[->[>+----------[>-<[-<+>]]<-[->+<]+>++++++++++>]+<<[<----------<]>++++++++++]>[>++++++++++++++++++++++++++++++++++++++++++++++++>]<<<<[>.<<<]++++++++++.
1My brain is totally fucked up – Hugo Dozois – 2013-03-17T18:12:25.373
2
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)
2
{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! – Soham Chowdhury – 2013-04-27T15:04:41.880
0
This feels awfully clumsy but here it goes:
{.2/.{2$\P}{;1}if.*@@1&{*.}*;}:P;
Usage: 2 11P
-> 2048
(Thanks Peter Taylor)
Simple if
s 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 – 2013-03-14T09:44:42.190
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 – 2013-03-14T12:09:43.743
@ChrisTobba, the interpreter is at http://www.golfscript.com/golfscript/golfscript.rb (and requires Ruby). See also http://meta.codegolf.stackexchange.com/a/521/194
– Peter Taylor – 2013-03-14T13:29:58.7670
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.
0
C++, 44 characters
int p(int x,int n){return !n?1:x*p(x,n-1);}
This runs in O(n) time. – Clearer – 2014-10-09T21:51:43.003
0
fairly straightforward port of the java solution
{$[y;*/((y-2*r)#x),2#x .z.s/r:_y%2;1]}
0
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
-1
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... – ThinkChaos – 2014-02-01T23:22:51.343
-1
function p($x,$n){return($n>1)?p($x*$x,$n-1):$x}
1This doesn't compute powers (it instead computes x^(2^(n-1))
) and isn't logarithmic time in n
– Peter Taylor – 2013-06-08T16:48:53.287
other languages, which does it shorter are also welcome! – Chris Tobba – 2013-03-12T17:04:31.820
2Python, 4 chars:
x**n
– Keith Randall – 2013-03-13T21:44:10.353this dosn't count, cause it's not a algo itself. It use an underlying algorithm. – Chris Tobba – 2013-03-14T12:04:33.730
1I think I win this one – dspyz – 2013-03-15T02:22:45.900