Help using factorial function...

I'm doing a little bit of homework, and one of my problems is as follows:

Write a function that will return N! when N is passed to it.
Your program should ask for N and K. The probability of K numbers being selected from N numbers is:

Code:

                     N!
Probability =    --------
                 K!(N-K)!

Basically, it's a lottery program, where the user enters the number of chances he's purchases, and enters the number of chances total. The program computes the probability. I know that my factorial function that I created is not the problem, it has to be somewhere in the code itself. Any help is appreciated, here's the code:

Code:

#include <iostream>
using namespace std;

int fac(int n);

int main()
{
	int	fact1, fact2, picks, total, fact3, subtraction;
	float	output;

	cout << "Enter the amount of chances you are choosing..." << '\n' << endl;
	cin >> picks;
	cout << '\n' << "Now, enter the total number of choices..." << '\n' << endl;
	cin >> total;

	subtraction = total - picks;

	output = fac(total) / (fac(total * fac(subtraction)));

	cout << '\n' << "Your chances are 1 in " << output << "." << endl;

	return (0);
}

int fac(int n)
{
	int	i=0, fact=1;
	for(i=1;i<=n;++i)
		{
			fact=fact*i;
		}
		return(fact);
}

Thanks!

How does it not work? Incidentally, note that 13! is too large to fit into a 32-bit int.

What is the problem? Is it not compiling? Is it giving you incorrect output? If so, what input do you give it? What output do you expect? What output do you get?

I do see an error. Make sure your formula matches what you do in the code.

I know that the coding seems to be correct, it's not giving me the output that I expected. For example, when I input 5 for picks, and 10 for total, it should give me 1 in 242. However, after I type in the inputs, it freezes for a moment, then an error message comes up, and the program terminates.

>> output = fac(total) / (fac(total * fac(subtraction)));
That is the formula that is wrong. Convert it to the same format as the probability forumla you posted, and you will see that they are different.

Make them the same and you'll probably get a better result.

To convert it, replace total with N, replace fac(...) with (...)!, replace (subtraction) with (total - picks) and then replace total and picks in there with N and K.

If you want to be able to calculate "n choose k" for n or k > 13, using integer arithmatics, you could let P_num be a list of the prime factors of n!, and P_den be a list of the prime factors of (n-k)!k!.

Let P_res be the subtraction P_num - P_den elementwise and multiply the remaining factors left in P_res to make the final number. You'll be able to use a broader range of numbers and it's a nice exercise

Example:
8 choose 5

Numerator:
8! = 40320 = 2^7 * 3^2 * 5^1 * 7^1
P_num[2] = 7
P_num[3] = 2
P_num[5] = 1
P_num[7] = 1

Denominator:
(8-5)!5! = 720 = 2^4 * 3^2 * 5^1
P_den[2] = 4
P_den[3] = 2
P_den[5] = 1

P_res[2] = P_num[2] - P_den[2] = 7-4 = 3
P_res[3] = ... = 0
P_res[5] = ... = 0
P_res[7] = ... = 1

So the result is 2^3 * 7 = 56

the only this is, my prof wants us to do this by using functions that we write....

i still can't get this to return the results that i want, does anyone see anything wrong that i've done, i've fixed the equation, so i don't believe that's the problem anymore.

Code:

//William Orazi, CSE 121, Probability

#include <iostream>
using namespace std;

float fac(float n);

int main()
{
	float	picks, total, subtraction;
	float	output;

	cout << "Enter the amount of chances you are choosing..." << '\n' << endl;
	cin >> picks;
	cout << '\n' << "Now, enter the total number of choices..." << '\n' << endl;
	cin >> total;

	subtraction = total - picks;

	output = fac(total) / (fac(picks) * fac(subtraction));

	cout << '\n' << "Your chances are 1 in " << output << "." << endl;

	return (0);
}

float fac(float n)
{
	int		i=0;
	float	fact=1;
	for(i=1;i<=n;++i)
		{
			fact=fact*i;
		}
		return(fact);
}

i originally had the input as int, but i changed it to float so that larger values could be entered

If you're going to change to floating point, use double instead of float. double is the default floating point type anyway, and it also provides greater precision than float.

>> i still can't get this to return the results that i want
You forgot to give us the input, the expected output, and the actual output you're getting.

Also, are you sure that 10 choose 5 isn't 1/252 rather than 1/242?

Bear in mind both what Daved says about the limited precision in float (only about 6-7 digits precision), and the fact that float doesn't have a dramatically greater range than double, so if you have fairly large numbers as input, you may find that the range is still not good enough with float - use double.

--
Mats

is there a type that will allow for larger numbers? for example 20!, which is in the billions?

oh and it was 1/252 that was just a typo

Most compilers have a way to support 64-bit integers, but not all do it the same way. "double" will be a much greater range, and with about 16 digits precision, so you should get close to the right number that way.

If you are using gcc, long long will make a 64-bit number. In MS compilers, __int64 is a 64-bit number.

--
Mats

yea i'm using visual studios, so double gives better precision than float, because our prof always told us it was the other way around, float dedicates more memory than double and therefore allows for more integers ... that's what he told us anyway

Either you misunderstood him or he misspoke, I doubt he would really think that, it's exactly the other way around.

Are you still having problems? Your code seems to work when you use double, even for numbers as high as 20.

Either you misunderstood the professor, or the professor has been sipping too many bevies/smoked too much of that funny stuff.

double is a 64-bit floating point, with 52 bits of mantissa, giving about 16 digits. float is a 32-bit floating point, with 24 bits mantissa, giving about 7 digits. If you want more than that precision, there's several compilers that support "extended precision" which is, on x86, an 80-bit number with 64 bits mantissa (approx 21 digits). This is usually called "long double" in the compiler [VS supports this form, as does gcc].

--
Mats