1 Attachment(s)
Factorial calculation optimization
For a problem I'm working on, I need to calculate some very, very large factorials; or at least the first five non-zero digits of said factorial. I've worked out the function:
F(n) = ((n!)/(10S5(n)))%105
S5(n) = Attachment 1808 where p = 5 to get the trailing zeros of the factorial.
The Algorithm:
Code java:
public static void main(String[] args) {
// TODO Auto-generated method stub
Timer t = new Timer();//just a timer, can be replaced with long start = System.currentTimeMillis();
t.start();//^
long fact = 1;//variable containing the needed value
long limit = (long) 100000.0;//the nth factorial
long pow10 = 10;//powers of 10
for(long i = 2; i <= limit; i++)//for loop to calculate the needed factorial
{
fact*=i; // (i-1)! * i = i! at that point
while(fact%10==0)//does the fact/10^(s_5(i)) function to strip the trailing zeros
fact/=10;
fact %= 100000;// does the modulus to keep the numbers in bounds
if(i%pow10==0)//simply prints out the factorial of powers of ten
{
pow10*=10;
System.out.println(i + ": " + fact);
}
//System.out.println(i + ": " + fact);
}
System.out.println(fact);//print the result
t.end();//ends the timer and prints out the result
t.printElapsedTimeSeconds();//can be replaced with System.out.println("Elasped time: " + (System.currentTimeMillis()-start)/1000 + " seconds.");
}
I can't use De Polignac's formula because the required sieve would take too much memory and brute forcing every prime takes too long. This is the output of F(1000000000):
Code :
10: 36288
100: 16864
1000: 53472
10000: 79008
100000: 2496
1000000: 4544
10000000: 51552
100000000: 52032
1000000000: 64704
64704
Elapsed time: 13.476 sec.
I need to calculcate F(1000000000000) or F of 1 trillion. This would take a very long time, there has to be some optimization or tweak that I'm missing somewhere.
Re: Factorial calculation optimization
Hmm, interesting problem...
So you want to find the last 5 digits of n! after all the trailing zeros?
The first thing to do is eliminate all the trailing zero.
Each trailing zero equates to a prime factor pair of (2,5).
So first order of business is to eliminate all of these pairs. An easy way to do this is count up how many times n! is divisible by 5. Since this is always going to be smaller than the number of times n! is divisible by 2, we know that the factor 5 will be the limiting value of the (2,5) pairs.
Then as you're multiplying through, if a value is divisible by 2/5 and you haven't reached the limiting value for that number, divide the value by the appropriate value.
For example, let's take 10!:
There are two 5 prime factors of the result (5, 10).
Then as we multiply through, removing factors of 2 up to the limit:
num = 1
num = num * 2 / 2, two_count = 1
num = num * 3
num = num * 4 / 2, two_count = 2
num = num * 5 / 5, five_count = 1 (not actually necessary to keep track of five_count since every factor of 5 will be removed)
num = num * 6
num = num * 7
num = num * 8
num = num * 9
num = num * 10 / 5, five_count = 2 (not actually necessary to keep track of five_count since every factor of 5 will be removed)
Once you guarantee that the least significant digit is non-zero, you can use a simple math trick to calculate the last x digits of a*b:
You only need to multiply the last x digits from each number a, b to find the last x digits of the result.
For example, to find the last 2 digits of 123456 * 789012:
56 * 12 = 672
Last two digits are 72.
This last step isn't necessary for smaller factorials but is absolutely vital for larger numbers because there's the potential for a*b to overflow, especially for larger factorials.
The algorithm is O(1) space and ~O(n) runtime (possibly O(n log(n)), not sure about this).
Some run statistics (not comparable with your times because we likely have different hardware):
Quote:
10: 36288
100: 16864
1000: 53472
10000: 79008
100000: 62496
1000000: 12544
10000000: 94688
100000000: 54176
1000000000: 38144
Time taken: 21.404 s
Interestingly, there are some discrepancies between my answers and your answers, especially for larger factorials (possibly due to numerical errors, or my mis-understanding of program requirements). i checked using Wolfram Alpha and it looks like my answers are correct.
There might be some optimization for figuring out how many factors of 5 there are, I'm not sure.
You could also try optimizing by using divide and conquer and parallelizing, just make sure you ensure your counts are computed for each division (if you're going to try multi-threading).
1 Attachment(s)
Re: Factorial calculation optimization
Ok, well, you can use De Polignac's formula to figure out how many factors of a prime factor there are in n!.
Could you also explain this a different way?
Quote:
So first order of business is to eliminate all of these pairs. An easy way to do this is count up how many times n! is divisible by 5. Since this is always going to be smaller than the number of times n! is divisible by 2, we know that the factor 5 will be the limiting value of the (2,5) pairs.
Then as you're multiplying through, if a value is divisible by 2/5 and you haven't reached the limiting value for that number, divide the value by the appropriate value.
For example, let's take 10!:
There are two 5 prime factors of the result (5, 10).
Then as we multiply through, removing factors of 2 up to the limit:
num = 1
num = num * 2 / 2, two_count = 1
num = num * 3
num = num * 4 / 2, two_count = 2
num = num * 5 / 5, five_count = 1 (not actually necessary to keep track of five_count since every factor of 5 will be removed)
num = num * 6
num = num * 7
num = num * 8
num = num * 9
num = num * 10 / 5, five_count = 2 (not actually necessary to keep track of five_count since every factor of 5 will be removed)
This is a project Euler problem, so there is a solution possible that takes less than a few minutes possible. I noticed that there are a few thousand final five values under 100000! that have quite a few repetitions, so that says to me that there may be a way to predict when and where those repetitious values come up.
Re: Factorial calculation optimization
Hmm, after close examination of your code you're right they are very similar. The only difference is that you use De Polignac's Formula which is faster, but you failed to properly handle the factorial computation part.
In either case, much slower than should be expected for a Project Euler problem. Which problem number is it?
Re: Factorial calculation optimization
Problem 160 - Project Euler
Problem 160. I've been working on it for a while. First attempt was to brute force the factorial using JScience's LargeInteger class and huge multi-threading. That took too long. Then I moved to trying De Polignac's algorithm specifically, but brute forcing prime numbers took too long and a large enough sieve is impossible to do in Java. This is the only method that's come close to what's needed. I then noticed that there were last-five-digit-combos that never came up, and a whole lot that came up quite often. That's probably the key to figuring out the solution, but I don't know how to apply it.
Re: Factorial calculation optimization
Here's something I just thought of:
One of the key tricks we're taking advantage of is by only keeping track of the last 5 digits for multiplication. Even with 1 trillion factorial we're going to be repeatedly multiplying essentially these same 5 digit numbers over and over again. You might have some luck with either a quick integer power function or look-up tables to quickly compute the repeated multiplications. Dunno if it will work, but may be worth a shot.
