macOS java programming help (again)

[phiber optik]

hey all
well i was trying to write some code that would output the first 20 fibonacci numbers, but im having some trouble when i impliment it. whenever i try to run the program (java fibonacci 20) it gives me this error:
Exception in thread "main" java.lang.NoSuchMethodError: main
any help will be appreciated!
here's the code (its a little weird i guess im still learning the language):
import java.util.*;

public class fibonacci {

public void main (String args[]) {
int input = Integer.parseInt(args[0]);
int result = fibonacci(input);
System.out.println(result);
}

public int fibonacci(int x) {
int a;
int b;
b = 1;
while (x > 0) {
a = 0;
a = a + b;
b = a ;
System.out.println(b);
x = x - 1;

}
return 0;
}
}

 

[jsw]

Try changing the method signature to:

public [b]static[/b] void main(String[] args)

 

[phiber optik]

well now it runs, so that helped! Now, the problem is that i get 20 1's. anyone got any ideas how to edit it to make it display 20 fibonacci numbers?

 

[therevolution]

Well, have you examined your logic closely?

Hint: look at the first line of your 'while' loop. You're resetting 'a' to zero every time you loop. You want to perform that initialization before the loop starts, like you did with 'b'.

 

[phiber optik]

yeah that could affect it
but im still getting the same output
hmmm.....

 

[therevolution]

Yeah, I was just trying to give you a starting point.

Try pretending that you are 'executing' your code and keep track of the variable names on a piece of paper. You may have to do a few loops before you see that your algorithm isn't matching up with how it should be, and you can make adjustments from there.

Sorry, I'm a meanyhead when it comes to helping people with their programming problems, because I believe you don't learn much when someone just gives you the answer. You need to learn to step through your code if you're going to be a competent programmer. Start now!

 

[Doctor Q]

Your approach to helping is perfect, therevolution.

Tell us how it goes as you make changes, phiber optik, and we'll answer questions and give tips to help.

 

[phiber optik]

if a = 2
while (something)
b = (a -2) + (a -1)
how do i have the program ignore a = 2 the second time around?

 

[Doctor Q]

You might not even need an if statement, but let's find out.

Sometimes the problem in programs like this is that you try to write the initialization code, and then the loop, because they come in that order, when it's much easier if you start by considering what the loop should do and from that determine what initialization is appropriate.

So let's think about it this way. I assume that you want your a and b variables to represent two consecutive numbers in the Fibonacci sequence. So your while loop is going to repeat a certain number of times computing one more Fibonacci number each time as a and b move through the values. Is that right?

You know the Fibonacci series: 1 1 2 3 5 8 13 21 34 55 etc. So think about a particular case. Suppose a is 5 and b is 8 and you want the code in the loop to change a and b to the next values in the sequence, namely change a to 8 and change b to 13, and to output the 8. What assignment statements and call to System.out.println would do that?

In other words:

As the loop body starts: a=5 and b=8.

After the loop body ends: a=8 and b=13 and the output is 8.​

(If you need an extra variable to use temporarily to store a value, that's fine.)

Once you figure out the assignment and println statements to do what you want for 5 and 8, your loop code is done because the same logic should work for anywhere in the sequence.

And, once you figure that out, THEN figure out how to set a and b before the while loop to make the first Fibonacci values come out. It'll be simple. Assign some small integer value to a and some small integer value to b to make the loop start correctly, either by logic or by trial and error.

It'll be easiest to help you if you post your code. If you put [code] and [/code] tags around it in your forum posts, it'll stay formatted correctly, e.g.,

public static void main (String args[]) {
        int input = Integer.parseInt(args[0]);
        int result = fibonacci(input);
        System.out.println(result);
}

 

[ChrisBrightwell]

Your logic is flawed.

  private static int fib(int x)
  {
    if (x == 0 || x == 1)
      return x; 

    else 
      return fib(x-1) + fib(x-2);
  }

Then your main will look something like this.

  public static void main(String[] args)
  {
    for(int x=0; x<20; x++)
    {
      System.out.println("Input: " + x + ", Output: " + fib(x));
    }
  }

 

[phiber optik]

two questions:

(If you need an extra variable to use temporarily to store a value, that's fine.)

how do you do this? I simply dont have the programming vocab to know how to create a temporary value. Is it an argument for a variable?
And does the value of a become reset every time the code loops, or is the altered value retained into the next loop, ignoring the initialization out of the loop?
Thanks tons for the input!!

 

[phiber optik]

and here's the code i have so far: (thanks for the /code tip)

 import java.util.*;

public class fibonacci {

    public static void main (String args[]) {
	int input = Integer.parseInt(args[0]);
	int result = fibonacci(input);
	System.out.println(result);
}

	public static int fibonacci(int x) {
		int a;
		int b;
		int c;
		c = 0;
		a = 2;
		while (x > 0) {
		
			b = (a - 1) + (a-2);
			
			if (c < 1)
				a = b;
			System.out.println(b);
			x = x - 1;
			
			c = c + 1;
			}
			return 0;
		}
	}

this version simply outputs a whole bunch of -1, but i thought id give you an update. Thanks!

 

[janey]

I still think there's something wrong with your logic.

Maybe here's a pointer or two:

Think about what the fibonacci sequence is, and how you calculate it:
f(n) =

• 0 if n == 0
• 1 if n == 1
• (n-1)+(n-2) if n > 1

Create a temp variable or two to store numbers you might need to calculate the fibonacci numbers, like int firstTempValue = 0 and int secondTempValue = 1

Then, to output the first x numbers of the fibonacci sequence, you could have an if statement for the first two numbers of the sequence (as they can't be calculated), and then have a for loop at the end of the if statement, starting from 2 (like for( int i = 2; i >= x..., where x is the number of fibonacci numbers you want), to calculate the rest of the numbers as needed.

Using the number of fibonacci numbers you want, the fact that you calculate the fibonacci numbers as stated above, and a temp variable or two to store any intermediate result, try to write down a way you can write it, and implement it.


However, just as a heads up, recursion is not the right thing to use in this situation, a la something like

private static int fibonacci ( int x ) {
    if ( x == 0 || x == 1 )
        return x;
    else
        return fibonacci(x-1)+fibonacci(x-2);
}

because there is an easier-to-understand version where you don't need to use recursion at all, and doesn't have the potential problems that go with recursion.

 

[ChrisBrightwell]

and here's the code i have so far: (thanks for the /code tip)

... Did you look at the code I posted?

Your fibonnaci() method is doing too much. The loop should be in your main() method.

 

[janey]

... Did you look at the code I posted?

Your fibonnaci() method is doing too much. The loop should be in your main() method.

nothing wrong with the code you posted, but i'd love to see what it does if you want the first 20000 numbers in the sequence calculated. (oh god just imagine..)

Let me expand with a similar problem you find in a lot of intro books as an example of how to use recursion, and also a big example of why not to use recursion in this particular situation: the factorial problem.

factorial using recursion

int Factorial ( int number )    {
    if ( number == 1 )  {
        return number;
    }
    else    {
        return number * Factorial( number - 1 );
    }
}

factorial using iteration

int Factorial ( int number )    {
    int intermediateValue = 1;
    for ( int factor = 2; factor <= number; factor++ )  {
        intermediateValue = intermediateValue * factor;
    }

    return intermediateValue;
}

Now, given both of those, which one would you pick?
I'd go for the second, cause it's easier to understand, and it's better than the recursive version which would be insane if you were calculating the factorial of, say, 5897923.

Recursion's an awesome tool when used appropriately (i.e. quicksort). When there's a simpler and more efficient way of solving the problem without recursion, it's most definitely not appropriate (Of course, you could argue that a lookup table would be more efficient, but..)

 

[ChrisBrightwell]

nothing wrong with the code you posted, but i'd love to see what it does if you want the first 20000 numbers in the sequence calculated. (oh god just imagine..)

No, I'm well aware of the problem with higher values in this situation ... but he only has to count the first 20 values.

 

[Doctor Q]

two questions:

how do you do this? I simply dont have the programming vocab to know how to create a temporary value. Is it an argument for a variable?
And does the value of a become reset every time the code loops, or is the altered value retained into the next loop, ignoring the initialization out of the loop?
Thanks tons for the input!!

It looks like you figured out how to use temporary variables, e.g., int c ;, but I'm confused what your current plan is since my suggestion (to concentrate on one particular case to figure out the code to put in the while loop) was followed by other proposals. Should I say more about what I had in mind or are you now following another plan?

As janey says, this problem could be solved either with iteration or with recursion. For your purposes, either way would work and either way would be fine since you don't care about the tradeoff between elegance and efficiency.

 

[janey]

No, I'm well aware of the problem with higher values in this situation ... but he only has to count the first 20 values.

Well then, why not a

System.out.println("0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181");

Just kidding.

Yeah, I know in this situation it's not a big deal, but looking at the way he's trying to write it, looks like he's just using it to display the first 20, but leaves room for other values (i.e. 3, 10, 50, 300..)

 

[Doctor Q]

Don't laugh so hard, janey. I had a problem on an exam in a programming class, to write a program that would output the English for a given dollar amount, from $0.01 to $99.99, and one student turned in something like this:

if ( amount == 0.01 ) printf("One cent\n") ;
else if ( amount == 0.02 ) printf("Two cents\n") ;
...
else if ( amount == 99.99 ) printf("Ninety nine dollars and ninety nine cents\n") ;

as if a compiler would fill in the "..." part for him or the professor would accept that as his program. (The professor did not.)

My answer to that exam question was a little more elegant than that. Although I didn't get a chance to make sure mine was correct, and the other student's program certainly would have been correct, once he ever finished it.

 

[janey]

That is SOOOOOOOOOOO wtf worthy..
http://www.thedailywtf.com/

I actually did something like that for a class:
http://applegoddess.livejournal.com/37254.html

 

[gekko513]

and here's the code i have so far: (thanks for the /code tip)
this version simply outputs a whole bunch of -1, but i thought id give you an update. Thanks!

Here's an example of what the others ment by pretending to execute the code. I assume that x starts out being set to 3 in my example. See what happens:

 

[ChrisBrightwell]

Here's the non-recursive algorithm I found in one of my old homework folders:

  private static long fib(int x)
  {
    if(x == 0 || x == 1)
      return x;

    else
    {
      long back1 = 1;
      long back2 = 0;
      long result = 0;

      for(int i=0; i<x-1; i++)
      {
        long sum = back1 + back2;
        back2 = back1;
        back1 = sum;
        result = sum; 
      }

      return result; 
    }
  }

You can eliminate one of the variables in the else{}, but I didn't care that much back then, nor do I care to fool with it right now.

You get a rollover error at x==93. If you're using an int for x, you'll get a rollover error at x==47. There's some error checking to be done (check for non-negative integers, esp.), but you get the idea.

Also, for the record, the recursive algorithm becomes obnoxious at x==35 here on my Powerbook. I suspect my workstation at work (dual 3.5GHz Xeon w/ HT, 4GB RAM) wouldn't flinch until 40 or 45. I'll test it tomorrow.

We use a table lookup for this in the app I develop at work (as well as for our factorial "calculations"), since the set of answers is so small.

 

[ChrisBrightwell]

Also, for the record, the recursive algorithm becomes obnoxious at x==35 here on my Powerbook. I suspect my workstation at work (dual 3.5GHz Xeon w/ HT, 4GB RAM) wouldn't flinch until 40 or 45. I'll test it tomorrow.

Haha OK ... It hit a similar "lag" at x==40.

To help n00bs reading this thread (and n00bs that will eventually read this thread), I did a bit of testing on the recursive vs non-recursive methods.

Here's the code I (tweaked and then) used to test:

import java.util.Date;

public class Fibonacci
{
  public static void main(String[] args)
  {

    Date start_loop = new Date();

    for(int x=0; x<50; x++)
    {
      Date start_fib = new Date();
      long value = fib(x);
      Date finish_fib = new Date();

      long time_for_fib = finish_fib.getTime() - start_fib.getTime();

      System.out.println("Input: " + x + ", Output: " + value + " (" + time_for_fib + " msec)");
    }

    Date finish_loop = new Date();

    long total_elapsed = finish_loop.getTime() - start_loop.getTime();
    System.out.println("total elapsed msec: " + total_elapsed);
  }

  private static long fib(int x)
  {
    if (x == 0 || x == 1)
      return x; 

    else 
      return fib(x-1) + fib(x-2);
  }
}

The machine here at work produced the following output:

% version
Microsoft Windows XP [Version 5.1.2600]

% java -version
java version "1.5.0_06"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_06-b05)
Java HotSpot(TM) Client VM (build 1.5.0_06-b05, mixed mode)

% javac Fibonacci.java

% java -cp . Fibonacci
Input: 0, Output: 0 (0 msec)
Input: 1, Output: 1 (0 msec)
Input: 2, Output: 1 (0 msec)
Input: 3, Output: 2 (0 msec)
Input: 4, Output: 3 (0 msec)
Input: 5, Output: 5 (0 msec)
Input: 6, Output: 8 (0 msec)
Input: 7, Output: 13 (0 msec)
Input: 8, Output: 21 (0 msec)
Input: 9, Output: 34 (0 msec)
Input: 10, Output: 55 (0 msec)
Input: 11, Output: 89 (0 msec)
Input: 12, Output: 144 (0 msec)
Input: 13, Output: 233 (0 msec)
Input: 14, Output: 377 (0 msec)
Input: 15, Output: 610 (0 msec)
Input: 16, Output: 987 (0 msec)
Input: 17, Output: 1597 (0 msec)
Input: 18, Output: 2584 (0 msec)
Input: 19, Output: 4181 (0 msec)
Input: 20, Output: 6765 (0 msec)
Input: 21, Output: 10946 (0 msec)
Input: 22, Output: 17711 (0 msec)
Input: 23, Output: 28657 (0 msec)
Input: 24, Output: 46368 (0 msec)
Input: 25, Output: 75025 (0 msec)
Input: 26, Output: 121393 (15 msec)
Input: 27, Output: 196418 (0 msec)
Input: 28, Output: 317811 (0 msec)
Input: 29, Output: 514229 (16 msec)
Input: 30, Output: 832040 (0 msec)
Input: 31, Output: 1346269 (31 msec)
Input: 32, Output: 2178309 (32 msec)
Input: 33, Output: 3524578 (46 msec)
Input: 34, Output: 5702887 (79 msec)
Input: 35, Output: 9227465 (140 msec)
Input: 36, Output: 14930352 (219 msec)
Input: 37, Output: 24157817 (344 msec)
Input: 38, Output: 39088169 (578 msec)
Input: 39, Output: 63245986 (922 msec)
Input: 40, Output: 102334155 (1500 msec)
Input: 41, Output: 165580141 (2422 msec)
Input: 42, Output: 267914296 (3922 msec)
Input: 43, Output: 433494437 (6345 msec)
Input: 44, Output: 701408733 (10267 msec)
Input: 45, Output: 1134903170 (16673 msec)
Input: 46, Output: 1836311903 (27081 msec)
Input: 47, Output: 2971215073 (43722 msec)
Input: 48, Output: 4807526976 (70363 msec)
Input: 49, Output: 7778742049 (114147 msec)
total elapsed msec: 298880

... that's 114 seconds for fib(49)!

Swap out the recursive function for the non-recursive function, and your code will look like this:

import java.util.Date;

public class Fibonacci
{
  public static void main(String[] args)
  {

    Date start_loop = new Date();

    for(int x=0; x<50; x++)
    {
      Date start_fib = new Date();
      long value = fib(x);
      Date finish_fib = new Date();

      long time_for_fib = finish_fib.getTime() - start_fib.getTime();

      System.out.println("Input: " + x + ", Output: " + value + " (" + time_for_fib + " msec)");
    }

    Date finish_loop = new Date();

    long total_elapsed = finish_loop.getTime() - start_loop.getTime();
    System.out.println("total elapsed msec: " + total_elapsed);
  }

  private static long fib(int x)
  {
    if(x == 0 || x == 1)
      return x;

    else
    {
      long back1 = 1;
      long back2 = 0;
      long result = 0;

      for(int i=0; i<x-1; i++)
      {
        long sum = back1 + back2;
        back2 = back1;
        back1 = sum;
        result = sum; 
      }

      return result; 
    }
  }
}

And my workstation here will kick out something like this:

% version
Microsoft Windows XP [Version 5.1.2600]

% java -version
java version "1.5.0_06"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_06-b05)
Java HotSpot(TM) Client VM (build 1.5.0_06-b05, mixed mode)

% javac Fibonacci.java

% java -cp . Fibonacci
Input: 0, Output: 0 (0 msec)
Input: 1, Output: 1 (0 msec)
Input: 2, Output: 1 (0 msec)
Input: 3, Output: 2 (0 msec)
Input: 4, Output: 3 (0 msec)
Input: 5, Output: 5 (0 msec)
Input: 6, Output: 8 (0 msec)
Input: 7, Output: 13 (0 msec)
Input: 8, Output: 21 (0 msec)
Input: 9, Output: 34 (0 msec)
Input: 10, Output: 55 (0 msec)
Input: 11, Output: 89 (0 msec)
Input: 12, Output: 144 (0 msec)
Input: 13, Output: 233 (0 msec)
Input: 14, Output: 377 (0 msec)
Input: 15, Output: 610 (0 msec)
Input: 16, Output: 987 (0 msec)
Input: 17, Output: 1597 (0 msec)
Input: 18, Output: 2584 (0 msec)
Input: 19, Output: 4181 (0 msec)
Input: 20, Output: 6765 (0 msec)
Input: 21, Output: 10946 (0 msec)
Input: 22, Output: 17711 (0 msec)
Input: 23, Output: 28657 (0 msec)
Input: 24, Output: 46368 (0 msec)
Input: 25, Output: 75025 (0 msec)
Input: 26, Output: 121393 (0 msec)
Input: 27, Output: 196418 (0 msec)
Input: 28, Output: 317811 (0 msec)
Input: 29, Output: 514229 (0 msec)
Input: 30, Output: 832040 (0 msec)
Input: 31, Output: 1346269 (0 msec)
Input: 32, Output: 2178309 (0 msec)
Input: 33, Output: 3524578 (0 msec)
Input: 34, Output: 5702887 (0 msec)
Input: 35, Output: 9227465 (0 msec)
Input: 36, Output: 14930352 (0 msec)
Input: 37, Output: 24157817 (0 msec)
Input: 38, Output: 39088169 (0 msec)
Input: 39, Output: 63245986 (0 msec)
Input: 40, Output: 102334155 (0 msec)
Input: 41, Output: 165580141 (0 msec)
Input: 42, Output: 267914296 (0 msec)
Input: 43, Output: 433494437 (0 msec)
Input: 44, Output: 701408733 (0 msec)
Input: 45, Output: 1134903170 (0 msec)
Input: 46, Output: 1836311903 (0 msec)
Input: 47, Output: 2971215073 (0 msec)
Input: 48, Output: 4807526976 (0 msec)
Input: 49, Output: 7778742049 (0 msec)
total elapsed msec: 172

The "total time elapsed" values will be skewed a bit, since I'm doing time calcs in the loop, but you can fix that pretty easily. I'm partial to the elegance of the recursive solution, but I understand its pitfalls. Like I said, we use a table lookup here at work.

 

[savar]

hey all
well i was trying to write some code that would output the first 20 fibonacci numbers, but im having some trouble when i impliment it. whenever i try to run the program (java fibonacci 20) it gives me this error:

Did you get all of your problems sorted out, Phiber?

This thread got way off-topic

 

[phiber optik]

wow this turned into a long thread...
i just got back from school and i got a chance to read all this. I'm pretty sure ill get all my problems sorted out with all this code. if not, you'll definetly hear about it!
oh and to give a feeling of satisfaction to therevolution, i learned a ton flipping through my java book and looking stuff up online, as well as writing my buggy code. So youre method of teaching worked out for me! (and youre not a meanyhead, just a good teacher.)
thanks again for all the help and code.