Daily Coding Problem: Computing Big Exponentials

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 to the code! If you have problems following along, I highly recommend you 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 a 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 by 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.

https://gist.github.com/NicolaM94/46ea02bb912e31dfc8baca955b93f7bd?embedable=true#file-multiplication-go

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 of conversion to do, however:

• first off, we use the variable integer to save our converted digit from the string (with stringedInt[n]-'0' we convert the rune value to its UNICODE counterpart and then convert it to int )
• then, with the fmt.Sprintf function, we convert the result back to a string and add it to the front of the out variable, which will be our result.

Let’s take a moment at the math done here: the possible digits we are multiplying are 0,1,2,3,4,5,6,7,8,9, but the results somehow repeat 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 lines 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 1,000 times to calculate the wall of text corresponding to 2¹⁰⁰⁰! Let’s write the simple code:

https://gist.github.com/NicolaM94/e13f77c1664abf3dcfa3cd0367ebcb01?embedable=true#file-wrap-go

In our main function, we define the final variable, initially equal to "1" . Then we loop over for 1000 times to update the result. Now, since the problem wants 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 problems, 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 the time complexity of this algorithm. The first part of the code runs a number of times 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, share a Ko-fi. Here’s my page!

As always, thank you so much for reading.

Nicola

Also published here.