Now, let’s do the same but in a slightly different approach – using square and multiply algorithm. As you probably know from math classes the following formulae are true: <\/p>\n\n\n\n
- 711<\/sup> = 7 10<\/sup> * 7 1<\/sup><\/li>
- 7 10<\/sup> = 7 5<\/sup> * 7 5<\/sup><\/li><\/ul>\n\n\n\n
Having that in mind we can compute the 7 30000<\/sup> as follows (I prepared a simple program that prints to operations for given base and exponent):<\/p>\n\n\n
\n![\"\"](\"https:\/\/baldsolutions.com\/wp-content\/uploads\/2022\/06\/image.png\")
<\/figure>\n<\/div>\n\n\nAs you can see instead of 30000 multiplications we are able to do the same exponentiation in just 20 operations (we can ignore the first line)! I decided not to explain the algorithm in details<\/p>\n\n\n\n
Summary<\/h1>\n\n\n\n
To sum up, the number of operations have a direct impact in terms of program performance. I didn’t explain here the exact algorithm’s steps as I believe that the above image explain the main idea of the algorithm well. I also encourage to read this <\/a>Wikipedia page. Moreover, I’ve got inspired by this<\/a> Computerphile video – I truly recommend this YouTube channel, there are many well-explained and interesting things to learn.<\/p>\n\n\n\n
As always I’ve prepared an example and you can find it on my github<\/a>, project: square-and-multiply<\/a>.<\/p>\n\n\n\n
Have a nice day, bye!<\/p>\n","protected":false},"excerpt":{"rendered":"
Introduction Computing large numbers isn’t usually our day-to-day issue. We use multiplication when it comes to finding out how much of a paint would be…<\/p>\n
- 7 10<\/sup> = 7 5<\/sup> * 7 5<\/sup><\/li><\/ul>\n\n\n\n