4
\$\begingroup\$

I have 2 functions to get the n-th fibonacci number. The 1st one uses recursive calls to calculate the power(M, n), while the 2nd function uses iterative approach for power(M, n). Theoretically (at least what I think), they should have the same speed O(log n), but why when I run both, the 2nd one is much slower than the 1st one?

def fib_1(n):
    from numpy import matrix
    def power(F, n):
        if n == 0 or n == 1: return matrix('1 1; 1 0', object)

        F = power(F, n >> 1) # n // 2
        F = F * F
        if n % 2 == 0:
            return F
        if n % 2 != 0:
            return F * matrix('1 1; 1 0', object)

    F = matrix('1 1; 1 0', object)
    F = power(F, abs(n)-1)
    return F[0,0] if n > 0 else int((-1)**(n+1)) * F[0,0]
def fib_2(n):
    from numpy import matrix
    def power(F, n):
        M = matrix('1 1; 1 0', object)
        while n > 0:
            if n & 1 == 1:
                M = F * M
            n = n >> 1 # n = n // 2
            F = F * F
        return M

    F = matrix('1 1; 1 0', object)
    F = power(F, abs(n)-2)
    return F[0,0] if n > 0 else int((-1)**(n+1)) * F[0,0]
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Please share how you profile. In my setup, fib_2 is much faster. \$\endgroup\$ – vnp Apr 22 '20 at 4:30
  • \$\begingroup\$ @vnp, for small numbers, fib_2 is totally faster, but for big n (like n=2,000,000), fib_2 is much slower. I just use a normal start_time = time.perf_counter() and end_time to see the time they took to complete calculating a big n fib \$\endgroup\$ – NepNep Apr 22 '20 at 4:46
6
\$\begingroup\$

Before we got any further, a word of warning. The complexity is only valid in a particular computational model.

The complexity of these algorithms is \$O(\log n)\$ only if the addition takes constant time. For large \$n\$ it is not the case.

Fibonacci numbers grow exponentially with n. It means that the number of bits grows linearly. Now we are in the Turing machine realm. The last addition itself takes \$O(n)\$, which is way more than \$\log n\$.

The overall complexity should be \$O(n\log{n})\$ in both cases. Why the two exhibit different performance?

The likely reason is that there is a subtle difference between them. fib_1 maintains just one matrix, F. fib_2 maintains two of them, F, M, and must do roughly twice as many reallocations as fib_1 does. The matrices contain huge numbers, and I expect that the memory management time dominates. Yet another factor the computational model shall now consider.

\$\endgroup\$
3
\$\begingroup\$

Before some more detailed performance analysis, it's important to note some low-hanging fruit in terms of code quality.

Global imports

Unless you have a really good reason, from numpy import matrix should be at the top of the file in global scope.

Deprecated library classes

matrix is deprecated. Use ndarray instead.

Do not reconstruct constants

matrix('1 1; 1 0', object) should not be parsed and reconstructed every time. Save it outside of function scope. If you need it to be modified later, modify a copy. Copying will be cheaper than parsing.

Redundant branches

In this:

    if n % 2 == 0:
        return F
    if n % 2 != 0:
        return F * matrix('1 1; 1 0', object)

The second if is not necessary because its condition is guaranteed to be True.

Expression simplification

int((-1)**(n+1))

It's probable that n is already an integer based on how your function is set up (though documentation and/or type hints would help to clarify this). The fact that a float is produced when the exponent is negative is probably due to Python assuming that it effectively needs to do a division, which is reasonable. All things considered, rather than doing the exponentiation - which is common in pure math, because of simplicity of analysis - you should consider doing the "piece-wise" thing instead. Rather than

return F[0,0] if n > 0 else int((-1)**(n+1)) * F[0,0]

consider

y = F[0,0]
if n <= 0 and n%2 == 0:
    y = -y
return y
\$\endgroup\$
7
  • \$\begingroup\$ On the last point, I don't know why but if the result is negative (-1), it's cast to -1.0. That's why I had int cast there \$\endgroup\$ – NepNep Apr 22 '20 at 2:58
  • 2
    \$\begingroup\$ @Reinderien When the exponent is integer, there are no roots involved. For negative integers it is the division. \$\endgroup\$ – vnp Apr 22 '20 at 4:10
  • 1
    \$\begingroup\$ Yes, that. Negative exponent is "one over" not "root". \$\endgroup\$ – slepic Apr 22 '20 at 4:42
  • 1
    \$\begingroup\$ return F[0,0] * (1 if (n > 0 or n%2) else -1) keeps it in 1 line, and is clearer than both in my opinion \$\endgroup\$ – Maarten Fabré Apr 22 '20 at 9:49
  • 1
    \$\begingroup\$ @MaartenFabré Re. the ternary-golfed statement - you're entitled to your opinion; I think the if is clearer. \$\endgroup\$ – Reinderien Apr 22 '20 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.