Quick problem

[Panphobia]

Umm I do not think this is too big of a problem but my program has an error where it divides by 0. I have set in things that should make this not the case, what could be the problem now?

code:

public static void main(String[] args) {         int c = 0;         for (int i = 1; i < 101; i++) {             for (int x = 1; x <= i; x++) {                 if (combo(i, x) > 1000000) {                     c += 1;                 }             }         }         System.out.println(c);     }     public static int combo(int n, int r) {         return (fac(n) / (fac(r) * fac(n-r)));     }     public static int fac(int n) {         if (n == 1 || n == 0) {             return 1;         }         return n * fac(n - 1);     }

[DemonWasp]

This problem is pretty subtle, and it took me a moment too. The problem is that int isn't large enough to hold values like 40!, which is approximately 8 x 10^47. Even if you use long, you can't handle values above 66! ~= 5.4 x 10^92.

There are two ways to handle this problem. First, you could use Java's BigInteger class, which can handle arbitrary-value integers, including 100! x 100!.

Second, you could take a good long look at the formula for combinations (what you've implemented in combo()) and try to come up with a version that doesn't generate numbers that are quite so huge. Even then, 100 choose 50 is more than can be stored in the long data type. You could use double, which can store substantially larger numbers, if you're willing to sacrifice some accuracy, or you can use BigInteger.

[Panphobia]

Thank you man, all I did was cast the return statement of the combo function to (int) made fac return a double, worked fine

[Tony]

now, consider that you've just calculated the value of 10! and your for-loop advances to 11. To calculate fac(11), you compute 11 * fac(10)... which you already knew the answer for just moments before! but now have to compute fac(10) (again) and fac(9) (also again) and fac(8)...

[Panphobia]

yea i understand what you are trying to say tony, but efficiency was not my aim lol, i was just solving some project euler

[Insectoid]

A lot of project euler is about efficiency. Many of the problems are designed to be impossible or take ridiculously long to execute with naive brute-force algorithms.

[mirhagk]

I'm doing euler as well, trying to do it in haskell. Essentially every solution can be like 2 lines of code, but it's RIDICULOUSLY hard to optimize it. I can solve the first few problems, but later ones quickly become impossible.

[bl0ckeduser]

Is this the ProjectEuler thing where you have to compute big factorials ?

I can strongly recommend writing custom code that does it using "pencil-and-paper" methods.
It's fun and there are skills to learn.

[md]

Panphobia @ 2012-11-14, 12:52 am wrote:

Thank you man, all I did was cast the return statement of the combo function to (int) made fac return a double, worked fine

That doesn't solve your issue, it just hides it so that you don't notice that your answers are wrong.

[Panphobia]

md @ Wed Nov 14, 2012 11:12 pm wrote:

Panphobia @ 2012-11-14, 12:52 am wrote:

Thank you man, all I did was cast the return statement of the combo function to (int) made fac return a double, worked fine

That doesn't solve your issue, it just hides it so that you don't notice that your answers are wrong.

I know exactly why it is wrong, but it solves the question, which non the less is the goal, I fitted the code to the question, I did not need to make it horribly efficient.

[Insectoid]

That's the wrong attitude to have in computer science.

[Tony]

Insectoid @ Thu Nov 15, 2012 12:20 am wrote:

That's the wrong attitude to have in computer science.

well... not necessarily. There's a trade-off between ideal solution and fast (to develop) solution. If one throws just enough code until something works, then you are correct ? that is bad news. But if one understands exactly what they are trading off, then it's a fair trade.

[Panphobia]

What i was getting at, is the question does not ask for efficiency, so I was looking at it from the perspective, "get it done as fast as possible", not spend more time to make it more efficient