Huge factorials!

Digit by digit (Daily Coding Problem 20)

Exclamation Mark Doodle Vectors by Vecteezy — Amira Home Channel

Welcome everyone with another problem to solve! Today we have some nice math to work with: factorials! We are going to build an algorithm to calculate huge factorials: we’ll see how fast they grow, how big they get and, finally, we will calculate the sum of their digits to solve our problem.

Today’s problems is given by ProjectEuler.net : a super cool website to look at if you are in the mood of some head scratching! There are more than 800 math and coding problems to solve and a vast archive of discussions about them. It is literally the perfect tool to train your math skills and learn something new. Go check it out and try to solve your challenges too!

Enough talking: let’s see what today’s problem has to offer.

n! means n * (n-1) * … * 3 * 2 * 1.

For example, 10! = 10 * 9 * … * 3 * 2 * 1 = 3628800, and the sum of the digits of 10! is 3+6+2+8+8+0+0 = 27.

Find the sum of the digits in the number 100!

As we anticipated before, what we are asked to do is to calculate the digits of a number, in particular the number 100! = 100 * 99 * … * 3 * 2 * 1 : pretty easy...right? Well, not quite!

Let’s put down some basics then and see how to manage such a big product.

Factorials!

The particular notation stated by the problem is a famous concept in math, known as factorial. The factorial of a number is simply the product of all the natural numbers up until that number. It’s usually expressed with the expression mark after the number (n!) or, in symbols, as

So, for instance, the factorial of the number 10, written as 10!, is 10! = 10 * 9 * … * 3 * 2 * 1 = 3628800.

What’s really cool about factorials is how fast they grow: since we are used to deal with Big-O complexity notation, here’s a chart comparing some function’s growth rates. It’s pretty clear that the factorial growth is the worst: for an instance size of less than 10, the number of operations executed by a factorial growing function exceeds (by a lot) a thousand operations!

Credits to http://bigocheatsheet.com/

One simple way to see this behavior is to try with a calculator: if you still have your scientific calculator from the high school, like the famous Casio or Sharpe, you can easily see that you can’t calculate over 69!: it gives you back a math error. This is because the number cannot be stored by the memory of the calculator, for it gets too big to address.

Some more recent calculators try to go over that bond: for example, the calculator of my phone (a Redmi 7) can calculate up to 170!, giving out the result with the exponential notation (7.25741562e³⁰⁶). If you try with 171! though, it just spits a disappointing ∞ … which is really not the case.

It’s also really cool to look at how many digits the result of a factorial has:

• the number 100! has 158 digits
• the number 500! has 1135 digits
• the number 1000! has 2568 digits
• the number 5000! has 16326 digits

The number 10000! has 35660 digits: it is so big that I could not fit it in a single image. Here’s a GIF with all the digits:

But wait a minute: didn’t we just say that we could not calculate over the factorial of 70? There’s a trick to do so, that we’ll see in a moment. But to understand how we can calculate arbitrarily big factorials, we first must go back to the basics of multiplication.

How we multiply

When you were kids, chances are that your teacher at school taught you to multiply in column with a process similar to this:

On the left side, a simple multiplication between a three digit number and a one digit number, in which each digit from the right to the left gets multiplied by 9. At each multiplication, if the result is greater than 9, the remainder is written on top of the next digit (right to left) and added on the next step of the process; on the right side, a multiplication of a three digit number and a two digit number, where there are two “temporary” results in between of the process. Here, we previously write a 0 as the right most digit in the second temporary result, and sum those to get the final result.

It’s really basic math, but this process works because we can decompose the starting number in units, tens, hundreds and so on and multiply each of those by the second number. After that we just sum each individual partial result to obtain the final result. Something like this:

That is precisely what we are going to do, on a much bigger scale. We are going to deal with very big numbers, so this process needs to be modified a bit to work with the integers memory limits built in the language we are using (Python in this case). To be true, Python 2 used to have a size limit in it’s int type, but since Python 3 replaced it the limit was somehow removed. Other languages do have it though, so we build this approach to keep the algorithm portable to those languages too. Also, it will come in handy to multiply from the right to the left.

Coding the process

Basically we first convert our number to a string and reverse it. After that, we multiply each digit for the second number, add the previous remainder, and store the result and the new remainder for the next calculation. Let’s see the process step by step first:

With this process, ideally, the only two limits we have on our products are:

• the RAM limit: when the number we are trying to multiply gets too big, we’ll be thrown a MemoryError, for the interpreter has not enough memory to allocate the calculated number. Every modern computer has 8, 16 or 32Gb of RAM tough, so you should have plenty of memory to allocate before reaching the limit.
• the time limit: as we’ll see better later, the time needed to complete the process grows pretty quickly. Even if it’s not a real limit (one can always wait right?), the more the number grows, the more time you’ll need to wait for a result.

Our code will replicate this process step by step, returning the result. Here’s the code:

The function multiplication accepts two arguments: n , the number to multiply as string, and m , the other one as integer. First off, we reverse n and create two other variables:

• newNumber , which will hold our new number digit by digit
• remainder , which will keep track of the remainder of each operation. The remainder is initially equal to 0.

We loop over the reversed number and, at each step:

1. We calculate the result of the digit we are on times the second number m and add the remainder.
2. We add the last digit of result to the newNumber ;
3. If there is a remainder (when result > 9 ), we update the variable remainder with the new one. The remainder is composed by the digits of resultexcept the last one. If there is no remainder, we set remainder back to 0. This is really important to avoid bringing on remainders of previous multiplications!

We keep looping for each digit of reversed and finally, if there is a remainder after the last multiplication, we add it to newNumber . After that we simply return our newNumber.

Calculating the factorial

Now that we have a method to multiply numbers of the size we want, we can apply it to calculate our factorials! Here’s the code:

It’s just a wrapper really: all it does is set a variable out , initially equal to the string “1” and then range from 1 to n (n+1 really, for Python’s range stops at n-1) to apply our multiplication function, each time updating out with the new result.

For example, here’s the result of 500!:

1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Summing up

Since our problem requires to calculate the sum of the digits of 100!, we also need a function to sum all the digits, but it’s quite simple to build: you can do it directly in your main function. Here’s the main:

As in the other article where the problem was also given by ProjectEuler.net, I won’t give out the solution: you need to build this by yourself at least, if you want to know it! ProjectEuler.net is really a lovely project: besides presenting math riddles and problems, their main focus is to provide a tool to start learning, thinking and reasoning about math. And I love that: they are so committed that publishing results and guides for their problems is actually forbidden (this is one of the first 100 problem, so I understand it is permitted). Given this, I don’t feel it would be fair to just give out the solution to copy paste and get the achievement.

Have a nice coding guys! 😎

Time and complexity

It’s not that hard to evaluate the time complexity of this algorithm: the biggest amount of time is spent inside the multiplication function. Here, besides allocating some variables and modifying their values, the slowest part is the for loop, which will run len(n) times, depending on the length of the number we are multiplying. It is linear, since there are no nested loops to deal with.

When we wrap this function in hugeFactorial though, we must run that function n times: so the time complexity becomes quadratic, leaving us with O(n²) t.c..

Finally, summing up the digits it’s another linear time algorithm, but it’s only invoked after the factorial is calculated: for this reason, it won’t add any complexity, leaving us with a total complexity of O(n²).

Talking about execution time, here’s the time taken by my machine (AMD Ryzen 5, avg. ck. 2700 MHz) to calculate some results:

With a simple regression, even if the data is clearly not enough, we can see that our prediction of a O(n²) time complexity holds true: the time taken actually grows like a parabola.

x = n! ; y = time (seconds); r coeff. = 0.99978; a = 0.95808; b = -0.00248; c = 0

I did not have much time to go over 10000!, so if you try it out please let me know your results!

Conclusions

Here it is, this was my tackle! In all likelihood, there are better approaches to this kind of problem but, as always, I wanted to share my try with you guys.

What do you think about this? Do you have a better solution or idea? Let me know in the comments!

I hope you liked the article and found something interesting in it! If so, please leave a like or share it with someone who could appreciate this kind of problems: that would really make my day!

Thanks for reading, as always

Nicola