Here is an awesome way to demonstrate divide and conquer algorithm performing exponentiation. Naive exponentiation algorithms x^{n} would perform n-1 multiplications as *n x n … x n-1*. This has an algorithmic complexity of *O(n)* which of course scales poorly for any significantly large number. This is not even including the overhead of performing integer multiplication beyond CPUs capacity is slower than staying within the CPU integer range. Now, do that n times and you have a problem.

Logarithmic performance *O(log n)* is one of the best common algorithmic complexities there is (outside of constant complexity of course, which is rare). One can achieve calculating power by utilizing the power of logarithms, which are clearly apparent in divide and conquer problem solutions.

Logarithms grow very slow compared to number of inputs, though for a calculating a power of say n^{1000000}, with the naive algorithm, you’d have to perform 999,999 multiplications. With a logarithmic complexity algorithm this drops to log_{2}1000000 = ceil(19.93) = 20 steps. 20 steps with a few extra operations for step compared to 1million multiplications.

Here is an example of both exponentiation algorithms, the logarithmic complexity and linear complexity (called naive), as well as built in python *pow()* function. Both our logarithmic *power* function and python’s built in one perform the same, where the naive linear function starts to truly deteriorate once any reasonable number is used as the exponent.

_**Note**: this function is recursive though you can run out of stack space for very large exponents (you can also easily reimplement it as recursion). On a system with a 1024 stack limit, this would mean your exponent would have to be above 2^{1024} or

17976931348623159077293051907890247336179769789423065727343008 11577326758055009631327084773224075360211201138798713933576587 89768814416622492847430639474124377767893424865485276302219601 24609411945308295208500576883815068234246288147391311054082723 7163350510684586298239947245938479716304835356329624224137216

before you run out of stack space._

Here is a benchmarked python implementation. The relevant algorithm part is highlighted.

#!/usr/bin/env python import math import time import sys def power(b, e): """logarithmic divide/conquer algorithm""" if e == 0: return 1 x = power(b, math.floor(e/2)) if e % 2 == 0: return pow(x, 2) else: return b * pow(x, 2) def naive_power(b, e): """linear power algorithm""" x = b; for i in range(1, e): x *= b return x def perform(name, base, exp, pfunc): print("%s: %d^%d: %d" % (name, base, exp, pfunc(base, exp))) if __name__ == '__main__': if len(sys.argv) != 3: sys.exit("You must provide a base and an exponent. (Usage: exp.py base exp)") base = int(sys.argv[1]) exp = int(sys.argv[2]) for func in (power, naive_power, pow): print("Benchmarking %s..." % func.__name__) bench = [] for i in range(0,5): start = time.time() ans = func(base, exp) end = time.time() bench.append(end-start) print("\tCalculated in: %s" % min(bench)) ]]>

Running above to calculate 2^{200000}

$ python exp.py 2 200000

Benchmarking power…

Calculated in: 0.0042099952697753906

Benchmarking naive_power…

Calculated in: 6.078423023223877

Benchmarking pow…

Calculated in: 0.0041148662567138672

Hmmm, both *pow() (python’s built in power)* and *power() (logarithmic complexity)* calculated the power in 4 millis (above is in seconds) and our *naive_power()* function calculates the same result in 6 seconds.

I tried running the script to calculate 2^{1000000}, which calculated using logarithmic functions in 25 milliseconds and I killed the *naive_power()* calculation after a few minutes of impatiently waiting for it to complete.

Power to the logarithms!!! ðŸ™‚

Tags: algorithms, python

Excellent and very interesting! Thank you

why do you mod 2 in your power function?