«

[The Fifth Horseman]

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.

#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");
}

[_r.u.s.s.]

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:

unsigned long long int fact (int n){
  if(n==1){
    return n;
  }else{
    return n*fact(n-1);
  }
}

that's the whole code

or you could cut it down to this

unsigned long long int fact (int n){
  (n==1)?(return n):(return n*fact(n-1));
}

but i'm not really a c guy so i'm not sure if the syntax is correct

[The Fifth Horseman]

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:

#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");
}

It seems to actually work, but only as long as the cut variable (which is responsible for determining if the array element needs to have its' upper registers moved to the higher cell) doesn't exceed 10.
Otherwise zeros start vanishing from various places in the number.

[_r.u.s.s.]

why do you actually try to store them as an array of 64 bit ints? o_O
why not array of 0..9?

[The Fifth Horseman]

Was trying to keep it in larger chunks than one digit each. That, obviously, didn't work out.

[_r.u.s.s.]

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

unsigned long long int fac(unsigned int n){
 (n==1)?:(n=n*fac(n-1));
 return n;
}

[PixelDao]

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.

[Bonecrusher]

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.

[The Fifth Horseman]

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.

#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;
   }

When tested, it didn't have much problems with returning factorials up to 200000. Didn't test it for greater numbers yet.

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.