Ive asked this everywer already but peopl seem too lame to make even a simple program like so i hope the mighty anon programers of 4chan are more skilled
what im trying to do is to Write a method taking two parameters x and n that computes the nth power of x without using ^ or declaring a new variable inside the method or using Math lib.
and it has to be coded in JAVA (i know it sux but dont ask why i use dat shit)
hep plox!
using stack space when it isn't necessary is always a waste of space and time, and should always be considered sub optimal, even when you have enough resources to afford it without crashing.
you've found a situation that is very common on the internet, and in the business world, and in academia, where people get off to acting like they know more than others about some kind of distinguished subject. Kudos on not playing into it yourself there friend. In this test, you have stayed committed to science!
>>152
alright then... One last call... anyone else want to say something about my programming skill/ mother/ Google dream's/ n00b status/ my unemployment (ima student if you hadn't read the comment about it before)
Name:
Anonymous2011-12-29 17:31
>>148 argues stack overflow
proven wrong now argues waste of space and time
you just can't seem to admit you're wrong can you?
the power recursive is just as fast as the iterative as well you can go time it yourself the difference is less than a few hundred milliseconds for powers up to 10000.
The fact that you're arguing over space is just funny. elegance solutions > shit code any day.
If the JVM supported tail recursive like other languages it wouldn't even be a problem since it would be OPTIMIZED
>>157
no... I am most doubtful of your demoting comment. I am quite good at mathematics thank you. >>155
I think we went over this already so im not going to reiterate it for you.
Because this came up a few times...:
public class someClass{
static int count = 0;
static boolean neg = false;
static int v = 1;
public static void main(String[] args){
System.out.println(powerUp((int) Integer.parseInt(args[0]),(int)Integer.parseInt(args[1])) + "");
}
public static double powerUp(int x, int n){
count = 0;
neg = false;
if(n < 0){
n = -1 *n;
neg = true;
}
for(;count < n; count++){
v = v * x;
}
if(neg){
return (1/(double)v);
}
return v;
}
}
>>158
still trying to strawman off topic back to your mistake?
Please stop posting about it, no one has cared about it nor did we ask for you to show a correct solution.
pushing around a stack pointer a couple thousand times when you don't need to do will take more time than necessary. The difference may only be a constant factor, but you'll feel it if your routine is called heavily.
>>160
thank you, go back to your imageboards and never comes back.
>>161 If the JVM supported tail recursive like other languages it wouldn't even be a problem since it would be OPTIMIZED
yes recursion in java is shit at the moment when used for anything heavy and big but a simple problem like this which is most likely for simple academia work isn't going to matter
Name:
Anonymous2011-12-29 17:49
>>162
But it's best practice not to use recursion either way.
and almost none of the solutions posted in here made use of tail recursion. Tail recursive calls need to look like:
int f(int x) {
return g(x - 1);
}
this can't be tail call optimized
int f(int x) {
return x*g(x - 1);
}
It needs to call g, get the return value, and then multiply by x. That multiply by x prevents a tail call, which would, in one way or another, jump to g with x - 1 as a parameter and its return value would go to the caller of f.
Name:
Anonymous2011-12-29 17:51
>>164
Java doesn't support tail recursion, that's why no one made a solution that looked like that.
tail calls and nice, and they generalize of iteration with loops, but not too many programmers are familiar with it. When writing enterprise code, I'll write it out tail call style and then do a translation to loops sometimes. It helps get things correct the first time you write it.
IisMathwizard, congratulations. You won the prize of the most retarded and annoying /prog/ spammer up to date.
1. IisMathwizard.
2. kodak-kun.
3. ``in Lisp'' guy.
4. FrozenVoid.
public class Exp{
public static void main(String[] args){
System.out.println(pow(2,30));
System.out.println(pow(2.0,30)); //tests
System.out.println(pow(2.0,-2));
}
public static double pow(double base, int exp){
if(exp < 0) return 1 / pow(base, -exp);
double ans = 1.0;
for(;exp > 0;--exp) ans *= base;
return ans;
}
}
When IisMathwizard said he was a student, he meant high-school. He is 16 years old and makes the claim of 5 years programming experience. He is notably immature; but so is Kodak-san.
Technically, the C code might already be tail-recursion optimized because it has no tail...?
btw has anyone got a legit example use for tail recursion... I've not seen many, but it always seems to be getting used when it's not really necessary in the first place..?
Eg. fib sequence doing every last node when you only need to do n + (n-1) for n steps...?
Name:
Anonymous2011-12-29 23:48
public int power(int x, int n)
{
if (n == 1)
return x;
x = x*power(x, n-1);
}
public static void main(String[] args)
{
System.println(power(2, 5));
}
But also imagine that these functions make sense. This might be hard to follow, but it is perfectly manageable to deal with these definitions mathematically. If you were to try to implement this using a single loop (and you can but it requires inlining it all into a single function), it becomes impossible to follow. It is still complicated of course, but the logic transfers so to speak have names, f g and h. Here is the loop, assuming the first call comes from f.
int f(int x, int y) {
if(x & 1) {
return f(y, x);
} else {
return g(x - y, x + y, x);
}
}
int g(int x, int y, int z) {
switch((x + y)%(z + 1)) {
case 16: return f(1, z);
case 1: return 6;
case 135: return g(1, 1, z);
default: return h(x + z);
}
}
int h(int x) {
if(x % 9 == 3) {
return h(x % 7);
} else {
return f(x % 7, x % 11);
}
}
--->>
int f(int fx, int fy) {
int gx, gy, gz, hx;
f_label:
if(x & 1) {
//return f(y, x);
int temp1 = y;
int temp2 = x;
x = temp1;
y = temp2;
goto f_label;
} else {
//return g(x - y, x + y, x);
gx = x - y;
gy = x + y;
gz = x;
goto g_label;
}
g_label:
switch((gx + gy)%(gz + 1)) {
case 16: //return f(1, z);
x = 1;
z = gz;
goto f_label;
case 1: return 6;
case 135: //return g(1, 1, z);
gx = 1;
gy = 1;
//gz is fixed.
goto g_label;
default: //return h(x + z);
hx = gx + gz;
goto h_label;
}
h_label:
if(hx % 9 == 3) {
//return h(x % 7);
hx = hx % 7;
goto h_label;
} else {
//return f(x % 7, x % 11);
fx = hx % 7;
fy = hx % 11;
goto f_label;
}
}
--->>
>>182
Its useful in languages without (or awkward) iterative looping.
Other than that its useful in some places like state automata-like code without resorting to mutation. (define (bears z)
(let chomp ([y z] [a 0] [b 0] [c 0])
(if (empty? y)
(list a b c)
(case (car y)
((a) (chomp (cdr y) (add1 a) b c))
((b) (chomp (cdr y) a (add1 b) c))
((c) (chomp (cdr y) a b (add1 c))))
)))
> (bears '(a b b c c c))
'(1 2 3)
> (bears (make-list 10000000 'a))
'(10000000 0 0)
/* Recursive */
unsigned long long rfib(const int n)
{
return (n < 2) ? n : rfib(n - 1) + rfib(n - 2);
}
/* Tail Call */
unsigned long long tcfib(const unsigned long long a,const unsigned long long b,const int n)
{
return n < 1 ? a : n == 1 ? b : tcfib(b,a+b,n - 1);
}
unsigned long long tfib(const int n)
{
return tcfib(0,1,n);
}
int main(int argc,char **argv)
{
int n = atoi(argv[2]);
switch(atoi(argv[1])){
case 0: printf("%d\n",rfib(n)); break;
case 1: printf("%d\n",tfib(n)); break;
}
}
[ @ ~/host/prog/fib ] $ time ./fib 0 30
832040
real 0m0.100s
user 0m0.080s
sys 0m0.008s
[ Fri Dec 30 12:26:49 ]
[ @ ~/host/prog/fib ] $ time ./fib 0 40
102334155
real 0m4.745s
user 0m4.732s
sys 0m0.008s
[ Fri Dec 30 12:29:41 ]
[ @ ~/host/prog/fib ] $ time ./fib 1 40
102334155
real 0m0.007s
user 0m0.000s
sys 0m0.004s
[ Fri Dec 30 12:29:47 ]
[ @ ~/host/prog/fib ] $ time ./fib 1 10000
1242044891
real 0m0.007s
user 0m0.000s
sys 0m0.000s
Why would i choose to do ugly for loops when i can make a nice tail call that gets optimized into one under the hood.
/* Iterative */
unsigned long long ifib(const int a)
{
unsigned long long l = 0,ret = 1,n,i;
if(a < 2) return a;
for(i=1;i<a;++i){
n = l + ret;
l = ret;
ret = n;
}
return ret;
}
/* Recursive */
unsigned long long rfib(const int n)
{
return (n < 2) ? n : rfib(n - 1) + rfib(n - 2);
}
/* Tail Call */
unsigned long long tcfib(const unsigned long long a,const unsigned long long b,const int n)
{
return n < 1 ? a : n == 1 ? b : tcfib(b,a+b,n - 1);
}
unsigned long long tfib(const int n)
{
return tcfib(0,1,n);
}
int main(int argc,char **argv)
{
int n = atoi(argv[2]);
switch(atoi(argv[1])){
case 0: printf("%d\n",rfib(n)); break;
case 1: printf("%d\n",tfib(n)); break;
case 2: printf("%d\n",ifib(n)); break;
}
}
[ @ ~/host/prog/fib ] $ time ./fib 1 1000000
1884755131
real 0m0.013s
user 0m0.008s
sys 0m0.004s
[ Fri Dec 30 12:50:28 ]
[ @ ~/host/prog/fib ] $ time ./fib 1 1000000
1884755131
real 0m0.011s
user 0m0.012s
sys 0m0.000s
[ Fri Dec 30 12:50:30 ]
[ @ ~/host/prog/fib ] $ time ./fib 2 1000000
1884755131
real 0m0.009s
user 0m0.004s
sys 0m0.000s
[ Fri Dec 30 12:50:32 ]
[ @ ~/host/prog/fib ] $ time ./fib 2 1000000
1884755131
real 0m0.017s
user 0m0.000s
sys 0m0.012s
that's with -O3, -O0 the tail call will seg fault @ fib 1000000
that could allow you to skip lots of consecutive ones. But you have to do a squaring every time you shift a bit anyways, so I don't think it would save much.
Name:
Anonymous2013-09-01 23:11
Zermelo began to axiomatize set theory in 1905; in 1908, he published his results despite his failure to prove the consistency of his axiomatic system.