# Intro and Problem Statement

Hello again everybody, this is the second follow up to my post about my Arbitrary Precision Calculator, PowArray. In this post I will be revealing and discussing my solution to Project Euler problem #20 (the basis for my Factorial calculator in PowArray).

Problem #20 states the following:

Factorial digit sumn! means n × (n − 1) × … × 3 × 2 × 1

For example, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,

and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.Find the sum of the digits in the number 100!

# A Foreword

I’ll limit the number of words in this post in favor of code, as the ideas are pretty similar and not worth reiterating verbatim.

Before jumping right into the solution, it is important to note that it is not a conventional one. Instead of directly looping all the numbers from 2 to n, with n being the argument of the factorial, I decided to calculate the prime factorization of the factorial first, and use those prime factors to calculate the factorial. This would eliminate the hassle of dealing with trailing zeroes in the calculation algorithm, as

the correct amount of factors of two and five would be compensated for in the beginning, and the trailing zeroes would be added back on when printing the result.

# Getting User Input

Now getting into the solution, the first thing needed to be done as usual, is getting user input. In this case, this will simply be the integer argument to pass to the factorial function.

private static Scanner in; public static void main(String args[]) { // ---GET INTEGER X FROM SCANNER INPUT--- in = new Scanner(System.in); System.out.println("Enter an integer x"); System.out.println(); int x = in.nextInt(); System.out.println(); }

# The Preliminary Optimization

Next comes getting the prime factorization:

// --- VARIABLE DECLARATION FOR PRIME FACTORIZATION ALGORITHM--- ArrayList<Integer> prime = new ArrayList<Integer>(); ArrayList<Integer> primequant = new ArrayList<Integer>(); boolean added = false; int size = 0; int i = 0; // --- PRIME FACTORIZATION ALGORITHM--- // In a loop 2 to x, find the prime factorization of i. for (int n = 2; n <= x; n++) { i = n; for (int j = 2; j <= i / j; j++) { while (i % j == 0) { // Search for each prime factor in an Integer ArrayList // called prime. for (int k = 0; k < prime.size(); k++) { // If it is there, then in another // Integer ArrayList describing the amount of times // that factor appears called primequant (the indices // match, meaning that the index ind of the prime array // corresponds to the same index in the // primequant array) add 1. if (prime.get(k) == j) { size = primequant.get(k); primequant.remove(k); primequant.add(k, size + 1); added = true; break; } } // If it isn't there, put the prime factor in // prime and initialize the quantity of that prime to 1 in // primequant. if (!added) { prime.add(j); primequant.add(1); } i /= j; added = false; } } // if i is decomposed into a prime factor, add it to the list of // primes if (i > 1) { // search for factor in prime and repeat algorithm as described // above for (int k = 0; k < prime.size(); k++) { if (prime.get(k) == i) { size = primequant.get(k); primequant.remove(k); primequant.add(k, size + 1); added = true; break; } } if (!added) { prime.add(i); primequant.add(1); } added = false; } } // Calculate the # of trailing zeros and subtract factors of five from // factors of two in order to prevent calculation errors due to // an accumulation of trailing zeroes. Finally, update ArrayList prime // with the balance. int twocount = 0; int fivecount = 0; int trailzeros = 0; for (int k = 0; k < prime.size(); k++) { if (prime.get(k) == 5) { fivecount = primequant.get(k); prime.remove(k); primequant.remove(k); break; } } for (int k = 0; k < prime.size(); k++) { if (prime.get(k) == 2) { twocount = primequant.get(k); primequant.remove(k); primequant.add(k, twocount - fivecount); break; } } trailzeros = fivecount;

# The Nitty Gritty

Once the prime factorization is calculated, the factors from the prime array and their quantities will be passed to the factorial calculation algorithm. Here it is:

// ---VARIABLE DECLARATION FOR FACTORIAL ALGORITHM--- // ***Note that the array being used to store the final result will // have to be instantiated with a predefined size. This can be any // integer below 2^31-1 as long as memory permits.*** // The size of the final product array declared below is enough to hold // up to 10000! byte[] finalprod = new byte[35660]; finalprod[finalprod.length - 1] = 1; int digprod = 0; int carryover = 0; int zerocount = 0; i = finalprod.length - 1; // curprime to the power of curpow will be calculated int curprime = 0; int curpow = 0; int digits = 0; List<Byte> digarray = new ArrayList<Byte>(); // For Adding Lines in Multi-Digit Multiplication int sumcarry = 0; int digsum = 0; boolean zerook = false; // ---ALGORITHM FOR CALCULATING X!--- // Multiply each of the primes together in the ArrayList prime // and store the result in a new ArrayList called finalprod. // Each individual prime factor taken from the prime ArrayList will be // exponentiated to the power of the quantity of that prime taken from // the primequant ArrayList. // Essentially the algorithm will be similar to that used to solve PE // #16, with the additional requirement that most of the factors will // have multiple digits. for (int pri = 0; pri < prime.size(); pri++) { curprime = prime.get(pri); curpow = primequant.get(pri); // Get number of digits in curprime, the current base. while (curprime > 0) { digarray.add((byte) (curprime % 10)); curprime /= 10; digits++; } Collections.reverse(digarray); curprime = prime.get(pri); for (int pow = 0; pow < curpow; pow++) { // Execute multi-line multiplication if the current factor has // more than one digit. if (digits > 1) { // A two dimensional array such that there is an array for // each line in the multiplication. Once these are filled, // they will be added together. byte[][] lines = new byte[digits][finalprod.length]; // A temporary two dimensional array to store the values of // the line arrays. byte[][] temparray = new byte[digits - 1][finalprod.length]; for (int init = 0; init < finalprod.length; init++) { for (int lineind = 0; lineind < digits; lineind++) { // initialize lines with // value of finalprod lines[lineind][init] = finalprod[init]; } } // Calculate the multiplications and fill the lines // according to the pencil and paper algorithm for long multiplication. // The loop will run according to the one line per digit // rule. for (int z = 0; z < digits; z++) { { // Check if 100 leading zeroes have been counted and // if the index variable has reached the // beginning of the array. If both are true, perform // the next multiplication. while (zerocount < 100 && i >= 0) { // Get the product of the current digit of the // base and the digit stored in the current // index of the current line. digprod = lines[z][i] * digarray.get(z); // Get the mod 10 of the product and add it to // carryover. Take the mod 10 of the whole // expression. This will ensure that no // matter how large the product is // (it will always be between 0 - 81), only a // single digit will be stored in each cell. lines[z][i] = (byte) ((digprod % 10 + carryover) % 10); // The carryover will simply be the tens digit // of the product plus the previous carryover. carryover = (digprod + carryover) / 10; // Check if all that remains in the array are // leading zeroes. Zerocount // will increment by 1 every time 4 // consecutive zeroes are found. if (i > 2 && lines[z][i] == 0 && lines[z][i - 1] == 0 && lines[z][i - 2] == 0 && lines[z][i - 3] == 0) { zerocount++; } // Shift the array index down by one for the // next iteration. i--; } // Reset values. carryover = 0; zerocount = 0; i = finalprod.length - 1; } // If the current digit is 0, store a value of 0 in all // indeces in the corresponding line. if (digarray.get(z) == 0) { for (int run = 0; run < finalprod.length; run++) { lines[z][run] = 0; } } } // Store value of the lines which need zeroes to be appended // (as per the pen and pencil long multiplication algorithm) // in temparray. for (int init = 0; init < finalprod.length; init++) { for (int tempind = 0; tempind < digits - 1; tempind++) { temparray[tempind][init] = lines[tempind][init]; } } for (int q = 0; q < digits - 1; q++) { // Append necessary zeros to each line array in // lines at beginning. for (int zeroind = digits - q - 1; zeroind >= 0; zeroind--) { lines[q][finalprod.length - 1 - zeroind] = 0; } // Restore the original values to the lines two // dimensional array with the appended zeroes. for (int index = finalprod.length - (digits - q); index >= 0; index--) { lines[q][index] = temparray[q][index + (digits - q - 1)]; } } // Initialize the finalprod array with a value of 0 in each // index. for (int init = 0; init < finalprod.length; init++) { finalprod[init] = 0; } // Sum the lines together after multiplying and // store the result in finalprod (in a similar fashion as // the multiplication algorithm). while (zerocount < 100 && i >= 0) { for (int digsumind = 0; digsumind < digits; digsumind++) { // Get the sum across all the lines at each index. digsum += lines[digsumind][i]; } // Store the value of the sum modulo 10 plus the // sum carryover value, then take the modulo 10 of // the whole expression. Similarly to the multiplication // algorithm, this will ensure that a single digit will // be stored in each index no matter how large the sum // is (between 0 - 18). finalprod[i] = (byte) ((digsum % 10 + sumcarry) % 10); // The sum carryover will simply be the tens digit of // the sum plus the previous sum carryover. sumcarry = (digsum + sumcarry) / 10; // Check if all that remains in the array are leading // zeroes. Zerocount will increment by 1 every time 4 // consecutive zeroes are found. A boolean zerook keeps // track of whether four consecutive zeroes are being // found. Only then will zerocount increment. for (int digsumind = 0; digsumind < digits; digsumind++) { if (i > 2 && lines[digsumind][i] == 0 && lines[digsumind][i - 1] == 0 && lines[digsumind][i - 2] == 0 && lines[digsumind][i - 3] == 0) { zerook = true; } else { zerook = false; } } if (zerook) { zerocount++; } if (!zerook) { zerocount = 0; } // Shift the array index down by one for the next // iteration. i--; // Reset values. zerook = false; digsum = 0; } // Reset values. sumcarry = 0; zerocount = 0; i = finalprod.length - 1; } else { // Execute single-line multiplication if the current factor // has // only one digit. This algorithm is identical to the one // used // in my PE #16 solution. while (zerocount < 100 && i >= 0) { digprod = finalprod[i] * curprime; finalprod[i] = (byte) ((digprod % 10 + carryover) % 10); carryover = (digprod + carryover) / 10; if (i > 2 && finalprod[i] == 0 && finalprod[i - 1] == 0 && finalprod[i - 2] == 0 && finalprod[i - 3] == 0) { zerocount++; } i--; } carryover = 0; zerocount = 0; i = finalprod.length - 1; } } // Reset values. digits = 0; digarray.clear(); }

# The Final Pieces

Next after calculating the factorial, we can calculate the sum of the digits as so:

// ---CALCULATE SUM OF DIGITS--- int finalsum = 0; List<Byte> finalprodarray = new ArrayList<Byte>(); System.out.println(x + "! = "); System.out.println();

Finally, we can print out the result as well as the sum of its digits, the number of digits and the number of trailing zeroes in the result.

// ---PRINT OUTPUT - THE FACTORIAL CALCULATION RESULT, THE SUM OF THE // DIGITS, // THE NUMBER OF DIGITS AND THE NUMBER OF TRAILING ZEROES--- for (int a = finalprod.length - 1; a >= 0; a--) { finalsum += finalprod[a]; finalprodarray.add(finalprod[a]); } Collections.reverse(finalprodarray); while (finalprodarray.get(0) == 0 && finalprodarray.get(1) == 0) { finalprodarray.remove(0); } finalprodarray.remove(0); // Put trailing zeroes at the end of the finalprodarray. for (int b = 0; b < trailzeros; b++) { finalprodarray.add(finalprodarray.size(), (byte) 0); } // Print x! int charcount = 0; for (int b = 0; b < finalprodarray.size(); b++) { if (charcount == 44) { System.out.println(); charcount = 0; } System.out.print(finalprodarray.get(b)); charcount++; } // Print the sum of the digits, the number of digits and the number of // trailing zeroes. System.out.println(); System.out.println(); System.out.println("The sum of the digits in " + x + "! = " + finalsum); System.out.println(); System.out.println("The number of digits in " + x + "! is " + finalprodarray.size() + " digits"); System.out.println(); System.out.println("The number of trailing zeros in " + x + "! is " + trailzeros);

# The Whole Shebang

Putting it all together, we have:

package projectEuler; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class FactorialDigitSum { private static Scanner in; public static void main(String args[]) { // ---GET INTEGER X FROM SCANNER INPUT--- in = new Scanner(System.in); System.out.println("Enter an integer x"); System.out.println(); int x = in.nextInt(); System.out.println(); // --- VARIABLE DECLARATION FOR PRIME FACTORIZATION ALGORITHM--- ArrayList<Integer> prime = new ArrayList<Integer>(); ArrayList<Integer> primequant = new ArrayList<Integer>(); boolean added = false; int size = 0; int i = 0; // --- PRIME FACTORIZATION ALGORITHM--- // In a loop 2 to x, find the prime factorization of i. for (int n = 2; n <= x; n++) { i = n; for (int j = 2; j <= i / j; j++) { while (i % j == 0) { // Search for each prime factor in an Integer ArrayList // called prime. for (int k = 0; k < prime.size(); k++) { // If it is there, then in another // Integer ArrayList describing the amount of times // that factor appears called primequant (the indices // match, meaning that the index ind of the prime array // corresponds to the same index in the // primequant array) add 1. if (prime.get(k) == j) { size = primequant.get(k); primequant.remove(k); primequant.add(k, size + 1); added = true; break; } } // If it isn't there, put the prime factor in // prime and initialize the quantity of that prime to 1 in // primequant. if (!added) { prime.add(j); primequant.add(1); } i /= j; added = false; } } // if i is decomposed into a prime factor, add it to the list of // primes if (i > 1) { // search for factor in prime and repeat algorithm as described // above for (int k = 0; k < prime.size(); k++) { if (prime.get(k) == i) { size = primequant.get(k); primequant.remove(k); primequant.add(k, size + 1); added = true; break; } } if (!added) { prime.add(i); primequant.add(1); } added = false; } } // Calculate the # of trailing zeros and subtract factors of five from // factors of two in order to prevent calculation errors due to // an accumulation of trailing zeroes. Finally, update ArrayList prime // with the balance. int twocount = 0; int fivecount = 0; int trailzeros = 0; for (int k = 0; k < prime.size(); k++) { if (prime.get(k) == 5) { fivecount = primequant.get(k); prime.remove(k); primequant.remove(k); break; } } for (int k = 0; k < prime.size(); k++) { if (prime.get(k) == 2) { twocount = primequant.get(k); primequant.remove(k); primequant.add(k, twocount - fivecount); break; } } trailzeros = fivecount; // ---VARIABLE DECLARATION FOR FACTORIAL ALGORITHM--- // ***Note that the array being used to store the final result will // have to be instantiated with a predefined size. This can be any // integer below 2^31-1 as long as memory permits.*** // The size of the final product array declared below is enough to hold // up to 10000! byte[] finalprod = new byte[35660]; finalprod[finalprod.length - 1] = 1; int digprod = 0; int carryover = 0; int zerocount = 0; i = finalprod.length - 1; // curprime to the power of curpow will be calculated int curprime = 0; int curpow = 0; int digits = 0; List<Byte> digarray = new ArrayList<Byte>(); // For Adding Lines in Multi-Digit Multiplication int sumcarry = 0; int digsum = 0; boolean zerook = false; // ---ALGORITHM FOR CALCULATING X!--- // Multiply each of the primes together in the ArrayList prime // and store the result in a new ArrayList called finalprod. // Each individual prime factor taken from the prime ArrayList will be // exponentiated to the power of the quantity of that prime taken from // the primequant ArrayList. // Essentially the algorithm will be similar to that used to solve PE // #16, with the additional requirement that most of the factors will // have multiple digits. for (int pri = 0; pri < prime.size(); pri++) { curprime = prime.get(pri); curpow = primequant.get(pri); // Get number of digits in curprime, the current base. while (curprime > 0) { digarray.add((byte) (curprime % 10)); curprime /= 10; digits++; } Collections.reverse(digarray); curprime = prime.get(pri); for (int pow = 0; pow < curpow; pow++) { // Execute multi-line multiplication if the current factor has // more than one digit. if (digits > 1) { // A two dimensional array such that there is an array for // each line in the multiplication. Once these are filled, // they will be added together. byte[][] lines = new byte[digits][finalprod.length]; // A temporary two dimensional array to store the values of // the line arrays. byte[][] temparray = new byte[digits - 1][finalprod.length]; for (int init = 0; init < finalprod.length; init++) { for (int lineind = 0; lineind < digits; lineind++) { // initialize lines with // value of finalprod lines[lineind][init] = finalprod[init]; } } // Calculate the multiplications and fill the lines // according to the pencil and paper algorithm for long // multiplication. // The loop will run according to the one line per digit // rule. for (int z = 0; z < digits; z++) { { // Check if 100 leading zeroes have been counted and // if the index variable has reached the // beginning of the array. If both are true, perform // the next multiplication. while (zerocount < 100 && i >= 0) { // Get the product of the current digit of the // base and the digit stored in the current // index of the current line. digprod = lines[z][i] * digarray.get(z); // Get the mod 10 of the product and add it to // carryover. Take the mod 10 of the whole // expression. This will ensure that no // matter how large the product is // (it will always be between 0 - 81), only a // single digit will be stored in each cell. lines[z][i] = (byte) ((digprod % 10 + carryover) % 10); // The carryover will simply be the tens digit // of the product plus the previous carryover. carryover = (digprod + carryover) / 10; // Check if all that remains in the array are // leading zeroes. Zerocount // will increment by 1 every time 4 // consecutive zeroes are found. if (i > 2 && lines[z][i] == 0 && lines[z][i - 1] == 0 && lines[z][i - 2] == 0 && lines[z][i - 3] == 0) { zerocount++; } // Shift the array index down by one for the // next iteration. i--; } // Reset values. carryover = 0; zerocount = 0; i = finalprod.length - 1; } // If the current digit is 0, store a value of 0 in all // indeces in the corresponding line. if (digarray.get(z) == 0) { for (int run = 0; run < finalprod.length; run++) { lines[z][run] = 0; } } } // Store value of the lines which need zeroes to be appended // (as per the pen and pencil long multiplication algorithm) // in temparray. for (int init = 0; init < finalprod.length; init++) { for (int tempind = 0; tempind < digits - 1; tempind++) { temparray[tempind][init] = lines[tempind][init]; } } for (int q = 0; q < digits - 1; q++) { // Append necessary zeros to each line array in // lines at beginning. for (int zeroind = digits - q - 1; zeroind >= 0; zeroind--) { lines[q][finalprod.length - 1 - zeroind] = 0; } // Restore the original values to the lines two // dimensional array with the appended zeroes. for (int index = finalprod.length - (digits - q); index >= 0; index--) { lines[q][index] = temparray[q][index + (digits - q - 1)]; } } // Initialize the finalprod array with a value of 0 in each // index. for (int init = 0; init < finalprod.length; init++) { finalprod[init] = 0; } // Sum the lines together after multiplying and // store the result in finalprod (in a similar fashion as // the multiplication algorithm). while (zerocount < 100 && i >= 0) { for (int digsumind = 0; digsumind < digits; digsumind++) { // Get the sum across all the lines at each index. digsum += lines[digsumind][i]; } // Store the value of the sum modulo 10 plus the // sum carryover value, then take the modulo 10 of // the whole expression. Similarly to the multiplication // algorithm, this will ensure that a single digit will // be stored in each index no matter how large the sum // is (between 0 - 18). finalprod[i] = (byte) ((digsum % 10 + sumcarry) % 10); // The sum carryover will simply be the tens digit of // the sum plus the previous sum carryover. sumcarry = (digsum + sumcarry) / 10; // Check if all that remains in the array are leading // zeroes. Zerocount will increment by 1 every time 4 // consecutive zeroes are found. A boolean zerook keeps // track of whether four consecutive zeroes are being // found. Only then will zerocount increment. for (int digsumind = 0; digsumind < digits; digsumind++) { if (i > 2 && lines[digsumind][i] == 0 && lines[digsumind][i - 1] == 0 && lines[digsumind][i - 2] == 0 && lines[digsumind][i - 3] == 0) { zerook = true; } else { zerook = false; } } if (zerook) { zerocount++; } if (!zerook) { zerocount = 0; } // Shift the array index down by one for the next // iteration. i--; // Reset values. zerook = false; digsum = 0; } // Reset values. sumcarry = 0; zerocount = 0; i = finalprod.length - 1; } else { // Execute single-line multiplication if the current factor // has // only one digit. This algorithm is identical to the one // used // in my PE #16 solution. while (zerocount < 100 && i >= 0) { digprod = finalprod[i] * curprime; finalprod[i] = (byte) ((digprod % 10 + carryover) % 10); carryover = (digprod + carryover) / 10; if (i > 2 && finalprod[i] == 0 && finalprod[i - 1] == 0 && finalprod[i - 2] == 0 && finalprod[i - 3] == 0) { zerocount++; } i--; } carryover = 0; zerocount = 0; i = finalprod.length - 1; } } // Reset values. digits = 0; digarray.clear(); } // ---CALCULATE SUM OF DIGITS--- int finalsum = 0; List<Byte> finalprodarray = new ArrayList<Byte>(); System.out.println(x + "! = "); System.out.println(); // ---PRINT OUTPUT - THE FACTORIAL CALCULATION RESULT, THE SUM OF THE // DIGITS, // THE NUMBER OF DIGITS AND THE NUMBER OF TRAILING ZEROES--- for (int a = finalprod.length - 1; a >= 0; a--) { finalsum += finalprod[a]; finalprodarray.add(finalprod[a]); } Collections.reverse(finalprodarray); while (finalprodarray.get(0) == 0 && finalprodarray.get(1) == 0) { finalprodarray.remove(0); } finalprodarray.remove(0); // Put trailing zeroes at the end of the finalprodarray. for (int b = 0; b < trailzeros; b++) { finalprodarray.add(finalprodarray.size(), (byte) 0); } // Print x! int charcount = 0; for (int b = 0; b < finalprodarray.size(); b++) { if (charcount == 44) { System.out.println(); charcount = 0; } System.out.print(finalprodarray.get(b)); charcount++; } // Print the sum of the digits, the number of digits and the number of // trailing zeroes. System.out.println(); System.out.println(); System.out.println("The sum of the digits in " + x + "! = " + finalsum); System.out.println(); System.out.println("The number of digits in " + x + "! is " + finalprodarray.size() + " digits"); System.out.println(); System.out.println("The number of trailing zeros in " + x + "! is " + trailzeros); } }

# Runtime Complexity

The worst case complexity of the algorithm for calculating x! is: , as this solution can be considered a slightly better implementation of the naïve approach. Later on, I will be discussing a much more optimized version of this algorithm which will implement Peter Borwein’s trick to calculating factorials and exponentiation by squaring. With Borwein’s trick, the algorithm’s complexity would be reduced to .

# Wrapping Up

In summary, this program should take in user input, namely any arbitrary integer below 2^{31}-1, calculate its factorial and return the answer including the sum of the digits, the number of digits and the number of trailing zeroes. Hopefully you enjoyed this post, as I must now bid you adieu. ‘Till next time!

Hi,

Good idea!

But with the way you do it the runtime is still O(n^2 log n).

You may take a look at Peter Luschny’s page at http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

Did I give you the link to Peter Borweins paper?

Oh, and

pleaseuse separate functions for sieve, multiplication, and exponentiation it does a lot of good to the legibility of your code such that others can read it more easily.And from many painful experiences I can tell you that one of these “others” are you, too! Just wait enough time and do enough different stuff in the meantime and suddenly you’ll find yourself mumbling to yourself: “Who the hell wrote that bunch of random characters and called it a program? I wrote it, really? What the…!”

Went through it, many times and all I got was a lousy t-shirt 😉

PS: your blog ate my comment at the other posting without comment. Is there a special reason for that? (Too many links, wrong HTML or too much of it or some-such?)

LikeLike

Hello Cristoph,

Thanks for your reply. Actually I’m familiar with Peter Luschny and have read about his fast factorial functions, especially the factorial prime swing. Very cool stuff, and I could probably implement some of those ideas eventually. Thankfully he has a java version of it as well.

OK looks like I really botched that runtime evaluation. I figured it would be pretty similar to my exponentiation algorithm, since the idea is similar with the addition of those multi-digit handling bits. Could you explain exactly to me how you arrived at ?

Actually I haven’t implemented a sieve function, so I thought it would be just fine to stick in to the main void. I get what your saying, I certainly could chunk it up into many functions. Is it painful to read though? Even with the comments?

Huh? It appears fine to me, try checking it out again. I even replied to it. The thing is, I set up my blog so that it asks me to moderate comments, so that I can leave out any spam. This is something that I think you may find as a useful feature.

LikeLike

Hi,

He does—in my opinion!— some overcomplicated things without good explanations (also: please check his license if he has any, I can’t remember if I saw anything in this direction there). But you should look at his implementation of binary splitting although most examples for the binary splitting technique

arethe factorial, so just look around until you find something simple and readable.Binary splitting has a small overhead and starts to win at very low numbers (my cutoff for the C version is at 1700! and for the JavaScript version at 500!, should be somewhere in the middle for Java) and is also very easy to implement.

That is the runtime of the naïve algorithm.

It is even be worse in reality, have you checked it by just running against the naïve algorithm?

The basic idea is sound: use the prime factorization of the factorial which can be done fast. But then you do simple exponentiation which is slow and ruins the whole thing. Using exponentiation by squaring will give you some advantage (the complexity analysis is quite complicated, let me point you to Peter Borwein’s “On the Complexity of Calculating Factorials”. A preprint is freely available).

An implementation in C of Borwein’s algorithm can be found at http://en.literateprograms.org/Factorials_with_prime_factorization_%28C%29.

Some tips and hints:

The multiplication of the small primes should be done with binary splitting.

All primes larger than or equal n/2 have an exponent of one, you can do it at the end and on its own, just remember to multiply that primorial with the result.

You already skip trailing zeros, so nothing to mention here.

I see that Java has a build-in BitSet, you should use it for your prime-sieve. I vaguely remember tha Rosetta code…yes, her it is: http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Java I would use the sieve directly instead of a LinkedList to get the primes (#position in bitset is the prime) and put them in a simple integer array because you need them only linearly.

It is not necessary for small ranges but it is not a bad idea to safe half of the memory by ignoring even numbers (but don’t forget that 2

isa prime! 😉 ) ignoring all multiples of three will also safe a good amount, but five is probably not worth the hassle any-more.Painful? Of course not. If you want code that hurts visit thedailywtf.com. But be warned: it’s not for the faint of heart! 😉

No, it is just unnecessarily hard to read. It will also be hard to maintain when it grows.

The code here is meant to show an implementation of your idea and also instead of pseudo-code. That means it must be clear and easy to follow. That is not always possible. Assembler listings for example are hard to follow, they need a different representation, e.g.: some pseudo-code. Java on the other side can easily be written with legibility in mind and there is rarely a reason not to do so..

So I would suggest to part the whole thing into the following functions:

– a multiplication algorithm for the arbitrary precision number

– ditto for squaring

– ditto for exponentiation (the O(log n) algorithm!)

– a prime-sieve with the functions previous_prime, next_prime and prime_pi (number of primes) although you’ll need only next_prime.

– a function to factor the factorial

– a function for the primorial implemented with the binary splitting algorithm

– a function for small factorials implemented with the binary splitting algorithm (you can build one for both, the primorial and the factorial but it gets unnecessary complicated, hence error prone)

The things left for the main function are organisation and the loop over the exponents (and all the things I forgot to mention 😉 ), that’s all.

It should be possible to implement over one weekend. Feel free to ask if you get stuck.

That isn’t it, that works well—it shows the comment together with a line on top that says something in the line of “Your comment awaits moderation”.

Such things are not rare and I developed the habit to save my comments locally before clicking “send”, that means I can simply try again which I’ll just do.

LikeLike

Will do!

Are you saying my algorithm is slower or the naïve one? Actually my algorithm is a Big Integer implementation of the naïve one, if we’re talking straight up multiplication without any fancy optimizations. This was enough to get a solution to the Project Euler problem I described fairly quickly (a few milliseconds).

I actually haven’t implemented a real sieve, but I will look into that BitSet implementation of the Sieve of Eratosthenes. Anyways getting the prime factorization is not the issue as you mentioned, but the incredibly slow exponentiation algorithm. You have given me a lot of good ideas already, so I will take a look into all of them one by one, and make sure I understand them before implementing them. I may not get all this done any time soon, as school is starting in just over a week, but I really do appreciate your active interest and willingness to help. 🙂

LikeLike

Nope, didn’t work.

It might have to do somthing with too many links, please check what you set it to. How many did I…ah, I had seven links in it, that might have triggered the silent dumping.

LikeLike

Yeah that is probably why, I have the max links set to 4. I’ll change it and get back to you.

LikeLike

Hi,

Yes, albeit only by a constant.

Using the fast exponentiation algorithm would make it already faster. But the factorization has a large overhead, using a method with binary splitting between the naïve approach and Borwein’s trick is recommended.

“Good enough” solutions are for the time when you make money with it and when you need one yesterday. It is not the correct approach as long as you are still learning the basics.

Holy sh… I start to sound like my parents! *shivers*

Sorry for that.

OK, I understand 😉

Than go and have some fun in the last week of your summer holidays!

I think I have to

~~cut~~shear the front-lawn instead *sigh*LikeLike

Hello,

OK I will definitely implement those optimizations and perhaps use the exponentiation by squaring algorithm.

The approach that I used was considered “correct” by most members of the Project Euler community. You see, after reading about what people had to say about the problem, it seemed that anything was considered supremely better than using a built in BigInteger library (or someone else’s for that matter). Even coming up with this with little to no programming experience was a big triumph for me. I think most people would agree, as most are too lazy to go to the trouble of doing something as complicated as this. But nevertheless, optimizing it and making it better is certainly the next step.

Oh it’s not really about having fun, I’ve been doing that all summer :), it’s more of the fact that I have a summer internship to complete!

Anyways the challenge isn’t over, it’s only begun if anything. Although I will be posting about different Project Euler problems in the meantime, as I would like to cover as many topics as possible on this blog!

LikeLike

Hi,

Project Euler was named after Leonhard Euler as far as I know?

The method I used for the quote that follows this sentence is known as “quote mining” and frowned upon.

From the Project Euler page right at the top:

Sorry, don’t hit me, I just couldn’t resist 😉

I haven’t read it before but I was quite sure that “build your own” was a condition? It wouldn’t make much sense to use the build-in tools of your language of choice, would it? Well, it could but that is a different game and it is called “code golf”.

No, from the written intention of the Project Euler it was clear that building a biginteger library, albeit rudimentary (just multiplication) was the targeted solution.

You went even further by trying to use the simplicity of factoring factorials to make it faster!

But because you made me look at it I found some of the problems quite interesting. You don’t need to write a program for everything (#24 for example can be done analytically).

#25 is better. You can do it brute force (by matrix exponentiation) of course but I do not know if you can do it analytically. Quite interesting.

#34 is bit mean, there are only 4 factorions and there is an upper bound you can come up with analytically so you need to do both to find all of them.

#500 is a funny one, although I had expected something with “500!!!” in the question.

The three exclamation marks indicate the triple-factorial:

This can be made general by way of Euler’s Gamma function.

Proof is available.

I was in no way and form trying to belittle you! I, too, started at zero once and even if the internet creates the impression that many of the older people seem to have forgotten those times, I did not and I apologize.

Ouch!

Thanks!

I have chosen JavaScript and C for my project because the first one runs in every browser and the second one has LibTomMath, a Public Domain BigInt library in plain C. Both languages have a wide distribution, a very wide one.

What about Java? How widespread is its use in schools? Would it make sense to add it to my project?

Would you do it?

Do they pay something, at least? No?

All work, no fun, and no paycheck, too?

Yepp, that’ll prepare you well for adulthood.

And now that I’m starting to get a bit too cynical for other peoples taste I’ll stop and click on “Post Comment”.

LikeLike

Yes indeed! A true genius of a mathematician he was, although it would have been cool too if it was called Project Turing. 🙂

I don’t mean to shoot you down here ;), but clearly that’s been taken out of context. An efficient and elegant solution is desirable, but this is Project Euler’s main criteria which deems a solution efficient:

My solution meets that rule quite well, as it was able to solve the problem in 50 or so milliseconds. I understand that mathematics and some insightful modifications/changes would help make my solution more efficient/elegant, but I’ve already been trying to improve it since day one of solving the problem. I’ve put in hundreds of hours on this specific application (all the algorithms in total), so you can see there’s been a lot of effort put in. Also my parents think I’m crazy for spending so much time on this! XD

Why would I? I am a civilized human being after all! (I realize this isn’t saying much) 😛

Actually, you’d be surprised how lazy people are. If you skimmed through the solution forum for the problem (only accessible after solving that particular problem), you’d see about 95% are implementations of a native BigInteger library or something of the sort. Also, take a look at this, somebody dedicated to solving project Euler problems:

http://www.mathblog.dk/project-euler-16/

You’ll see his solution was a trivial implementation of the C# BigInteger library.

Java is probably the most popular language in the world. Source: http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html

My high school didn’t offer any real computer science course, but I’ve spoken to a few others who have said they learned Java first in their computer science course. I enjoy programming in it quite a lot, it meets my needs and I have little to no complaints. Then again you’re asking someone with two years of programming experience. Well I don’t think it’s the best language for BigInteger libraries (it’s very verbose) from what people are saying, and seen as how you already have a good grounding in the languages you’ve used, I honestly don’t think it would add much value. But then again, I don’t really know. Would I do it? You mean convert your projects to Java? How much will you pay me? 🙂

LikeLike

Hi,

And what’s about Emmy Noether, Sophie Germain, Ada Lovelace, Sofia Kovalevskaya, all from the long list at https://en.wikipedia.org/wiki/List_of_female_mathematicians and from https://en.wikipedia.org/wiki/Women_in_computing, and all I have forgotten?

And the women I named my project after, Joyce Currie Little (http://www.women.cs.cmu.edu/ada/Resources/Women/#Joyce%20CurrieLittle) isn’t even on any of these lists.

Yes, that’s why I added the note that I ripped it out of context together with the proper nomenclature 😉

And if you really were unfamiliar with the expression “quote mining”: feel lucky. People that use that trick seriously are to be avoided at all costs or to be blunt: run for your live.

Although it is not sure if Richelieu said it, it is a good example of why quote-mining is not the finest way to win an argument.

Hmmm…

That sounds really slow.

If you have a current Firefox at hand you might try the following snippet:

It was the simplest I could come up with. It runs in about 6ms on my machine which might count as modest, and has probably about the same speed as yours. But the speed of JavaScript depends heavily on the engine, a different browser might be able to do it faster (node.js v0.10.25 does 100! in 2ms and with 10000! the difference is 110 seconds to 2 seconds) or fails completely and is much slower.

But I didn’t meant it to be a benchmark. This snippet has been carefully crafted to do its job and nothing more. More so: you cannot optimize it without rewriting the whole thing or at least large parts of it with one exception:

The snippet runs over the whole array n +1 times and does n log n small multiplications, so the simplest way to optimize it is to shorten the array by skipping multiples of ten. You need an extra function to get the multiplicity of the prime factor five (which is admittedly fast) and in the outer loop a test if

`iter`

is a multiple of ten to be able to act accordingly (divide by ten until you have a single digit). It is a small overhead and may gain you a little bit even with 100!, I haven’t tested it.You cannot do it with larger digits without a large rewrite.

You cannot do it with binary splitting without an even larger rewrite.

But if you take it apart and use individual functions for every such part you would have a multiplication function which you can expand to use bigger limbs, a prime sieve, and a good integer exponentiation function.

This would allow you without much hassle to use a naïve algorithm for the smallest factorials, binary splitting for the medium sized factorials, Borwein’s trick for the really large ones, and you get fast primorials, too, as a by-product.

All of these functions are useful and will come handy at some point in the future.

The function above on the other side is a single-use snippet to be run once and disposed after.

But I, as a regular reader of thedailywtf, am very aware of the fact that you can overdo it, not everything needs to be expandable at all cost. The Unix mantra “Do only one thing but do it good” is not the worst suggestion, you do not need to make a jack of all trades device out of every single one-line shell script.

No, I’m not, have seen too much *sigh*

So let me ask Google what the people did:

Found a discussion at XKCD (http://forums.xkcd.com/viewtopic.php?f=17&t=15795) where they tried the same as I did: to find the sum without computing the actual factorial; one in C that is similar to my snippet, although a bit rough at http://www.programminglogic.com/solution-to-problem-20-on-project-euler/ ; one in a manner that could get them an entry at thedailywtf at http://joerichard.net/java/euler-project/euler-project-problem-20-solution-648/ but with the rest: all use the build-in biginteger functions, that’s right.

Looking at the graph it seems that Java is slowly but steadily on a decline, things like C are stable, Perl is rubbing the ground, and he pike of Objective-C is caused by IOs. VB-Net is on a slow but steady rise? Hoo, creepy! 😉

You can find a bit more information at http://langpop.com/ and http://redmonk.com/sogrady/2015/07/01/language-rankings-6-15/ has a bit more text. A scientific approach is at http://arxiv.org/pdf/1409.0252. IEEE’s costs money but ITWorld has an excerpt at http://www.itworld.com/article/2951877/development/the-top-programming-languages-of-2015.html

Aaand finally a list that is based on no data at all, just gut instinct: http://mashable.com/2015/01/18/programming-languages-2015/

No, I asked someone of your age. I honestly don’t know what they teach in school now.

I could ask my niece but my sister sends her kids to a Waldorf school (Rudolf Steiner school). It is not as bad in Germany as it is in other places but still. I don’t even know if they get any IT-lessons offered at all.

I did it with JavaScript 😉

OK, it is not very fast but it is usable.

It’s only the one project called Little (a full programming language) and it is not a simple conversion but a proper rewrite.

It is a free Open Source project. The only thing one could do is to post at Kickstarter and pass the hat.

The only thing I wanted to do in the far future is to write a book on how I did it but I doubt that I would sell it. Knowledge should be freely available.

LikeLike

Sure, I never said anything against women in computing. I’ve just been intrigued with the life of Alan Turing for a very long time, and he’s certainly one who should be honored for his efforts. I know there are others who also deserve the praise which they haven’t received, but hopefully there will be some group dedicated to honoring them.

Right, but why do so at all? The whole point of Project Euler is to encourage one to foster an interest in mathematics and computer science and have fun learning at the same time. Sure I’m paraphrasing, but Project Euler is certainly meant to be more of a leisure than an examination preparation/homework website. So there is no dictatorial hand proclaiming that everybody must come up with the most efficient, most powerful algorithm in order to gain the satisfaction of having achieved something. I am getting a little off track here, but the thing is I actually want to improve and learn all the advanced mathematics techniques/algorithm optimizations I could implement, it just takes time. As it is, I’m doing this for fun, a productive kind of fun, something that I hope will benefit me in my career.

So you do understand some French, hmm? 🙂

Actually that was directly from my app. The reason why it’s a little slower in the GUI is because I have the standard out printStream rerouted to the JTextPane, so that all the system.out.println output is seen in that result text box. This creates a little bit more overhead than anticipated. Testing the algorithm out directly in the console produces a result below 20 ms. It doesn’t scale too badly though, the difference should be roughly constant no matter how large the calculation is.

I will run the snippet when I have time, as I don’t know of a quick way of getting it to run. I tried to implement Stirling’s approximation in an early prototype of my app to see if I could give the user a better estimate of how many digits would be in the result, but unfortunately there is no easy way of extending this to very large factorials (that I know of) other than making your own BigInteger logarithm function or using Java’s BigInteger library (grumble).

From what I’ve understood from your snippet, it seems like you are calculating the factorial in the Int8Array? I still haven’t seen an implementation of the way that you mentioned of getting the sum without computing the factorial. Is there a mathematical proof you can point me to with the result stating that the aforementioned can be accomplished by simply summing the digits of its prime factors/factors? I’m intrigued, but still skeptical about this.

Nevertheless, it seems like Java won’t be going away anytime soon, as it is still being used almost everywhere.

I thought you were addressing the question to me? So you also asked someone else in pre-university?

It wasn’t really a serious question, as I figured it would be an open source project. Well, I don’t know about you, but if I’m having to spend long hours on a computer developing something useful, I would like some tangible compensation in return.

LikeLike

Hi,

It is 2015 now and just saying nothing against women is still not enough. We need to support them actively.

And there it goes, my hard-earned reputation as an old chauvi 😉

Oh, yes!

But will it happen in our lifetime? We had an apology by then PM Gordon Brown in 2009 and a pardon by your Queen in 2013. That’s all. Alan Turing died in 1954.

We

dohave the Turing Award, which many see as the equivalent of the Nobel Prize for IT.A painful combination of a bit too much coffee, a swollen prostate and the TV-news in the background (for the local weather-report ) where some politician-I-will-not-name used quote-mining to make the opposition look bad, criminally bad.

The caffeine overdose made me find the words but the latter two made me rant a bit about the people who use it for more serious things than just a bad joke. I am sorry if that irritated you too much.

Only rudimentary. I worked internationally (well, mainly Europe but “internationally” sounds so much better 😉 ) for several decades, so I had to learn the basics of French, Spanish, Dutch (I live close to the border), a bit of Italian, and even some Japanese (spoken only, of course). All that is a long time ago but If I ask Google and get an answer in one of the above languages (except Japanese 😉 ) I’m still able (well, mostly) to get the information I want.

And I cannot say that I have a large talent for languages, quite the contrary.

Ah, error in benchmarking, can happen.

The 50ms were a really high value for your code, about a magnitude more than I could explain. So I wrote that snippet to find the runtime for the straightforward solution for my machine (assuming sufficient similarity in horse power). That gave results around 6ms, doubling it for all of the overhead gave 12ms but if you say now that the corrected benchmark gave <20ms, well, that's inside the error bars.

But such a large difference—a whole magnitude!—between node.js (even an older version!) and Firefox? Who would have thought.

Assuming a desktop (key short-cuts are for the PC, for Apple replace “ctrl” with “command”):

Firefox (a recent one):

Copy the code (with ctrl+c , just highlighting it with the mouse might not work)

Open the scratchpad (shift+F4)

Paste the Code into it (ctrl+v, pasting with the mouse might not work)

Open the browser-console (ctrl+shift+j )

Go back to the scratchpad and press ctrl+r

The result should come up in the browser-console window.

Firefox on Android may be different

Firefox on iOS? Well, they say they’re working on it ( https://support.mozilla.org/en-US/questions/1062886 )

Works up to 10^14 (for IEEE 754 doubles, the Java standard type). Not enough?

You can make use of the equalities

to get more.

You could also use “double-double” (http://www.fractalforums.com/programming/%28java%29-double-double-library-for-128-bit-precision/ based on http://web.mit.edu/tabbott/Public/quaddouble-debian/qd-2.3.4-old/docs/qd.pdf) but it is complicated and you have to write your own functions (exp, log, sqrt, ceil, and so on).

Not impossible but you would spend more than just a single weekend with it 😉

Yes, why?

Ah, no, that snippet has nothing to do with my hypothesis.

And if the folks at XKCD (they are not just anybodies!) have a hard time to come up with something, anything in short time… 😉

But truth is: my todo list is way longer than my arm, I don’t even need my reading glasses to decipher the last point on it.

Currently in work is a derivation with proof for the maximum of the terms in Spouge’s approximation. I do have an upper bound which is enough for programming (it is not that far off, not much waste) but nobody did it the full way and somebody has to do it and if I am that somebody…

It is definitely more than just summing up the digits of the factors 😉

But as I said, it is probably as fast/slow as the actual computing of the factorial.

I think, no, I’m pretty sure, that the solution, if it exists, is hidden deeply in group-theory.

It is a very interesting problem and I won’t drop it, so be patient.

I have my doubts about the “almost everywhere” but it is sufficiently wide-spread, so I will think about using it for my Little project (yes, I looove bad puns! 😉 ).

Uhmm…?

Oh, I see, thank you for pointing that out!

At least not as embarrassing as my than/then error! 😉

Is “No, I wanted to ask someone of your age” followed by something in the line of “so I took the liberty to ask you” better? Awkward? So-so? Completely off?

If you “have to” spend your time for it, than: yes, that needs more compensation than a lukewarm handshake and a pat on the head, without further discussions.

There is also one other, often forgotten thing you should think about: we use a lot of software that has been written and gets maintained by people who do it all for free[1]. We should give something back.

[1] more and more companies pay programmers now, mostly for the maintaining but also for new features and I don’t think they do it out of pure altruism.

LikeLike

Reblogged this on PotentialMind.

LikeLike