## 11 Replies - 6318 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(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).

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