FastPow

You’ll learn about fast multiplication in C++

Fast Power

In the c++ world, there is no need for creating a new functions like std::pow.

The value of aⁿ can be obtained using a property:

if the power n is even, then calculate (a^n/2)² else calculate a^n/2 * a^{n/2 + 1}

We can code this easily using a recursive function:

 uint64_t fast_pow(uint32_t a, uint32_t b)
 {
    if(b == 0)
        return 1;
    if(b % 2 == 0)
        return fast_pow(a, b/2) * fast_pow(a, b/2);
    else
        return fast_pow(a, b/2) * fast_pow(a, b/2 + 1);
 }

A simple solution, but not as efficient, being a O(n) solution

 uint64_t slow_pow(uint32_t a, uint32_t b)
 {
     int res = 1;
     for(int i = 0;i < b;i++)
        res *= a;
     return res;
 }