Thread: Factorial

well its pretty easy to compute fact of small numbers...
but hhow will i calculate facorial of large numbers say fact(1000)
...

i am sure that this can be done with some short cut methods or manipulating strings...
some short cut methods will be very helpful
any suggestions on how to proceed

You should read the contest page....

wats contest page

I think the only "shortcut" you could really take would be partial memoization for multiple calls or delayed expansion.

I took a look at iMalc's class, and I think this should work. (He doesn't seem to do anything weird.)

The only shortcut I could [...] output after the number.

What about watching for given powers of 2 so you could shift the values instead of multiplying them? I guess that would only be an advantage for 'BigNum' libraries that had a good shift and a bad multiplication.

It just popped into my head. I have too much of a headache to think about.

Soma

Code:

template
<
   unsigned int bits_F
>
struct factorial_type
{
   typedef ubigint<bits_F> result_type;
   typedef unsigned long memoiry_type;
   typedef std::map<memoiry_type, result_type> memoiry_container;
   factorial_type
   (
      const memoiry_type & memoization_percentage_f = 10,
      const memoiry_type & initial_memoization_f = 250,
   ):
      memoization_percentage_m(memoization_percentage_f)
   {
      factorial(initial_memoization_f);
   }
   result_type factorial
   (
      const memoiry_type & value_f
   )
   {
      if(0 == (value_f % memoization_percentage_m))
      {
         const typename memoiry_container::const_iterator cursor(memoiry_m.find(value_f));
         if(memoiry_m.end() == cursor)
         {
            memoiry_m[value_f] = result_type(value_f) * factorial(value_f - 1);
         }
         return(memoiry_m[value_f]);
      }
      else
      {
         return(value_f == 1 ? result_type(1) : result_type(value_f) * factorial(value_f - 1));
      }
   }
   memoiry_type memoization_percentage_m;
   memoiry_container memoiry_m;
};