This article will be a guideline for optimization, not a full-detailed article. I encourage you to search for all terms mentioned yourself. Secondly, I am using Java and Wolfram Mathematica, however you can implement mentioned solutions in any language that you like.
This article will focus on 3 main topics:
Optimization for 2^x
Instead of using Math.pow(2, x)
, you can use 1l << x
.
Square-and-multiply, and others!
Square-and-multiply algorithm is used to compute x^n where x belongs to integers, and n belongs to positive integers. There is a cool video by ComputerPhile explaining the algorithm. However
in this article I'll just drop the implementation in java. Also, you can use the optimized implementations laid out
by GeeksForGeeks.
There's also the Barrett Reduction for computing x mod n. You can also use these keywords in ChatGPT or Google Bard to know alternatives and search on your own!
Expression Simplification
The simplification of any function is always correlated with higher computational performance. However, for the specific cases of 2^x and a^b where a is an integer and b is a positive integer, leaving these terms might be actually faster than resorting to other simplified forms. You can also use expansion series if you want a specific percision and at the same time faster computation. In Wolfram Mathematica, you can use Series to generate a power series for a certain function. You can use (and combine) the previous tips to evaluate each term of the series optimally.
Bonus Tips
First : When you bruteforce an equation for solutions (eg. integer) with n variables, you are bruteforcing for n-1 variables, the last one can be checked by direct evaluation. (also check tip 4)
Second : For bruteforcing the integer solutions, if you have logarithm of base x, the integer solutions have logarithm input of x^n where n is an integer. You do not have to check for every integer in log_x() to get an integer result.
Third : When evaluating a^2 + b^2 = c, the maximum values for a and b iterator variables are the absolute maximum when all other terms are zero. For example: maximum value of a is sqrt(c) and same for maximum value for b.
Fourth : When evaluating a^2 + b^2 = c, where c is already known. b will equal sqrt(c - a^2), now you only loop for variable a.
Fifth : This article has a lot of neat mathematical optimization tips on the problem of the sum of two squares. Make sure to check it out!