Thread: Help using factorial function...

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    48

    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!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    How does it not work? Incidentally, note that 13! is too large to fit into a 32-bit int.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  4. #4
    Registered User
    Join Date
    Sep 2007
    Posts
    48
    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.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> 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.

  6. #6
    Registered User
    Join Date
    Jul 2005
    Posts
    14
    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

  7. #7
    Registered User
    Join Date
    Sep 2007
    Posts
    48
    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

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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?
    Last edited by Daved; 11-09-2007 at 05:17 PM.

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Sep 2007
    Posts
    48
    is there a type that will allow for larger numbers? for example 20!, which is in the billions?

  11. #11
    Registered User
    Join Date
    Sep 2007
    Posts
    48
    oh and it was 1/252 that was just a typo

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Registered User
    Join Date
    Sep 2007
    Posts
    48
    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

  14. #14
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Undefined Reference Compiling Error
    By AlakaAlaki in forum C++ Programming
    Replies: 1
    Last Post: 06-27-2008, 11:45 AM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. Message class ** Need help befor 12am tonight**
    By TransformedBG in forum C++ Programming
    Replies: 1
    Last Post: 11-29-2006, 11:03 PM
  4. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM
  5. Question..
    By pode in forum Windows Programming
    Replies: 12
    Last Post: 12-19-2004, 07:05 PM