I know power of 2 can be implemented using << operator. What about power of 10? Like 10^5? Is there any way faster than pow(10,5) in C++? It is a pretty straight-forward computation by hand. But seems not easy for computers due to binary representation of the numbers... Let us assume I am only interested in integer powers, 10^n, where n is an integer.
pow() is function to get the power of a number, but we have to use #include<math. h> in c/c++ to use that pow() function. then two numbers are passed. Example – pow(4 , 2); Then we will get the result as 4^2, which is 16.
In this program, we have used the pow() function to calculate the power of a number. Notice that we have included the cmath header file in order to use the pow() function. We take the base and exponent from the user. We then use the pow() function to calculate the power.
Something like this:
int quick_pow10(int n) { static int pow10[10] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; return pow10[n]; }
Obviously, can do the same thing for long long
.
This should be several times faster than any competing method. However, it is quite limited if you have lots of bases (although the number of values goes down quite dramatically with larger bases), so if there isn't a huge number of combinations, it's still doable.
As a comparison:
#include <iostream> #include <cstdlib> #include <cmath> static int quick_pow10(int n) { static int pow10[10] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; return pow10[n]; } static int integer_pow(int x, int n) { int r = 1; while (n--) r *= x; return r; } static int opt_int_pow(int n) { int r = 1; const int x = 10; while (n) { if (n & 1) { r *= x; n--; } else { r *= x * x; n -= 2; } } return r; } int main(int argc, char **argv) { long long sum = 0; int n = strtol(argv[1], 0, 0); const long outer_loops = 1000000000; if (argv[2][0] == 'a') { for(long i = 0; i < outer_loops / n; i++) { for(int j = 1; j < n+1; j++) { sum += quick_pow10(n); } } } if (argv[2][0] == 'b') { for(long i = 0; i < outer_loops / n; i++) { for(int j = 1; j < n+1; j++) { sum += integer_pow(10,n); } } } if (argv[2][0] == 'c') { for(long i = 0; i < outer_loops / n; i++) { for(int j = 1; j < n+1; j++) { sum += opt_int_pow(n); } } } std::cout << "sum=" << sum << std::endl; return 0; }
Compiled with g++ 4.6.3, using -Wall -O2 -std=c++0x
, gives the following results:
$ g++ -Wall -O2 -std=c++0x pow.cpp $ time ./a.out 8 a sum=100000000000000000 real 0m0.124s user 0m0.119s sys 0m0.004s $ time ./a.out 8 b sum=100000000000000000 real 0m7.502s user 0m7.482s sys 0m0.003s $ time ./a.out 8 c sum=100000000000000000 real 0m6.098s user 0m6.077s sys 0m0.002s
(I did have an option for using pow
as well, but it took 1m22.56s when I first tried it, so I removed it when I decided to have optimised loop variant)
There are certainly ways to compute integral powers of 10 faster than using std::pow()
! The first realization is that pow(x, n)
can be implemented in O(log n) time. The next realization is that pow(x, 10)
is the same as (x << 3) * (x << 1)
. Of course, the compiler knows the latter, i.e., when you are multiplying an integer by the integer constant 10, the compiler will do whatever is fastest to multiply by 10. Based on these two rules it is easy to create fast computations, even if x
is a big integer type.
In case you are interested in games like this:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With