Computing big exponentials
Daily Coding Problem 23
Welcome back with another problem to solve! Today’s problem will focus on calculating big exponentials from scratch. This problem is similar to the problem seen in the Daily Coding Problem number 20, so this one will be pretty short. We’ll fast forward a bit over the explanations and direct our attention straight on the code! If you have problems following along, I highly recommend you to check Daily Coding Problem number 20 for a much deeper explanation, since the concepts involved are the same.
This problem is provided by the wonderful website Project Euler, an awesome platform to test your math, logic and coding skills on more than 800 problems. Go check it out: you will not be disappointed!
We’ll be using Go for this program: headache time! :D
The problem
Let’s take a look at the problem:
2¹⁵ = 32768 and the sum of its digits is 3+2+7+6+8=26.
What is the sum of the digits of the number 2¹⁰⁰⁰?
The problem is really simple: we need to calculate 2¹⁰⁰⁰ and sum its digits to give it as result. Simple, isn’t it? Well…
Exponentials
To give out some simple basics, an exponential number is simply the repetition of that same number a certain number of times. For example, writing 4³ means calculating 4*4*4. What’s really cool about powers (which is also what causes us this problem) is how fast they grow: not the fastest, but still pretty fast.
The function we are interested in is the green one: you can easily see how fast it grows. Even if the power function x³ grows faster initially, the exponentiation of 2 catches up pretty quickly. As in the previous article, try with your calculator: you should not be able to calculate over 2³³², which is 8.749002899x10⁹⁹.
And yet, with a little bit of reasoning and a simple program, we can calculate that 2³³³ is
17498005798264095394980017816940970922825355447145699491406164851279623993595007385788105416184430592
and with the same approach, 2⁵⁰⁰ is
3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589376
Cool right? Let’s see how it’s done then!
The approach
If there’s one thing computers are good at, it’s repeating the same job multiple times really fast. We’ll exploit this ability to repeat a simple task many many times to iterate over all the exponents from 1 to the desired one and print out the result. The simple operation we are doing is the multiplication of a certain number with the number 2, to increase the exponent. However, we are doing this multiplying each digit of the starting number by 2: this way we can manage increasingly big numbers simply by multiplying their digits. Let’s write a multiplication function.
As always, let’s explain a bit what’s happening here. We create the multiply
function which takes in two parameters: stringedInt
, the integer we want to multiply, and factor
, the factor we are multiplying it for. After that we define the variable carryover
, which we’ll explain in a moment.
Now we start looping: we loop over the length of stringedInt
and multiply each digit by factor
. We have some type conversion to do, however:
- first off, we use the variable
integer
to save our converted digit from the string (withstringedInt[n]-'0'
we convert the rune value to its UNICODE counterpart and then convert it toint
) - then, with the
fmt.Sprintf
function we convert the result back to string and add it to the front of theout
variable, which will be our result.
Let’s take a moment on the math done here: the possible digits we are multiplying are 0,1,2,3,4,5,6,7,8,9, but results somehow repeats in a certain manner. For example, 2*2 is 4 and 2*7 is 14, so a 4 with a 1 in front of it. The 1 will be our carryover, which will be added to the next multiplication, so to keep just the unit digit we calculate integer % 5 * 2
. If you’re not versed with modulo operations, here are some resources to get an idea about it. After multiplying, we just need to add the carryover that could have been stored from the previous multiplication: integer % 5 * 2 + carryover
.
We must store the carry though: that is done in the next block of code, which evaluates if integer > 4
. This is because for values from 5 to 9 our mudulo will bring us back to the values from 0 to 4, but we need to deal with the carry. We know that the carry can only be 1 at most, so we simply check if integer > 4
: if it is, we have a 1 to carryover and we store it in its variable carryover
.
The final block, from line 12 to 14, simply adds the last carry possibly left from the last multiplication: for example, if the last number multiplied was an 8, out
will now start with a 6, but we have a 1 stored in carryover
. We must add it to the front of out
to have the correct result.
It’s really basic math, to be honest, but describing it textually could make it worse than it is. So here’s a drawn example of the process:
Wrapping up
Now we just need to apply that process a 1000 times to calculate the wall of text corresponding to 2¹⁰⁰⁰! Let’s write the simple code:
In our main
function we define the final
variable, initially equal to "1"
. Then we loop over for a 1000 times to update the result. Now since the problem want the sum of the digits of 2¹⁰⁰⁰, we simply create the variable sum
and loop over final
summing up all the digits.
Also, this same algorithm can be used to calculate every exponential of every number: just change the value in the multiply
call or the n
upper limit in the loop and you’ll get whatever result you want. For example, running
...
for n := 0; n < 500; n++ {
final = multiply(final, 5)
}
...
will calculate 5⁵⁰⁰.
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 Complexity
As always, let’s take a brief moment to discuss about the time complexity of this algorithm. The first part of the code runs a number of time equal to the length of the stringedInt
, which unfortunately will increase at each loop. Then we run the multiplier n
times to reach the nth exponent. So, technically speaking, we’ll have a complexity of O[len(stringedInt)*n]
, which we can generalize with some approximation to O(n²).
Conclusion
Here it is: that’s my solution! I hope you enjoyed following along and reading about this problem. If so, please leave a clap or two: that would make my day!
Also, if you are willing and can contribute to the channel sharing a Ko-fi. Here’s my page!
As always, thank you so much for reading
Nicola