12-11-2009, 02:18 PM | #1 | ||
Join Date: Oct 2004
Location: Opole, Poland
Posts: 14,276
|
C++: Does this make any sense?
Well, so here we are on sixth list of programming homework. One of the tasks is to use a function to return the factorial of an input number.
As anyone with a shred of common sense can realise, normal variables won't do here: the factorial exceeds the capacity of such variable types as unsigned __int64 and long double after reaching the factorial of 20. I've had an idea how to get around that and just finished scribbling it down. The code is crude as fuck, but we won't get anything such as pointers explained before next lecture (which as after we're supposed to turn in the homework, so...) I'd like to ask if someone less n00bish in C++ than myself could take a look at the thing. Code:
#include <iostream.h> #include <math.h> unsigned __int64 facseg(unsigned int n, long int position) { unsigned __int64 monster[n], mem=0; long int ind=0, mult=1, cut=12; for(monster[0]=1, mult=1; mult<=n; mult++) { for (ind=0; ind<n; ind++) { monster[ind]=(monster[ind]*mult)+mem; mem=monster[ind]/pow(10,cut); monster[ind]=monster[ind]%pow(10,cut); } if (mem!=0) { errorbit=1; return 0; } return monster[position]; } main() { unsigned int fa; cin >> fa; bool errorbit=0; cout << "\n"; facseg(fa, 0); if (errorbit) { cout << "ERROR: VALUE EXCEEDED\n"; } else { long int index=fa-1; while(facseg(fa,index)==0) { index--;} for (; index>=0; index--) { cout << facseg(fa, index); } } system("PAUSE"); } |
||
|
|
12-11-2009, 05:31 PM | #2 | ||
Join Date: May 2005
Location: Nitra, Slovakia
Posts: 6,533
|
i havent looked into the code but you could either:
a) store number as a string b) store it as an array of int/char c) use an external library d) google for more solutions? and by the way.. why do you think you need to make a function able to handle really big numbers? is it in assignment? you're just beginners, maybe they meant `just make a function that does it`, don't care about big numbers. like up to 5 or so also, your code looks kind of messy, have you thought about defining the function via recursion? like this: Code:
unsigned long long int fact (int n){ if(n==1){ return n; }else{ return n*fact(n-1); } } or you could cut it down to this Code:
unsigned long long int fact (int n){ (n==1)?(return n):(return n*fact(n-1)); }
__________________
Last edited by _r.u.s.s.; 12-11-2009 at 06:34 PM. Reason: ooops made a typo in the code |
||
|
|
12-11-2009, 06:07 PM | #3 | ||
Join Date: Oct 2004
Location: Opole, Poland
Posts: 14,276
|
b) is the basic idea. I'm trying to cut it into an array of unsigned __int64's
Starting from the code I posted above, this is what I got: Code:
#include <cstdlib> #include <iostream> #include <math.h> // !20=2432902008176640000 (19 digits) = maximum value a single unsigned __int64 can take. bool errorbit=0; using namespace std; unsigned __int64 facseg(unsigned __int64 n, __int64 position) { unsigned __int64 monster[(6*n)], mem=0, mult=1, cut=10; long int ind; for(ind=0; ind<(6*n); ind++) { monster[ind]=0; } for(monster[0]=1, mult=1; mult<=n; mult++) { for (ind=0; ind<(6*n) || (monster[ind]==0 && mem==0); ind++) { monster[ind]*=mult; monster[ind]+=mem; if (monster[ind]>=cut) { mem=monster[ind]/cut; monster[ind]=monster[ind]-(mem*cut); } else { mem=0; } } } if (mem!=0) { errorbit=1; return 0; } return monster[position]; } main() { system("CHCP 1250"); unsigned __int64 fa; cout << "Enter value..\n"; cin >> fa; facseg(fa, 0); if (errorbit) { cout << "ERROR: VALUE EXCEEDED\n"; } else { __int64 index=(6*fa)-1; while(facseg(fa,index)==0) { index--;} cout << index+1 << " digits.\n" ; cout << fa << "! = "; for (; index>=0; index--) { cout << facseg(fa, index); } } cout << "\n"; system("PAUSE"); } Otherwise zeros start vanishing from various places in the number.
__________________
"God. Can't you people see I'm trying to commit a crime against science and nature here?" -- Reed Richards Last edited by The Fifth Horseman; 12-11-2009 at 06:12 PM. |
||
|
|
12-11-2009, 06:09 PM | #4 | ||
Join Date: May 2005
Location: Nitra, Slovakia
Posts: 6,533
|
why do you actually try to store them as an array of 64 bit ints? o_O
why not array of 0..9?
__________________
Last edited by _r.u.s.s.; 12-11-2009 at 06:15 PM. |
||
|
|
12-11-2009, 06:38 PM | #5 | ||
Join Date: Oct 2004
Location: Opole, Poland
Posts: 14,276
|
Was trying to keep it in larger chunks than one digit each. That, obviously, didn't work out.
|
||
|
|
12-11-2009, 06:53 PM | #6 | ||
Join Date: May 2005
Location: Nitra, Slovakia
Posts: 6,533
|
that would most probably three times more complex than defining your own multiplication function via array of digits
by the way, i installed this dev c++ right now and wrote the recursive version for you. try it.. trust me Code:
unsigned long long int fac(unsigned int n){ (n==1)?:(n=n*fac(n-1)); return n; }
__________________
|
||
|
|
13-11-2009, 06:32 AM | #7 | ||
Join Date: Nov 2009
Location: Alpine Village, United States
Posts: 19
|
The teacher probably wants you to write your own multiplication function and return the result as a string. This is the only way to get it to be precise to an arbitrary length.
|
||
|
|
15-11-2009, 06:18 AM | #8 | ||
Join Date: Aug 2009
Location: Cankaya, Turkey
Posts: 3
|
are you sure teacher wanted a function that ables to show factorial of large numbers like 100?
it is not possible in practical using with even unsigned long. i think it is also not possible to calculate it with forwarding it to string, you still need to have an integer for multiplication. there would be some mathematic libraries out there but i think your teacher don't want you to use them. there is an open source calculator speedcrunch, you can examine its codes for handling large numbers if you want. but it will be really painful. |
||
|
|
15-11-2009, 11:19 AM | #9 | ||
Join Date: Oct 2004
Location: Opole, Poland
Posts: 14,276
|
The only real requirement was to make it calculate a factorial, not actually return that to the parent function. The teacher is very insistent about every program having to output the results to the user, though.
This is what I ended up with - the program stores the number as nine-digit chunks in an array of unsigned integers. Code:
#include <cstdlib> #include <iostream> #include <iomanip> #include <math.h> using namespace std; void factorial(unsigned __int64); main() { system("CHCP 1250"); unsigned __int64 x; cout << "Enter value...\n"; cin >> x; if (x>841814) { cout << "ERROR: VALUE EXCEEDED\n"; } else { factorial(x); } system("PAUSE"); } void factorial(unsigned __int64 n) { unsigned __int64 mem=0, mult=1, calc, celsize=9, digits=0, max=int(ceil(n*5.565709/celsize)), cut=int(pow(10,celsize)); unsigned int monster[max]; __int64 i, im1=0; for(i=0; i<max; i++) { monster[i]=0; } for(monster[0]=1; mult<=n; mult++) { for (i=0; (i<=im1 || monster[i]!=0 || mem!=0) && i<max; i++) { calc=monster[i]*mult+mem; monster[i]=calc%cut; mem=(calc>=cut)?calc/cut:0; } im1=i-1; if (mem!=0) { cout << "ERROR: TABLE BOUNDARY EXCEEDED\n"; return; } else if (mult<n) { cout << mult << "!\n"; } } i=im1; for (int dec=0; monster[i]>=int(pow(10,dec)); dec++) {digits++; } digits+=(i*celsize); cout << n << "! = " << int(monster[i]); for (i--; i>=0; i--) { cout << setw(celsize) << setfill('0') << monster[i]; } cout << "\n(" << digits << " digits)\n" ; cout << "(" << n << "!)\n" ; return; } The limit I imposed was an estimate based on calculation of the maximum size of monster array (anything over 520588 elements crashes the executable), multiplied by the number of digits per array element (nine) and divided by the proportion between the size of the factorial in calculation to its number of digits (for factorial of one million it's 5.565709 digits per one point of the number's size), thus: 841814.
__________________
"God. Can't you people see I'm trying to commit a crime against science and nature here?" -- Reed Richards Last edited by The Fifth Horseman; 15-11-2009 at 11:30 AM. |
||
|
|
|
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
I Wish To Make A Statement... | songnar | Blah, blah, blah... | 22 | 11-01-2007 09:06 AM |
I Wanna Make An Rpg | Bobbin Threadbare | Programming | 19 | 03-11-2006 07:59 AM |
Name The Car Make | efthimios | Forum Games | 75 | 08-12-2005 12:44 PM |
Make Dosbox Larger Without Make It Fullscreen | _\Magus/_ | Tech Corner | 4 | 02-05-2005 07:57 PM |
|
|
||
  |