# Maximum PC

 It is currently Fri Sep 19, 2014 11:12 am

 All times are UTC - 8 hours

 Page 1 of 1 [ 7 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: c++ factorialPosted: Tue Oct 28, 2008 1:45 pm
 Klamath

Joined: Sat Jul 07, 2007 7:50 pm
Posts: 213
I need help with designing a factorial in c++. Here is my code.
Code:
#include <iostream>
using namespace std;
//prototype functions
int factorial(long int);
int powerFunction ( int, int);
int permutationWithoutRepetition(int,int);
int combinationsWithRepetition( int, int);
int combinationsNoRepetitions( int, int);
int main()

{
long int  input1,  input2;
cout<<"First number."<<endl;
cin>>input1;
cout<<"Second number."<<endl;
cin>>input2;
//Check input to ensure second number is larger than first
while (input1<=input2&&input1>0){
cout<<"The second number must be smaller than the first number. Please enter the \nsecond number."<<endl;
cin>>input2;}
cout<<"The number factorial is "<<factorial(input1)<<endl;
//function call for permutations without repetition
int permNoReps=permutationWithoutRepetition(input1,input2);
//fucntion call for combination with repetition
int combWithRep=combinationsWithRepetition(input1,input2);
//function call for combinations without repetition
int combNoRep=combinationsNoRepetitions(input1,input2);
cout<<"The permutations withy repetitions are "<<powerFunction(input1,input2)<<endl;
cout<<"The permutations without repititions are "<<permNoReps<<endl;
cout<<"The combinations with repetition are "<<combWithRep<<endl;
cout<<"The combinations without repetition are "<<combNoRep;*/
system ("pause");
return 0;
}
int factorial (long int x){
int total,z;
total=1;
for(z=1;z<=x;z++)
total=total*z;
int powerFunction( int x, int y){
int z=1;
for (int a=1;a<=y;a++)
{z=z*x;}
return z;}
int permutationWithoutRepetition( int x, int y){
int tempFactorial=x-y;
int permNoReps=factorial(x)/factorial(tempFactorial);

return permNoReps;
}
int combinationsWithRepetition( int x, int y){
int combWithReps=factorial(x+y-1)/(factorial(y)*factorial(x-1));
return combWithReps;
}
int combinationsNoRepetitions( int x, int y){
int combNoReps=factorial(x)/(factorial(y)*factorial(x-y));
return combNoReps;
}

Now, my problem is that in the function named factorial when I try to input a number over 15 I start getting whacky output until I finally start getting 0. What is the deal?

Top

 Post subject: Posted: Tue Oct 28, 2008 2:31 pm
 Team Member Top 500

Joined: Mon Jan 08, 2007 1:41 pm
Posts: 2033
I'm confused as to what you mean by a "factorial" program? Are you talking factorials such as "15!" ? If you are I don't see how your program has anything to do with the definition of factorial that I'm aware of.

I'm no expert in c++, but looking at your code in the "int factorial()" function, you're beginning with one, multiplying it by 2, then by 3, then by 4... all the way up to and including int x.

You can clearly see, doing it out by hand, that passing 15 to "factorial" returns something like 1.31 x 10^12, which I'm pretty sure is outside the parameters of an int. I tried changing the type to double, and that seemed to fix it (aside from all the compiler warnings about ints to doubles).

Top

 Post subject: Posted: Tue Oct 28, 2008 3:09 pm
 Klamath

Joined: Sat Jul 07, 2007 7:50 pm
Posts: 213
My apologies I wasn't clear. I need to do these calculations
n!/(n-r)! and

n!/r!(n-r)! and

(n+r-1)!/r!(n-1)! and

n^r

The factorial is just a function that I call in the other functions to do calcuations with.

Top

 Post subject: Posted: Tue Oct 28, 2008 4:02 pm
 Team Member Top 500

Joined: Mon Jan 08, 2007 1:41 pm
Posts: 2033
Ah, I see now.

But, like I said before, the most apparent problem is the need for larger variables that can hold all that data.

To demonstrate:

Here, I did a simple find and replace on all your ints and made them unsigned longs. Same as a long, only twice as big because it can only hold positive numbers. AFAIK, this is the largest int data type possible.
Code:
#include <iostream>
using namespace std;
//prototype functions
unsigned long factorial(unsigned long);
unsigned long powerFunction ( unsigned long, unsigned long);
unsigned long permutationWithoutRepetition(unsigned long,unsigned long);
unsigned long combinationsWithRepetition( unsigned long, unsigned long);
unsigned long combinationsNoRepetitions( unsigned long, unsigned long);

int main()

{
unsigned long  input1,  input2;
cout<<"First number."<<endl;
cin>>input1;
cout<<"Second number."<<endl;
cin>>input2;
//Check input to ensure second number is larger than first
while (input1<=input2&&input1>0){
cout<<"The second number must be smaller than the first number. Please enter the \nsecond number."<<endl;
cin>>input2;}
cout<<"The number factorial is "<<factorial(input1)<<endl;
//function call for permutations without repetition
unsigned long permNoReps=permutationWithoutRepetition(input1,input2);
//fucntion call for combination with repetition
unsigned long combWithRep=combinationsWithRepetition(input1,input2);
//function call for combinations without repetition
unsigned long combNoRep=combinationsNoRepetitions(input1,input2);
cout<<"The permutations withy repetitions are "<<powerFunction(input1,input2)<<endl;
cout<<"The permutations without repititions are "<<permNoReps<<endl;
cout<<"The combinations with repetition are "<<combWithRep<<endl;
cout<<"The combinations without repetition are "<<combNoRep;
system ("pause");
return 0;
}
unsigned long factorial ( unsigned long x){
unsigned long total,z;
total=1;
for(z=1;z<=x;z++)
total=total*z;
unsigned long powerFunction( unsigned long x, unsigned long y){
unsigned long z=1;
for (unsigned long a=1;a<=y;a++)
{z=z*x;}
return z;}
unsigned long permutationWithoutRepetition( unsigned long x, unsigned long y){
unsigned long tempFactorial=x-y;
unsigned long permNoReps=factorial(x)/factorial(tempFactorial);

return permNoReps;
}
unsigned long combinationsWithRepetition( unsigned long x, unsigned long y){
unsigned long combWithReps=factorial(x+y-1)/(factorial(y)*factorial(x-1));
return combWithReps;
}
unsigned long combinationsNoRepetitions( unsigned long x, unsigned long y){
unsigned long combNoReps=factorial(x)/(factorial(y)*factorial(x-y));
return combNoReps;
}

Now, what you have to realize is that your given calculations are quite possible to do with larger numbers, but it's the factorial function that is giving you the problems. 15 factorial has something like 12 decimal places. 16 factorial is 16 times that. You see how this increases almost exponentially.

A way to make this work is to simplify before you take the factorial.

For example, if you have:

6!/3!

and expand it:

(6*5*4*3*2*1) / (3*2*1)

You can obviously see that 6!/3! is simply equal to (6*5*4)

To put this in code, it could be as simple as:

Code:
int input1=6;
int input2=3;
int output=1;

//Find 6! / 3!

for (int i=input2+1; i<=input1; i++)
output*=i;

// here are the steps the output variable goes through with the given inputs:
// initialized to one
//multiplied by 4 (input2+1)
//multiplied by 5
//multiplied by 6

//You can see, this process is equivalent to what we said 6!/3! is: (4*5*6)

Haven't tested that myself, but it looks right.

So I suggest you change your factorial function to take a numerator (call it input1) and a denominator (call that input2) as arguments, and you won't have to be dealing with huge #'s.

Top

 Post subject: Posted: Sun Nov 30, 2008 5:42 pm
 Little Foot

Joined: Mon Jul 28, 2008 1:39 pm
Posts: 123
Try not using doubles (factorials don't need decimal places) and use unsigned long instead. They give you extra precision on the other side of the decimal point, which is what you need.

EDIT: Crap, didn't notice you already covered that. Oh well.

If you need a really big data type, you could write a class like Java's BigInteger class.

Top

 Post subject: Posted: Sun Nov 30, 2008 6:07 pm
 Team Member Top 500

Joined: Mon Jan 08, 2007 1:41 pm
Posts: 2033
Quertior wrote:
Try not using doubles (factorials don't need decimal places) and use unsigned long instead. They give you extra precision on the other side of the decimal point, which is what you need.

EDIT: Crap, didn't notice you already covered that. Oh well.

If you need a really big data type, you could write a class like Java's BigInteger class.

No worries, haha.

He must have figured something out, because, obviously, he never posted back.

In his case, I think that finding ways to hold huge numbers (i.e. unsigned longs) would have solved the problem, but even that fails at some point.

The ideal solution, as I pointed out, is to simplify before calculations start taking place. Since almost everything he wanted to do involved division and multiplication, simplifying was easy. For example, 15! / 14! is simply 15. There's no need to find 15 factorial, then divide it by 14 factorial. It's obvious how much better this approach is given something like 1,000,001! / 1,000,000!

Top

 Post subject: Posted: Sun Nov 30, 2008 6:20 pm
 Little Foot

Joined: Mon Jul 28, 2008 1:39 pm
Posts: 123
Even unsigned longs have their (albeit extremely high) limits. Java's BigInteger class is very useful for something like 10000! or other large calculations.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 7 posts ]

 All times are UTC - 8 hours

#### Who is online

Users browsing this forum: No registered users and 4 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Maximum FAQs    Forum Rules, Posting Guidelines & Announcements    The Good, The Bad & The Banned    FAQs Help/Do It Yourself    PC Building Lab    The Help Desk    PC Modding    Education & Certification Hardware    Nuts & Bolts    Portable Talk    Appraisals, Deals & Bargains (oh my!) OS/Software/Programming    Windows Parlor    Alt.OS.Abode    Games Arena    Programmers' Paradise Networking/Internet    Internet Truckstop    Network Nook In/Out    Magazine and Book Feedback    Forum & Website Feedback    Dog Pound Team Maximum PC Folding at Home    Team Maximum PC - Folding at Home - FIND CURES TO DISEASES    Team MPC - Folding Gauntlets
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group