Hello,
I search efective algorithm for calculating factorial of big number (f.e. 1000 or even more). It is not easy task, because the result is very huge. I have written some program in C# that calculate it (you can see it here: http://www.geocities.com/ventsislavnikolov/b_n_f.htm), but I think that there is more efficiently decision of the problem (especially regading time consuming). Thank you in advance.

in practice large factorials are not calculated becasue they must traverse each element. There are method to estimate large factorials accurately, as well as using prime factorization to calculate precisely, but these are large algorithms and very complicated.

why do you need 1000 factorial?

I need to calculate factorial in my job, there is real situation to reach value near to 1000. Do you know where I could find more information for the methods you are talking about?

well lets see mathematica does 1000! is well less then 1 second on my 2Ghz pc (my machine is very slow and old).

You are right that there are faster algorithems then just the standard recursive ones.

Now these numbers don't fit into a double: 1000! ruffly = 4.0238726x10^2567

so you need to think about the format you want the number in as that has a lot to do with how you will construct the algorithm.

I know of two aproches. One is to view the thing as a polynomial and use the polynomial algorithm. The other does a ruff and dirty factorization and uses the pow() function to cut down on the multiplications.

I use polymonial wrote multiplier and the product is in kind shown below:
Z=X.Y=X.(y(n-1).10^(n-1)+y(n-2).10^(n-2)+...+y(1).10^1+y(0).10^(0))=X.y(n-2).10^(n-2)+X.y(n-3).10^(n-3)+...+X.y(1).10^(1)+X.y(0).2^(0)
y(i) is consequtive digit of multiplier in n digits decimal area(i=0 is junior, i=n-1 is senior digit). The count of addends is equals to digits of the multiplier. The scheme I use is:

-------> ------>
---------------------- -----------------------------
| | | | |
---------------------- -----------------------------
transitory sum multiplier |-> y(i)
+
----------------------
| |
----------------------
multiplicant

in every step is forming product ((multiplicant).y(i)) and add the result to the current transitory sum (in the beggining transitory sum is 0), after that I shift transitory sum and multiplier one digit rigth-hand side and the operation repeate. After consideration of all multiplier digits, the transitory sum is final result.
In that way I forming multiplication to calculate factorial, but transitory sum grow bigger ang bigger and I use string for its representation. When I need to process it I work in portions that could be represent in C# long int type, and after that every portion is again transfrom in string that is put into string represented transitory sum. Moreover multiplier and multiplicant grow up too in the process of factorial calculation, so I need to represent them like a strings too. Frequently transform from string to long int data type and back into the string is slow. But in truth also maybe I could consider some other algorithm to calculate factorial. But I need it to be accurate (not round).

well rather than try to write out an example myself here is link to several algorithems: Fast Factorial Functions I think you will find much more there than I would be able to type out.

Yes, there is useful information. Thank you very much.

To keep this simple, use this Java code:



This code prints all factors of this number. In this example, the output is:
1 2 4 5 8 10 20 25 40 50 100 125 200 250 500 1000

This post has been edited by alpha02: 23 Mar, 2007 - 06:41 AM

he was looking for a factorial, not a factor, these are completely different:
a factorial is of the form:
5! = 5*4*3*2*1

ah ok. well someone can find my code useul, and for a factorial I thought about:



It outputs the number. However I'm afraid this will not work if the number is too high because of Java's data types limitations, but it is worth the try.

This post has been edited by alpha02: 23 Mar, 2007 - 08:39 AM

Java's BigInteger class will buy you a little more breathing room, but with some factorial algorithms, it's a losing battle.

There is algorithms solve problem without using of BigInteger class. Just must some ingenuity.