# factorial

Page 1 of 1

## 11 Replies - 6212 Views - Last Post: 24 March 2007 - 05:59 PM

### #1 vennik

Reputation: 0
• Posts: 10
• Joined: 17-March 07

# factorial

Posted 17 March 2007 - 04:26 AM

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...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.

Is This A Good Question/Topic? 0

## Replies To: factorial

### #2 William_Wilson

• lost in compilation

Reputation: 207
• Posts: 4,812
• Joined: 23-December 05

## Re: factorial

Posted 17 March 2007 - 05:15 AM

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?

### #3 vennik

Reputation: 0
• Posts: 10
• Joined: 17-March 07

## Re: factorial

Posted 17 March 2007 - 06:59 AM

William_Wilson, on 17 Mar, 2007 - 05:15 AM, said:

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?

### #4 NickDMax

Reputation: 2254
• Posts: 9,245
• Joined: 18-February 07

## Re: factorial

Posted 17 March 2007 - 10:25 PM

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.

### #5 vennik

Reputation: 0
• Posts: 10
• Joined: 17-March 07

## Re: factorial

Posted 18 March 2007 - 03:25 AM

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).

NickDMax, on 17 Mar, 2007 - 10:25 PM, said:

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.

### #6 NickDMax

Reputation: 2254
• Posts: 9,245
• Joined: 18-February 07

## Re: factorial

Posted 18 March 2007 - 10:08 AM

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.

### #7 vennik

Reputation: 0
• Posts: 10
• Joined: 17-March 07

## Re: factorial

Posted 19 March 2007 - 11:10 AM

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

NickDMax, on 18 Mar, 2007 - 10:08 AM, said:

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.

### #8 Liontrue1

Reputation: 47
• Posts: 811
• Joined: 20-May 06

## Re: factorial

Posted 23 March 2007 - 07:38 AM

vennik, on 19 Mar, 2007 - 02:10 PM, said:

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

NickDMax, on 18 Mar, 2007 - 10:08 AM, said:

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.

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 William_Wilson

• lost in compilation

Reputation: 207
• Posts: 4,812
• Joined: 23-December 05

## 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:

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

NickDMax, on 18 Mar, 2007 - 10:08 AM, said:

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.

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 Liontrue1

Reputation: 47
• Posts: 811
• Joined: 20-May 06

## 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:

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

NickDMax, on 18 Mar, 2007 - 10:08 AM, said:

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.

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 Programmist

• Refactorer in Chief

Reputation: 255
• Posts: 1,843
• Joined: 02-January 06

## Re: factorial

Posted 23 March 2007 - 10:36 AM

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

### #12 vennik

Reputation: 0
• Posts: 10
• Joined: 17-March 07

## Re: factorial

Posted 24 March 2007 - 05:59 PM

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