11 Replies  5853 Views  Last Post: 24 March 2007  05:59 PM
#1
factorial
Posted 17 March 2007  04:26 AM
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...olov/b_n_f.htm), but I think that there is more efficiently decision of the problem (especially regading time consuming). Thank you in advance.
Replies To: factorial
#2
Re: factorial
Posted 17 March 2007  05:15 AM
why do you need 1000 factorial?
#3
Re: factorial
Posted 17 March 2007  06:59 AM
William_Wilson, on 17 Mar, 2007  05:15 AM, said:
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?
#4
Re: factorial
Posted 17 March 2007  10:25 PM
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.
#5
Re: factorial
Posted 18 March 2007  03:25 AM
Z=X.Y=X.(y(n1).10^(n1)+y(n2).10^(n2)+...+y(1).10^1+y(0).10^(0))=X.y(n2).10^(n2)+X.y(n3).10^(n3)+...+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=n1 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 rigthhand 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).
NickDMax, on 17 Mar, 2007  10:25 PM, said:
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.
#6
Re: factorial
Posted 18 March 2007  10:08 AM
#7
Re: factorial
Posted 19 March 2007  11:10 AM
NickDMax, on 18 Mar, 2007  10:08 AM, said:
#8
Re: factorial
Posted 23 March 2007  07:38 AM
vennik, on 19 Mar, 2007  02:10 PM, said:
NickDMax, on 18 Mar, 2007  10:08 AM, said:
To keep this simple, use this Java code:
public class test1{ public static void main (String[] args){ int fact = 1000; //Number to factorize for (int i=1; i<=fact; i++){ if (fact%i == 0){ //It works System.out.print (i + " "); //Print this number } } } }
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 March 2007  07:41 AM
#9
Re: factorial
Posted 23 March 2007  07:43 AM
alpha02, on 23 Mar, 2007  12:38 PM, said:
vennik, on 19 Mar, 2007  02:10 PM, said:
NickDMax, on 18 Mar, 2007  10:08 AM, said:
To keep this simple, use this Java code:
public class test1{ public static void main (String[] args){ int fact = 1000; //Number to factorize for (int i=1; i<=fact; i++){ if (fact%i == 0){ //It works System.out.print (i + " "); //Print this number } } } }
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
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
#10
Re: factorial
Posted 23 March 2007  09:38 AM
William_Wilson, on 23 Mar, 2007  10:43 AM, said:
alpha02, on 23 Mar, 2007  12:38 PM, said:
vennik, on 19 Mar, 2007  02:10 PM, said:
NickDMax, on 18 Mar, 2007  10:08 AM, said:
To keep this simple, use this Java code:
public class test1{ public static void main (String[] args){ int fact = 1000; //Number to factorize for (int i=1; i<=fact; i++){ if (fact%i == 0){ //It works System.out.print (i + " "); //Print this number } } } }
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
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:
public class test1{ public static void main (String[] args){ int fact = 1000; //Number to factorize int total = 1; for (int i=fact; i>0; i){ total = total*i; } System.out.println(total); } }
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 March 2007  09:39 AM
#11
Re: factorial
Posted 23 March 2007  10:36 AM
#12
Re: factorial
Posted 24 March 2007  05:59 PM
