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

I don't know about shortcuts. But there are some libraries that handle big numbers.

You should read the contest page....

wats contest page

You would ust some kind of bignum library like GMP, or a home made one like I have on my website.

The only shortcut I could think of would be to remove a great deal of those trailing zeros by instead of multiplying by a number like 30, or 700 etc, you just multiply by 3 or 7 and increment a count of how many zeros the number had, 1 or 2, then you'll end up with a slightly smaller memory footprint and a whole lot of extra zeros to output after the number.
It'll still get massive though.

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

Originally Posted by phantomotap

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.

Yeah that could work too. You'd add up all the shift amounts and do one huge shift at the end. I guess you'd keep memory usage lower until right at the end when it would jump up a lot in the final shift. By doing it with powers of 10 instead, (10 being the base the number is displayed in) you can totally avoid and shift at the end and just have a loop outputting nothing but zeros.
I guess you could even do both!

base 10 makes the most sense, because it enables you to print the stored number the normal way, then print the right number of zeros. This assumes that the only thing you are doing with the result is printing them. Otherwise the technique is useless.

But if you are using a big number library, why bother.



The shortcut that comes to my mind is to have a look up table the factorial of certain milestone numbers. So if you want to find the factorial of 1052, your program may find find the product of all numbers 1001-1052, and multiply that by the stored value of 1000 factorial. The look up table should probably be logarithmically scaled, unless there is an upper bound to numbers you want your program to operate on.