Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 6 of 6

Thread: Factorial calculation optimization

  1. #1
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default 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) = ec6eb4f9e17c320d12784365efaad220.png where p = 5 to get the trailing zeros of the factorial.

    The Algorithm:
    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):

    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.


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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):

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

  3. #3
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default 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?

    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.

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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?

  5. #5
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

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

  6. #6
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

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

Similar Threads

  1. Having problem with factorial
    By wickedsunday in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 9th, 2012, 01:44 PM
  2. [SOLVED] Sine function, can't get factorial to work
    By Actinistia in forum What's Wrong With My Code?
    Replies: 4
    Last Post: May 27th, 2012, 11:24 AM
  3. [SOLVED] Is it possible to get factorial of negative number
    By Lokesh in forum Java Theory & Questions
    Replies: 3
    Last Post: August 4th, 2011, 05:45 PM
  4. Factorial and Factorion, that is the question!
    By Java Neil in forum What's Wrong With My Code?
    Replies: 2
    Last Post: February 25th, 2011, 06:54 PM
  5. [SOLVED] Factorial of 1-20
    By pitchblack in forum What's Wrong With My Code?
    Replies: 2
    Last Post: February 16th, 2011, 12:33 PM