How to make my java function efficient (stack overflow)

Kelv

Limp Gawd
Joined
May 10, 2008
Messages
385
Heres my function, its breaking on line 30:
return this.factorhelper(n, (i + 1), acc);

I'm a unexperienced java programmer, I have some ideas such as getting rid of the accumulator in factorhelper and just use boolean and not but thought some of you might have much better ones.

Update #1: I made the changes I was thinking of.

Update #2: Would translating it into c++ be more effective? I also heard there are ways to increase the memory that java will use.

Update # 3: Btw I would like to have this program for several hours at least. Right now it lasts less then a second lol. Maybe I should just try writing it in c++ instead, I won't be able to right it off the top of my head but I'll just have to read up on it.

Update #4: I think I realized what I need to do, replace my current factor method with a PrimeOmega method. Hmm.. Anyone know much about it?


This is one weird result that I get back.
Code:
Current: 8522, Difference is: -17
java.lang.reflect.InvocationTargetExceptionCurrent: 8523, Difference is: -18
Current: 8524, Difference is: -17

Then the program makes it up to:
Current: 8784, Difference is: -25

and then throws this error for 50+ times:

Code:
at OddGreaterEven.factorhelper(OddGreaterEven.java:32)


New Code
Code:
class OddGreaterEven{
	OddGreaterEven(){}

	// recurses until the difference is equal to 1 (number of evens is greater than the number of odds)
	void f (int current, int difference){
		System.out.println("Current: " + (current + 1) + ", Difference is: " + difference);
		if (difference == 1){
			System.out.println("This is the winner! " + (current + 1));
		}
		else if (this.isOdd(current)){
			this.f((current + 1), difference - 1);
		}
		else this.f((current + 1), difference + 1);
	}

	// is the number of prime factors for this number odd?
	boolean isOdd(int current){
		return this.factorhelper(current, 2);
	}

	// returns the number of prime factors for the given integer
	boolean factorhelper(int n, int i){
		if ((n == 0) || (n == 1)){
			return false;
		}
		else if ((i <= n) && ((n % i) == 0)){
			return !this.factorhelper((n / i), i);
		}
		else if ((i <= n) && ((n % i) > 0)){
			return this.factorhelper(n, (i + 1));
		}
		else return false;
	}
}
 
Last edited:

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
You seem to be running off in all directions. A stack overflow isn't a sign of inefficiency, it's a bug. Your recursion never terminates. If you wrote this code in C++, it would fail in the same way.
 

Kelv

Limp Gawd
Joined
May 10, 2008
Messages
385
It doesn't terminate because the stack overflows, its not running into an infinite loop. Theres one way I can keep on running it, which is to rerun the program on the last value printed.

Of course there is the theory that the number of evens will never be greater then the number of odds.

What can I do about the memory management? I only want to store two numbers, the current number and the difference between number of odds and number of evens.
 

Wiseguy2001

2[H]4U
Joined
Nov 28, 2001
Messages
3,466
I've only ran the code in my head, but these lines don't gel with me.
Code:
else if (this.isOdd(current)){
			this.f((current + 1), difference - 1);
		}
		else this.f((current + 1), difference + 1);

So if difference != 1 these two statements are going to counteract one-another, adding 1 to evens and subtracting 1 to odds. This isn't going to get anywhere, just deeper into your recursion and causing a stack overflow.

Also when you get this figured out I recommend you look into multi-threading, this will greatly speed it up (on multi-core CPU's), this type of program is crying out to be threaded.
 

mikeblas

[H]ard|DCer of the Month - May 2006
Joined
Jun 26, 2004
Messages
12,776
It doesn't terminate because the stack overflows, its not running into an infinite loop.
Your analysis is incorrect. You need to do more debugging.

What can I do about the memory management? I only want to store two numbers, the current number and the difference between number of odds and number of evens.
Why?
 

Crash250f

Gawd
Joined
Nov 9, 2007
Messages
640
Stack overflows terminate in an exception being thrown in java. You'd see it in the console and it would look something like:

Code:
Exception in thread "main" java.lang.StackOverflowError
	at ....

If you're not getting that, your stack is fine. :)
 
Top