13,249,813 members (67,084 online)
Add your own
alternative version

#### Stats

88.5K views
2.4K downloads
26 bookmarked
Posted 26 Jul 2009

# 1000 Factorial

, 27 Jul 2009
 Rate this:
Please Sign up or sign in to vote.
Optimum algorithm for calculating factorial of large number

## Introduction

Factorial or the product of positive integer numbers is one of the most usable mathematical functions (or processes). A lot of mathematical calculations need to have exact result of great number's factorial, such as 1000! to find the final response with high accuracy. But the problem is that no programming language has a variable or mechanism to store such a big figure. All of the programming languages and calculators estimate the result and then store it as scientific number. For example, calculator of Windows XP displays 1000! like this:

`4.02387260077093773543702433923 e+2567 `

So I decided to invent an algorithm for solving this problem.

## Algorithm

You know to calculate factorial of a number, you should multiply all numbers from 1 to itself, for example:

`1000! = 1*2*3*……*998*999*1000 `

There is no variable in any programming language that can store the result of this multiplication exactly; except storing in scientific notation. Because of sequential multiplication's huge result, finding a new strategy or mechanism is necessary.

In my recommended algorithm, the number is not looked at as a number, instead it is treated as sequential digits where each one has its own numerical value. In fact, an array of digits is available. Each time, the second number is multiplied by each digit of the first number (index of array) and then added with carry number up from the previous multiplication.
This process is shown, for example 12!:

`12! = 11! * 12     11! = 39916800     12! = 479001600 `

• If the result is less than 10, the result will be placed in the cell of array.
• If it is equal to or greater than 10, it will be divided by 10 and then the remainder will be placed in the array's cell and quotient placed in variable that will be added with next multiplication's response.
Note: Notice that all the numbers are stored from end of array, the same as normal calculation (real calculation).

## Programming Code

### Declarations

```int numArr[3000];
int total,rem=0,count;
register int i;```

In the first line, an array is defined such that its size depends on factorial size. "`rem`" is defined to store remainder of division.

At the end , an integer variable is defined and named "`i`" that plays the role of loop counter and array's index and due to much access, it's defined as register.

The register type modifier tells the compiler to store the variable being declared in a CPU register (if possible), to optimize access.

Note: Modern compilers have a good optimizer that decides which variables should be stored in registers. They make their own register choices when global register-allocation optimization is on.

### The Main Part of the Code

```i=2999;				//start from end of array.
numArr[2999]=1;

for(count=2;count<=1000;count++)
{
while(i>0)
{
total=numArr[i]*count+rem;
rem=0;
if(total>9)
{
numArr[i]=total%10;
rem=total/10;
}
else
numArr[i]=total;
i--;
}
rem=0;
total=0;
i=2999;
}```

According to the algorithm that was explained before, there is a loop counting 2 to 1000 and each time value of '`count`' is multiplied by array's cell and added with '`rem`' which contains carry from previous multiplication.

Finally, the result is stored in '`total`' and then placed in the array's cell.

## Another Algorithm

At first, I found another algorithm for this problem. It's based on simulating multiplication by successive additions. For example 20= 4*5 also 20= (5+5+5+5).
So putting numbers in an array and then adding it with itself 'X' times.
X for 1000! is:

X= ∑ n
n=1,2,3, … ,999,1000

Note: This algorithm is not as optimum as the first one that I explained. Also it's too dull and needs several big arrays. The second ZIP file belong to this algorithm.

## Points of Interest

I would like to point out that the algorithm has high computing speed, so it turns the program to quite an optimum state.

One of the most important features of this algorithm is using just one array, while other algorithms need more memory (using several arrays to simulate multiplication by sequential sums).

Furthermore, less coding helps to understand the program easily and you can rewrite it in any programming language.

One of the reasons for high execution speed is using register variable as loop's counter. Loop's counter is a variable with most access to it.

## Usage

As I mentioned in the introduction, factorial operation is used in a lot of mathematical calculations, especially, the computations that relate to statistics that need exact result of factorial.

So this program can be part of any program that needs factorial method, such as statistical software.

## Appreciation

I'd like to thank Mr.Fermisk Naserzade for introducing me to this problem and Mr. Iraj Safa for helping me to edit this article.

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Iran (Islamic Republic of)
Mohammad Shafienia is student of MS of IT(Information Security) in Tehran University who has been coding since 1999. He was born in Tehran, the capital of Iran.
He has started programming by BASIC, but now he is .Net developer. AI and Low-Level programming are his favorite issues. He is good at team-working and participates in research projects.
Mohammad loves sport, specially volleyball and camping. He is such outgoing person and crazy about nature.
One of his wishes is to have laboratory same as Bell Lab, How ambitious.

To contact Mohammad, email him at shafienia[AT]gmail[DOT]com
www.iranexam.net

## Comments and Discussions

 First Prev Next
 congratulations Andy Allinger15-Dec-13 10:53 Andy Allinger 15-Dec-13 10:53
 Thank you Member 945166326-Jun-13 9:34 Member 9451663 26-Jun-13 9:34
 good work！ kspliusa28-Mar-12 21:40 kspliusa 28-Mar-12 21:40
 Also excellent jrobb22914-Feb-12 12:02 jrobb229 14-Feb-12 12:02
 Re: Also excellent Mohammad Shafieenia27-Oct-12 2:02 Mohammad Shafieenia 27-Oct-12 2:02
 excellent sir!!! kushal seth18-May-10 6:17 kushal seth 18-May-10 6:17
 Re: excellent sir!!! Mohammad Shafieenia27-Oct-12 1:59 Mohammad Shafieenia 27-Oct-12 1:59
 Need a break after if statement Pourya Shirazian4-Aug-09 7:48 Pourya Shirazian 4-Aug-09 7:48
 Re: Need a break after if statement Mohammad Shafieenia5-Aug-09 8:45 Mohammad Shafieenia 5-Aug-09 8:45
 very good! alejandro29A4-Aug-09 5:48 alejandro29A 4-Aug-09 5:48
 Re: very good! Mohammad Shafieenia4-Aug-09 10:22 Mohammad Shafieenia 4-Aug-09 10:22
 Excellent Anil Srivastava30-Jul-09 0:54 Anil Srivastava 30-Jul-09 0:54
 Re: Excellent Mohammad Shafieenia30-Jul-09 1:35 Mohammad Shafieenia 30-Jul-09 1:35
 Why don't you try to implement a more generalized solution zimstep27-Jul-09 22:40 zimstep 27-Jul-09 22:40
 why? MSHADroo27-Jul-09 12:19 MSHADroo 27-Jul-09 12:19
 Re: why? MSHADroo2-Aug-09 23:35 MSHADroo 2-Aug-09 23:35
 congratulation MSHADroo27-Jul-09 11:33 MSHADroo 27-Jul-09 11:33
 Re: congratulation Mohammad Shafieenia27-Jul-09 21:37 Mohammad Shafieenia 27-Jul-09 21:37
 Efficiency improvement supercat927-Jul-09 7:18 supercat9 27-Jul-09 7:18
 Re: Efficiency improvement Mohammad Shafieenia27-Jul-09 8:01 Mohammad Shafieenia 27-Jul-09 8:01
 Re: Efficiency improvement supercat927-Jul-09 19:57 supercat9 27-Jul-09 19:57
 Re: Efficiency improvement [modified] brianma5-Aug-09 0:30 brianma 5-Aug-09 0:30
 Re: Efficiency improvement supercat95-Aug-09 5:28 supercat9 5-Aug-09 5:28
 Re: Efficiency improvement Amin Ghadirian26-Jun-13 11:23 Amin Ghadirian 26-Jun-13 11:23
 "Only" up to 1142 mluri26-Jul-09 22:14 mluri 26-Jul-09 22:14
 You have used a fixed array of size 3000, so you can "only" calculate the factorial up to 1142!. Maybe it could be generalized to "any" size number? Besides, you say that the big speed (I haven't tried it, so I can't tell) is due to declaring the loop index as register. Have you compared the speed with not declaring it "register"? I would say that any modern compiler would do a good job in puting it in a register if it is used often, but I might be wrong.
 Re: "Only" up to 1142 Mohammad Shafieenia26-Jul-09 23:23 Mohammad Shafieenia 26-Jul-09 23:23
 Re: "Only" up to 1142 mluri27-Jul-09 0:20 mluri 27-Jul-09 0:20
 Re: "Only" up to 1142 Mohammad Shafieenia27-Jul-09 5:27 Mohammad Shafieenia 27-Jul-09 5:27
 Re: "Only" up to 1142 mluri27-Jul-09 0:24 mluri 27-Jul-09 0:24
 Re: "Only" up to 1142 Mohammad Shafieenia27-Jul-09 5:37 Mohammad Shafieenia 27-Jul-09 5:37
 Re: "Only" up to 1142 Rick York27-Jul-09 7:21 Rick York 27-Jul-09 7:21
 Re: "Only" up to 1142 zimstep27-Jul-09 22:51 zimstep 27-Jul-09 22:51
 [Message Deleted] Md. Marufuzzaman26-Jul-09 13:01 Md. Marufuzzaman 26-Jul-09 13:01
 Re: It's good Mohammad Shafieenia26-Jul-09 21:25 Mohammad Shafieenia 26-Jul-09 21:25
 Re: It's good Adrabi Abderrahim3-Aug-09 4:21 Adrabi Abderrahim 3-Aug-09 4:21
 Re: It's good Mohammad Shafieenia3-Aug-09 7:43 Mohammad Shafieenia 3-Aug-09 7:43
 Last Visit: 31-Dec-99 19:00     Last Update: 19-Nov-17 10:59 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.171114.1 | Last Updated 27 Jul 2009
Article Copyright 2009 by Mohammad Shafieenia
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid