Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

NEED URGENT HELP

Name: edo-chan 2011-12-28 11:11

sup /prog/

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!

Name: Anonymous 2011-12-29 17:44

>>155

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.

Name: Anonymous 2011-12-29 17:46

>>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: Anonymous 2011-12-29 17:49

>>162
But it's best practice not to use recursion either way.

Name: Anonymous 2011-12-29 17:49

>>155

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: Anonymous 2011-12-29 17:51

>>164
Java doesn't support tail recursion, that's why no one made a solution that looked like that.

Name: Anonymous 2011-12-29 17:51

>>163

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.

Name: Anonymous 2011-12-29 17:52

>>165

It can't support tail calls to other functions, but any language that supports loops can support tail recursion.

Name: Anonymous 2011-12-29 17:53

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.

Name: Anonymous 2011-12-29 17:53

>>167
Java can't do tail recursion.

Go ahead try it for yourself, make something tail recursive in java and make you'll see it overflow like normal recursion.

Name: Anonymous 2011-12-29 17:55

>>169

I said it can support tail recursion, not that it does.

Name: Anonymous 2011-12-29 17:56

>>170
will you suck on my big meaty balls now?

Name: Anonymous 2011-12-29 17:57

how did IisMathwizard Win?

Name: Anonymous 2011-12-29 18:08

>>171
why would this internet discussion battle affect my decision?
>>172
win/loss point of view on discussion considered harmful.

Name: Anonymous 2011-12-29 21:11

Use a global ^^

optimize with exponent-by-squaring

all done

Name: Anonymous 2011-12-29 21:36

Something like



int pTop, CurrentSum, EndSum=1, endCount=0;

function doPower(X, n){

while (endCount!=n){
  CurrentSum = X;
  pTop=1;

  while(pTop*2< n-endCount){
    CurrentSum *= CurrentSum;
    pTop += pTop;
    }

  EndSum *= CurrentSum;
  endCount += pTop;
  }
}

Name: Anonymous 2011-12-29 21:47

lol @ tail recursion... n^256 still does 256 multiplications, and you call it an optimization..?

Name: Anonymous 2011-12-29 21:48

http://rosettacode.org/wiki/Exponentiation_operator#Java

PROPER ENTERPRISE JAVA WAY


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;
   }
}

Name: Anonymous 2011-12-29 21:48

>>176
that's not what tail recursion optimization means

Name: Anonymous 2011-12-29 22:06

>>178

But it does just optimize the 'junk' calls to itself?

Name: Anonymous 2011-12-29 22:15

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.

Name: Anonymous 2011-12-29 22:33

>>179
it turns a tail recursion function into an iterative loop.


Other optimization optimize the method at which you tried to do stuff.

Name: Anonymous 2011-12-29 22:33

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: Anonymous 2011-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));
}

lol

Name: Anonymous 2011-12-29 23:52

>>182
do you even know what tail recursion optimization is?

Name: Anonymous 2011-12-29 23:52

>>182

It can be useful for shifting back and forth between a bunch of different functions. IE, try doing this in a loop:


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) {
    h(x % 7);
  } else {
    f(x % 7, x % 11);
  }
}


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;
  }
}

--->>

Name: Anonymous 2011-12-30 0:12

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

Name: Anonymous 2011-12-30 0:30

>>182

[ Fri Dec 30 12:28:54 ]
[ @ ~/host/prog/fib ] $ cat fib.c
#include <stdlib.h>
#include <stdio.h>

/* 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.

Name: Anonymous 2011-12-30 0:36

>>185 ty // 186 also, though i have no idea what it does =)

looks like a no brainer when given a choice between spaghetti code and just about any alternative =)

small challenge for the readers... see if you can optimize for n^(2^x-1) instead of n^(2^x) ;)

Name: Anonymous 2011-12-30 0:42

>>187

Where's the 'normal' implementation to compare with?

Eg >> 1+1 1+2 2+3 3+5...

Name: Anonymous 2011-12-30 0:51

>>189

[ Fri Dec 30 12:45:42 ]
[ @ ~/host/prog/fib ] $ cat fib.c
#include <stdlib.h>
#include <stdio.h>


/* 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

Name: Anonymous 2011-12-30 1:04

...does a bit of variable switching i guess

hows this?


a=0;
b=1;
for(i=0;i<n;i+=2){
    a+=b;
    b+=a;
    }
ret = b;
if (n%2==1) ret = a;

Name: Anonymous 2011-12-30 1:06

>>188
Its something like:
  void chomp (list y, int a, int b, int c) {
    if (empty_questionmark (y)) {
        return LISP(a, b, c);
    } else {
      switch (car (y)) {
      case SYMBOL_A: chomp (cdr (y), ++a, b, c)); break;
      case SYMBOL_B: chomp (cdr (y), a, ++b, c)); break;
      case SYMBOL_C: chomp (cdr (y), a, b, ++c)); break;
      }
    }
  }
void bears(list z) {
  chomp (z, 0, 0, 0);
}

Name: Anonymous 2011-12-30 1:06

>>191

return n%2 ? b : a;

Name: Anonymous 2011-12-30 1:08

>>188

n^(2^x-1) = (n^(2^x))/n I guess that would be good enough. One could do:

n^(sum_i_to_m(2^i)) = n^(2^(m+1) - 1) = n^(2^(m+1))/n

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: Anonymous 2013-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.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List