Helllo Guy's
I was thinking of this problem for the past one month. We have to generate the factoroial of say 100 using c and usual integer data type how can this be achived
thanx in advance
Printable View
Helllo Guy's
I was thinking of this problem for the past one month. We have to generate the factoroial of say 100 using c and usual integer data type how can this be achived
thanx in advance
int main(){
int x=0;
int y=100;
int total;
while(x<=y){
total *= x;
x++;
}
printf("The value is %i",total);
return 0;
}
Might work. But I make no guarantees. Might be hard to calculate 100! with a 32 bit integer though. It's like 9.3*10^157 or something like that.
You could also use a recursive algorithm
int factorial(int x){
static int total=0;
total*=x;
x--;
factorial(x);
return 0;
}
But I suck at writing recursive algorithms.
And please stop asking us to do your homework for you. We have better things to do.
If it's really like 9.3*10^157 or something like that, then it WON'T work. The maximum unsigned 32 bit integer is 4.3 x 10^9. The maximum unsigned 64 bit integer is 1.8 x 10^19. You will need a (dynamically allocated) string to store the result.Quote:
Might work. But I make no guarantees. Might be hard to calculate 100! with a 32 bit integer though. It's like 9.3*10^157 or something like that.
I remember my friend at univ wrote a program to calculate 200! using string. But I forget how. Don't care actually. What's the purpose anyway, other than doing your homework...
Peace always,
<jdenny>
sorry guys but you've got your math messed up over there.
'total' will never go beyond zero if you use those routines.
vozhan, so what would you use?
vozhan, Shriek never said it would work for sure:
Actually, it might go over 0, depending on how overflows are taken into account the integer would wrap around and start counting from 0 again (or a negative number like -(2 ^ 31) if you're using signed integers). ;)Quote:
Originally posted here by Striek
Might work. But I make no guarantees. Might be hard to calculate 100! with a 32 bit integer though. It's like 9.3*10^157 or something like that.
No way! Recursion is defiently not the way to figure this type of program, you will run out of memory very quickly. If you really need help, PM me and ill show you but i am very busy at the moment because of finals so i wont have time for the next like week so i dont know if ill be much help...Quote:
You could also use a recursive algorithm
int factorial(int x){
static int total=0;
total*=x;
x--;
factorial(x);
return 0;
}
vozhan is correct. With that algorithm, total will never get past 0 because of the following:
If you look above, you will notice that 0 has been assigned to total to start, then total is timed by x. Because total is zero, it doesn't matter what x is:Quote:
static int total=0;
total*=x;
total x "new total"
0 1 0
0 2 0
0 3 0
If you set total to 1 to start with, it might be alright...but it should be much better to use something like a while or a for loop rather than writing a recursive algorithm, if only because you should make your code as readable as possible unless you are entering the obsfucated c code competition :P
ac
[edit]the columns are a bit messed up in the "table" above, but you get the idea[/edit]
[edit]and you couldn't use a string to solve the problem simply because Hunt_guy said that he was to use the integer data type. If he was allowed to use a string, why not just use a long?[/edit]
One way to go about the solution would be to note the maximum size of an integer. Every time you reach this maximum size, you add one to a counter and start your "total" integer again (well not again, from wherever you got to). When you have worked out the whole factorial, you simply use output it to the screen:
std::cout << (counter*MAX_INT_SIZE)+total << endl;
or use printf (I don't want to make a fool of myself attempting to write it using printf, I never got used to the %s, %d, etc...never know which one to use :P
Anyhow, that would be a simple way of doing it.
ac
[edit] I just realised that that would not be entirely correct in that it assumes that you would get exactly the max int value every time, but it is almost right :P [/edit]
Erm, maybe you better ignore my last post. I've thought about it and I don't think that my maths is anywhere near correct :(. Hrrm...
Must be too late at night.
ac
Yeah, arbitrary precision is very confusing. I've tried to make my own like that with huge string allocations (acturally char arrays) and compare numbers one by one. I don't know what happened to it, but I probably never completed it anyways.
And that recursive function looks really....recursive. I don't see any code to exit out of the loop, IE it will continue to call it self over and over until the program finally kills the heap/stack or something. I don't quite know what it is...
Also, even if it wasn't a static, it would still always be zero (if you managed to get an answer out of it since it loops forever). Why? Since there is no checking to see if X is less than or equal to 1. Without that it would multiply it by 0 when x = 0, and thus the answers would be cleared.
Well the only reason I can acturally comment on it is because I have my C book here with an example of a recursive function to calculate factorials... heh. Sadly I don't think I'm *allowed* to post the code up. Sorry.
The next best thing - Using Linked Lists of Integers to store the factorial of 1000... http://www.codeguru.com/algorithms/factorial.shtml I don't happen to think that the code there is easily understandable though...
Tim_axe, sorry to be pedantic, but if you look at his code, x would never be zero, that wasn't the issue. The fact is that it is pointless even having the x if you set total to 0 at the start because total will never increase, and that's even if you ignore that there is no way to exit the recursion.
Also, because total is a local variable and you are not sending it as an argument, total would have died at the beginning of each recursion in any case. A slightly more functional function, if still not very good would be:
Please note that even that code is completely useless :P I just felt like correcting the other code (too tired to check who it was that posted it, and I can't see just now anyway :P)Code:void genFactorial(int x, int t)
{
int total = t; // you probably wouldn't even need total now
total*=x;
if(x>1)
x--;
else
break;
genFactorial(x, total);
}
void main(void) // yes, I know it isn't totally correct
{
genFactorial(100,1);
}
ac
Oh god that makes me look sad.
[edit] Tim_axe, I'm sorry. I realise what you are saying now (couldn't really see it properly, my contact lenses are fscked atm). I left what I said in incase someone already had seen it so that you know I was apologising [/edit]
Don't worry about it gothic_type, I can see where I sort of rambled on in my post and just messed up what I was trying to point out.
I'll work off of your code since it has the basic framework and I want to save typing...
<WANDERS OFF>
*Opens up DevC++*
*Finds C Programming Book*
*Mumbles*
*Types*
*Clicks Compile*
*Mumbles*
*Types*
*Clicks Compile*
*Mumbles*
*Returns to Open Window*
</WANDERS OFF>
Okay, this following code compiles, and works fine for me. If not, please debug it yourself. :P Also, don't give it an integer bigger than 14. It will crash or mess up something (Integer Overflow). Same goes for letters, and decimal numbers. Integers only...
Enjoy. Also, it won't do your 100 or whatnot. Only up to 14... Check the link in my previous post to find code for bigger numbers. I haven't tried it myself...Code:#include <iostream>
#include <stdlib.h>
using namespace std;
int main(void);
unsigned int genFactorial(unsigned int x);
int main(void)
{
int fact=0;
cout<<"Blah. Give me an Integer or I'll crash: ";
cin>>fact;
cout<<"\nI think that is: "<<genFactorial(fact)<<endl;
cout<<"If that's wrong, it's 42!"<<endl;
system("PAUSE");
return 0;
}
unsigned int genFactorial(unsigned int x)
{
if(x>1)
{
x *= genFactorial(x-1);
return x;
}
else
{
return 1;
}
}
Tim_axe, nice prog; appears to work correctly (despite the fact that I attempted to get gcc to compile it to begin with which made it unhappy :()
Now all we need to do is edit the program so that it can do 100, but still using integers :P.
ac
BTW -- Tim_axe, I think we must be the only people sad enough to have kept on posting to this topic...I think everyone else bailed :P
well you guys are using recursion, which isnt going to be good when you are computing 100 because you will run out of space in RAM.
White_Eskimo, the only reason I (and I think Tim_axe as well) was using recursion was because Striek had suggested it. His code was really messed up, so I was trying to "fix" it while also attempting to point out the multiplying by zero error.
Anyhow. Since no-one else really suggested/posted another method, at least it's something. :P
ac
Well I guess we could continue it... Anyone else want to help out? :D
So we can scrap the recursion idea because the program would eventually run out of heap/stack or something on really big numbers... But as to how will we use integers to store numbers that are over 32bits long... We might have to borrow from the code @ http://www.codeguru.com/algorithms/factorial.shtml by somehow adopting use of linked lists of integers. Although the code there already uses it to compute factorials...
So, I guess it would be like this (insert really bad program outline here):
Use types in number, ie 60.
Allocate 59/60/61 integers (array), put numbers 60 to 1 in them. (we will somehow multiply them later on, which is what factorials do)
Then we can allocate some more integers, say 1000 to be safe for now, and set each element to 0. This will hold our output, with each integer holding a single digit. 1000 here would mean we can store a 1000 digit answer for a factorial. My guess is that is the factorial of 150 or so?
We then multiply the last two integers from the first array, ie with values 60 and 59.
Store this result, ie 3540, in a temporary integer. We then seperate it into thousands, hundreds, tens, and ones, etc., and put it into the answer in those respective places in the answer array.
This gets messy. We seperate the next integer into ones and tens, and then somehow multiply the answer array and this next integer, ie 58, and deal with carrying over numbers to keep a single digit to the answer. Move that into the answer, and repeat that process. The link does that somewhere, but with linked lists instead of arrays of integers.
This technique could work well up until getting the factorial of about 65537, since 65537 * 65536 is a number over 32bits, the largest we could hold in an unsigned integer / long value on a normal 32bit PC... (first multiplacation step)
It is sort of reinventing the wheel I guess since there is already code to do it. I could probably work on it when I'm not studying for finals this week. Hopefully we can figure this one out, lol. :)
Later,
-Tim_axe
Wow. I looked at that "algorithm"...I couldn't even have begun to think about coding that (mainly because I've never learned about linked lists and I don't know as much as I should about c++).
Man!
ac
I tried to come up with my own code and it is useless. I can't get it to carry numbers over right and multiply them together the way I need to. It ended up using only the first unsigned long in the array of about 1000 of them.
Anyways, I read through the comments of that tutorial, and came across this one. Man the person (Krishna Kumar Khatri) is good... Saves me from ripping out anymore of hair trying to get my own version to work. :p
http://www.codeguru.com/mfc/comments/50249.shtml
lol. That code's still too confusing for me to understand without reading it over a couple of times :P.
If you could somehow devise a way to multiply parts 1 to n in an array to output them without having to store them in a variable, then I've got a program that solves this problem. But I guess that was the whole problem in the first place :P
Anyhow. I'm just annoyed that I couldn't think up a solution myself :)
ac
First Message. :cool: Here is a part of my program. You can calculate 10000!, maybe more.
I am cutting code.
#define Max_Digit 20000 // May be changed by memory
#define Base 10 // 256 is confortable
struct GreatNumber{
public:
int digits[Max_Digit];
int decflag;
int positionflag;
}stemp,sptemp,temp2;
GreatNumber Mult(GreatNumber X, GreatNumber Y)
//Spider-Multiplication of numbers By:Slayerchange
{
int log1=0,log2=0,log3=0,log4=0,artik=0,deger=0;
log2=Y.positionflag+1;
log4=X.positionflag+1;
NullNumber(sptemp);
NullNumber(temp2);
for(log1=0;log1<=log2;log1++)
{
for(log3=0;log3<=log4;log3++)
{
deger=Y.digits[log1]*X.digits[log3]+artik;
if(sptemp.digits[log1+log3]+deger<Base){
sptemp.digits[log1+log3]+=deger;
artik=0;
deger=0;}
else{
deger+=sptemp.digits[log1+log3];
sptemp.digits[log1+log3]=deger%Base;
artik=(deger-deger%Base)/Base;
}
}
SetPosition(sptemp);
temp2=sum(temp2,sptemp);
NullNumber(sptemp);
}
return temp2;
}
//Some functions here irrevelent.You can delete them. Here is fakto.
void Fakto1000(void)
//1000!
{
GreatNumber A,B,C;
NullNumber(A);
NullNumber(B);
NullNumber(C);
A.digits[5]=1;
B.digits[0]=1;
C.digits[0]=1;
SetPosition(A);
SetPosition(B);
SetPosition(C);
do{
Inc(B,0,1);
C=Mult(C,B);
shownumber(B);
cout<<"\nFakto=";
shownumber(C);
}while(!Equal(A,B));
}
Ain't you cutting too much code? I can't see any definitions for SetPosition(), NullNumber() and shownumber(). Can you explain a bit about your code?Quote:
First Message. Here is a part of my program. You can calculate 10000!, maybe ore.
I am cutting code.
Peace always,
<jdenny>
Sorry , :D
INC(A,x,y):
Increase A[x] by y
NullNumber:
for all x upto Max_Digit , let A[x]=0
SetPosition:
Numbers are added into A[x] from left to write. Return , number's digit.
shownumber:
cout A[x] up to positionflag.
Here is the full-testing program. mult2() function and some of them are for testing ,you can delete them all.
Please look this site. You will find lots of interesting program codes.