Monday, February 13, 2017

1000000! - Statistics about 1 million factorial

So I calculated the number n = 1000000! = 1*2*...*n using my factorial calculating program here:

http://adrianloteanu.blogspot.com/2017/02/fast-factorial-calculator-applications.html

And here are some statistics about it:

1 000 000! has 5 565 709 digits and their sum is 23 903 442

Note that there are too many digits for me to display the number here.

Here is the distribution of digits 0-9 (how many of each digit there are):

 #0 = 782336 ( 0.140564 % )
 #1 = 532223 ( 0.095625 % )
 #2 = 532921 ( 0.095751 % )
 #3 = 531100 ( 0.095424 % )
 #4 = 532174 ( 0.095617 % )
 #5 = 531421 ( 0.095481 % )
 #6 = 531351 ( 0.095469 % )
 #7 = 530558 ( 0.095326 % )
 #8 = 530361 ( 0.095291 % )
 #9 = 531264 ( 0.095453 % )

The most common digit is "0" which seems to be true for most of the factorial numbers. 

The first few digits are:

1 000 000! =
826393168833124006237664610317266629113534797896387304516777588556337961103564508444653051131146397335 ....

 The last digits are of course a whole lot of 0's.

 The last non-zero digits are ...846349317400557393978919335572262720444928991567589948405211310582561765058412544

 The number is also approximately equal to 8.263 * 10^5565708


Fast Exact Factorial Calculator - Applications of Paralellism


I recently came across the need to calculate some fairly large values of factorials for which the standard common sizes of variables (32/64 bit) just would not do. Think values around 1 000 000!. So I wrote my own little mini-program to do it, based on the very cool BigInteger class available in Java. The problem is relatively trivial however I was not able to find a proper solution online so now I am sharing mine with the world. 

Some of the main ingredients for this application are:

1. The Java programming language

2. The BigInteger class defined in java.math.BigInteger. This class allows you to store and operate on integer numbers of any arbitrary size as they are stored internally as an array. The only practical limit is how big a number your RAM can hold. More details on the class can be found here:

https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html 

3. The Thread class. Basically anything in the "run" method of this class will run on a separate thread. Documentation can be found here:

https://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html

The idea is simple - I want to calculate n! = 1 * 2 * 3 * ... * n for relatively large values of n - say about 1 000 000!

 I can start with a BigInteger set to one and then in a loop from 1 to n multiply it with each number along the way. That means O(n) operations. However each multiplication gets more complicated as the numbers have more digits, and the number of digits grows fast as n! is a very fast growing function. Each multiplication would intuitively need a number of operations proportional to the square of the number of digits our numbers have (think about how you learned multiplication in school). I may be mistaken here but I think that the worst case complexity is O(n*log(n!)*log(n)) = O((nlog(n))^2).

But if I want to use the full resources of my 4 core 8 thread processor I need to distribute this work. So I let each of my T=8 threads multiply 1/T=1/8 of the numbers in this way:

Thread 1 will calculate : 1 * 9 * 17 * ... * (8k+1)
Thread 2 will calculate : 2 * 10 * 18 * ... * (8k+2)
....
Thread 8 will calculate : 8 * 16* 24 * ... * (8k+8)

This will work for any T and the application will automatically distribute the work on all available threads. The idea behind doing this interleaving of numbers and not just splitting the range 1..n into T different parts is that I want all threads multiplying numbers of roughly the same magnitude (number of digits). If Thread 1 would have multiplied numbers from 1 to T then it would have finished much faster then Thread T which would have done n-T to n as it would have been working with  much smaller numbers.

While improvements can still be made, this allowed me to calculate the value of
1 000 000! in under 30 seconds which was good enough for my purposes. Here is an approximation of how fast you can calculate n! with this program (depending on what computer you have):

Since time grows roughly proportionally with n*n (though theoretical complexity may differ) you won't be able to calculate too far beyond 10 000 000! in under 1 hour, depending of course on how fast your computer is. So this is one practical limitation. For my purpose, with values around n = 1 000 000, this is more than enough.

Here are some nice statistics about 1 000 000!:

http://adrianloteanu.blogspot.com/2017/02/1000000-statistics-about-1-million.html

Download the source code file here: factorial.java

Compile it with "javac factorial.java" and run with "java factorial <number>"

Here is the code:

Cheers!