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: IisMathwizard !!b/mIEkVC6+3Cvk1 2011-12-29 17:18

>>131
I believe that i specified it as an IDE. i understand what netbeans is and know of its features especially because i have it open as i type...

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2011-12-29 17:18

>>134
I didn't that post the code you idiot. I was responding to the other idiot who thinks Netbeans is an editor (alone).

Name: IisMathwizard !!b/mIEkVC6+3Cvk1 2011-12-29 17:19

>>135
glad to see someone still has a sense of humour

Name: IisMathwizard !!b/mIEkVC6+3Cvk1 2011-12-29 17:21

>>138
i do apologize.. i have way too many people attacking me right now.. I didn't realize that you were having a side conversation

Name: Anonymous 2011-12-29 17:22

>>142
Let's just hope google doesn't ask him what an editor is -(.

Name: kodak_gallery_programmer !!kCq+A64Losi56ze 2011-12-29 17:23

>>143
I was just pointing out one of your many vast misconceptions. Again, computer programming doesn't seem to be your thing.

Name: Anonymous 2011-12-29 17:23

>>141
It's only Kodak-san and some other random retard, Kodak belittles everyone since he's like 5 feet tall or something.

Name: IisMathwizard !!b/mIEkVC6+3Cvk1 2011-12-29 17:23

>>144
ouch... So quick poll... Who doesn't like me and for what reason(s)
so that i may solve this arguement clusterfuck

Name: Anonymous 2011-12-29 17:25

>>134

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.

Name: Anonymous 2011-12-29 17:25

>>147
Just stop talking to them.

Name: Anonymous 2011-12-29 17:27

>>138
why did you reply that to >>134 when 134 has no relation to you, it as pointed at IisMathwizard


Are you trolling?

Name: IisMathwizard !!b/mIEkVC6+3Cvk1 2011-12-29 17:27

>>149
kthen... so does this mean that the arguements have been resolved
?

Name: Anonymous 2011-12-29 17:29

>>151
Yes you are new to programming, everyone has been at some point. Everybody makes mistakes.

Name: Anonymous 2011-12-29 17:31

>>147

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!

Name: IisMathwizard !!b/mIEkVC6+3Cvk1 2011-12-29 17:31

>>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: Anonymous 2011-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

Name: Anonymous 2011-12-29 17:32

The jews are after me.

Name: Anonymous 2011-12-29 17:33

>>154
could you change your name to fit something that actually makes sense. You're clearly not good at math nor a wizard by any means.

Name: IisMathwizard !!b/mIEkVC6+3Cvk1 2011-12-29 17:35

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

Name: Anonymous 2011-12-29 17:37

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

Name: IisMathwizard !!b/mIEkVC6+3Cvk1 2011-12-29 17:43

bye then. Happy coding...

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