Pure Programmer

## Project: Fast Exponentiation

Fast exponentiation is a process whereby a number can be raised to an integer power in constant time by looking at the binary digits of the power.

For example take 0.913. Since 13 is 11012 or 8+4+1 we have...

0.913 = 0.98+4+1 = 0.98 * 0.94 * 0.91

Notice that the one's bit of 13 corresponds to a factor of 0.91 in the answer. The two's bit would be a factor of 0.92 if the bit were present, which it is not. The four's bit is a factor of 0.94 and the eight's bit is a factor of 0.98. Notice also that each successive factor is the square of the previous factor.

So our fast exponentiation algorithm is to start with a result of 1 and a factor of 0.9 (the base). Then look at the least significant bit of the power and multiply the result by the factor if it is set. Then right shift the power by one bit and multiply the factor by itself. If the new least significant bit of the power is set multiply by the new factor. Continue this process of multiplying the result by the power if the least significant bit of the power is set, shifting the power and squaring the factor until the power becomes zero.

Write a fast exponentiation function that takes a double base and an integer power and then returns basepower using fast exponentiation algorithm above. Include main code to test the function with a range of both positive and negative bases and a range of integer powers.

Output
\$ g++ -std=c++17 FastExponentiation.cpp -o FastExponentiation -lfmt \$ ./FastExponentiation -0.1^0 = 1.0000000000000000 -0.1^1 = -0.1000000000000000 -0.1^2 = 0.0100000000000000 -0.1^3 = -0.0010000000000000 -0.1^4 = 0.0001000000000000 -0.1^5 = -0.0000100000000000 -0.1^6 = 0.0000010000000000 -0.1^7 = -0.0000001000000000 -0.1^8 = 0.0000000100000000 -0.1^9 = -0.0000000010000000 ... 0.9^7 = 0.4782968999999996 0.9^8 = 0.4304672099999996 0.9^9 = 0.3874204889999996 0.9^10 = 0.3486784400999996 0.9^11 = 0.3138105960899996 0.9^12 = 0.2824295364809996 0.9^13 = 0.2541865828328996 0.9^14 = 0.2287679245496096 0.9^15 = 0.2058911320946487 0.9^16 = 0.1853020188851837

Solution