Quantcast

Maximum PC

It is currently Wed Aug 27, 2014 9:21 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 7 posts ] 
Author Message
 Post subject: c++ factorial
PostPosted: Tue Oct 28, 2008 1:45 pm 
Klamath
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;
    return total;}
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
  Profile  
 
 Post subject:
PostPosted: Tue Oct 28, 2008 2:31 pm 
Team Member Top 500
Team Member Top 500
User avatar

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
  Profile  
 
 Post subject:
PostPosted: Tue Oct 28, 2008 3:09 pm 
Klamath
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
  Profile  
 
 Post subject:
PostPosted: Tue Oct 28, 2008 4:02 pm 
Team Member Top 500
Team Member Top 500
User avatar

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;
    return total;}
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
  Profile  
 
 Post subject:
PostPosted: Sun Nov 30, 2008 5:42 pm 
Little Foot
Little Foot
User avatar

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. :wink:

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


Top
  Profile  
 
 Post subject:
PostPosted: Sun Nov 30, 2008 6:07 pm 
Team Member Top 500
Team Member Top 500
User avatar

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. :wink:

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
  Profile  
 
 Post subject:
PostPosted: Sun Nov 30, 2008 6:20 pm 
Little Foot
Little Foot
User avatar

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
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 2 guests


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

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group