Factorial

This is a discussion on Factorial within the C++ Programming forums, part of the General Programming Boards category; well its pretty easy to compute fact of small numbers... but hhow will i calculate facorial of large numbers say ...

  1. #1
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197

    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

  2. #2
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,231
    I don't know about shortcuts. But there are some libraries that handle big numbers.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You should read the contest page....

  4. #4
    dpp
    dpp is offline
    Registered User
    Join Date
    Jan 2009
    Posts
    197
    wats contest page

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,332
    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;
    };

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by phantomotap View Post
    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!
    Last edited by iMalc; 02-01-2009 at 11:50 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Apr 2006
    Posts
    2,050
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Segmentation fault using recursion to find factorial
    By kapok in forum C++ Programming
    Replies: 4
    Last Post: 02-23-2009, 10:10 AM
  2. Factorial
    By foxman in forum Contests Board
    Replies: 27
    Last Post: 07-11-2008, 06:59 PM
  3. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 AM
  4. Basic Factorial from 1-10
    By AaA in forum C Programming
    Replies: 20
    Last Post: 05-28-2005, 07:39 AM
  5. factorial output
    By maloy in forum C Programming
    Replies: 1
    Last Post: 03-13-2002, 02:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21