Exponentiation, speed and complexity.Published:
Question you often hear today is do we *really* need to know how functions and methods are implemented in the programming languages we use, or this is just the thing from the past? Majority (if not all -- please, correct me if I'm wrong) of the modern languages that are commonly used today on the web/mobile have these mathematical operations inbuild, so unless you are really curios about "how stuff works", there is no need to know that, right?
I'm a graphic engineer and self-thought computer enthusiast, using programming languages to make stuff and have recently decided to strengthen my computer science basis. So I came across Introduction to Computer Science and Programming, MIT Open Course Ware lectures, where in lecture 8 (Complexity: Log, Linear, Quadratic, Exponential Algorithms) Prof. Eric Grimson and Prof. John Guttag also discuss about exponentiation and show examples how to implement it.
There are at least three ways:
def exp1(a, b): ans = 1 while (b > 0): ans *= a b -= 1 return ans
whilemethod to loop over exponents.
It runs in linear time: .
That means it takes n steps to go through the loop.
def exp2(a, b): if b == 1: return a else: return a*exp2(a, b-1)
def exp3(a, b): if b == 1: return a if (b%2)*2 == b: return exp3(a*a, b/2) else: return a*exp3(a, b-1)
If b is even, then a to the b is the same as squared a to the b over 2. In this one step, the problem is reduced in half! This is far better than the previous two examples. Its order of growth is logarithmic, log b: .
Let's make a simple comparison of these first two examples versus the third one:
|Notation||n = 10||n = 100||n = 1000|
The method of exponentiation, represented above is (usualy) a built-in method, but is there any need to think about that or in this direction?
I would say absolutely. Speed, performance, lower bandwidth traffic, they all sum up in an overall better user experience.
What do you think? Do you ask yourself if you can make something run faster, or smoother?
Do you know how exponentiation is implemented in your favourite programming language?