Python - "Fast Exponention Algorithm" performance outperformed by "worse" algorithm

Question

Can anyone explain to me how this code:

def pow1(a, n):
    DP = [None] * (n+1)
    DP[1] = a
    i = [1]
    while not i[-1] == n:
        if(i[-1]*2 <= n):
            DP[i[-1]*2] = DP[i[-1]]*DP[i[-1]]
            i.append(i[-1]+i[-1])
        else:
            missing = n-i[-1]
            low = 0
            high = len(i) - 1
            mid = 0
            while low <= high:

                mid = (high + low) // 2

                if i[mid] < missing:
                    if i[mid+1] > missing:
                        break
                    low = mid + 1

                elif i[mid] > missing:
                    high = mid - 1

                else:
                    break

            DP[i[-1]+i[mid]] = DP[i[-1]]*DP[i[mid]]
            i.append(i[mid]+i[-1])

    return DP[n]

out-performs this code:

def pow2(a,  n):
    res = 1
    while (n > 0):
        if (n & 1):
            res = res * a
        a = a * a
        n >>= 1

    return res

---

Here is how I check them:

a = 34 # just arbitrary 
n = 2487665 # just arbitrary 


starttime = timeit.default_timer()
pow1(a, n)
print("pow1: The time difference is :", (
    timeit.default_timer() - starttime))
starttime = timeit.default_timer()
pow2(a, n)
print("pow2: The time difference is :",
      (timeit.default_timer() - starttime))

This is the result on my MacBook Air m1:

# pow1: The time difference is : 3.71763225
# pow2: The time difference is : 6.091892

As far as I can tell they work very similarly only the first one (pow1) stores all its intermediate results therefore has like O(log(n)) space complexity and then has to find all the required factors(sub-products) to get the final result. So O(log(n)) calculating them all, worst case has to do log(n) binarySearches (again O(log(n)) resulting in a runtime of O( logN*log(logN) ). Where as pow2 essentially never has to search through previous results... so pow2 has Time Complexity: O(logN) and Auxiliary Space: O(1) vs pow1 - Time Complexity: O(logN*logN*logN) and Auxiliary Space: O(logN).

Maybe (probably) I'm missing something essential but I don't see how the algorithm, the hardware (ARM), python or the testing could have this impact.

Also I just realised the space complexity for pow1 is O(n) the way I did it.

Answer 1

Great catch. It's a weakness of while loops that they lead to wasted computations at the bottom of the loop body. Usually it doesn't matter.

Languages like Ada provide an unconditional loop expecting that an internal break (exit in Ada) will be used to leave for this reason.

So fwiw, a cleaner code using this "break in the middle" style would be:

def pow2(a,  n):
    res = 1
    while True:
        if (n & 1):
            res *= a
        n >>= 1
        if n == 0:
            return res
        a *= a

With other algorithms, you might need to guard the loop for the case n = 0. But with this one, that's optional. You could check for that and return 1 explicitly before the loop if desired.

Overall, this avoids a comparison per loop wrt your solution. Maybe with big numbers this is worthwhile.

Answer 2

Okey so I figured it out. In pow2 (which I implemented from cp-algorithms.com but can also be found on geeksforgeeks.org in python) there is a bug.

The problem is this line gets executed one time too many:

    res = 1
    while (n > 0):
        if (n & 1):
            res = res * a
        a = a * a #<--- THIS LINE
        n >>= 1

    return res

that gets called even tough the result has already been calculated, causing the function to do one more unnecessary multiplication, which with big numbers has a big impact. Here would be a very quick fix:

def pow2(a,  n):
    res = 1
    while (n > 0):
        if n & 1:
            res = res * a
            if n == 1:
                return res
        a = a * a
        n >>= 1

    return res

New measurements:

# a:34 n:2487665
# pow1(): The time difference is : 3.749621834
# pow2(): The time difference is : 3.072042833
# a**n: The time difference is : 2.119430791000001