7
\$\begingroup\$

I was reading this website. It mentioned how to use matrix exponents to find the n-th Fibonacci number in O(log n) time. I tried implementing it Python along with a fast exponent algorithm.

I'm not sure if this algorithm I have really is O(log n) time, and would also appreciate feedback on code style / practices. Here's my code:

def fibonnaci(n):
    # find the nth fibonacci number using matrices and exponents
    # (1 1) ** n = (F(n+1) F(n)  )
    # (1 0)        (F(n)   F(n-1))
    return matrix_2x2_exponent([[1, 1], [1, 0]], n)[1][1]  # formula is incorrect I think



def multiply_matrices(matrix1, matrix2):
    result = [[0, 0],
              [0, 0]]

    for i in range(len(matrix1)):
        for j in range(len(matrix2[0])):
            for k in range(len(matrix2)):
                result[i][j] += matrix1[i][k] * matrix2[k][j]

    return result


def matrix_2x2_exponent(matrix, n):
    # brings a matrix of dimensions 2x2 to the power n, using recursive algorithm
    if n == 0:
        return [[1, 0],
                [0, 1]]  # identity matrix

    result = matrix_2x2_exponent(matrix, n // 2)

    if n % 2 == 1:
        return multiply_matrices(multiply_matrices(result, result), [[1, 1], [1, 0]])
    else:
        return multiply_matrices(result, result)

print(fibonnaci(int(input())))
\$\endgroup\$
4
  • 2
    \$\begingroup\$ The operation complexity is logarithmic, if you count "multiply two matrices" as one operation. But arithmetic is slower with bigger integers. The time complexity measured in e.g. nanoseconds is linear. This is actually the best any algorithm can do, because the $n$th Fibonacci number takes $O(n)$ space. \$\endgroup\$
    – J.G.
    Feb 20 at 17:53
  • \$\begingroup\$ Indeed, the nth Fibonacci number is exponential in n (see Binet's formula), so the log of the nth Fibonacci number is linear in n. Therefore, even to print out the digits of the answer, will take linear time, not logarithmic time. (The time it takes to print out the answer is proportional to n, not to log(n).) \$\endgroup\$
    – mathmandan
    Feb 20 at 19:24
  • \$\begingroup\$ However, actually I do not see that the running time is linear in n, either. When I try the OP's code with n equal to 10**6, 2*10**6, 4*10**6, 8*10**6, 16*10**6, ..., it appears to me that doubling n corresponds pretty much exactly to tripling the runtime. So it does not seem linear to me...maybe more like O(n^{log_2(3)}), which would be roughly O(n^1.58). \$\endgroup\$
    – mathmandan
    Feb 20 at 19:27
  • 1
    \$\begingroup\$ @mathmandan If you want to review the question, I encourage you to use the answer box for this. \$\endgroup\$
    – Mast
    Feb 20 at 21:16

3 Answers 3

7
\$\begingroup\$

Use the Correct Function Name

fibonnaci should be fibonacci.

Perhaps you intentionally wanted this spelling, but I will work on the assumption that it was unintentional.

Use Type Hinting, At Least on Public Functions:

def fibonacci(n):

becomes:

def fibonacci(n: int) -> int:

Prefer Docstrings to Comments When Describing What a Function Does

For example, you have a perfectly good comment at the start of function fibonacci that would be better as a docstring:

def fibonacci(n):
    """Find the nth fibonacci number using matrices and exponents
    (1 1) ** n = (F(n+1) F(n)  )
    (1 0)        (F(n)   F(n-1))"""

Add Tests and Make the Module Importable

There are various testing frameworks you can use. But for simplicity you could use simple assertions.

Currently, if this module were imported it would execute print(fibonacci(int(input()))), which is not what you would want. I would place such code within a if __name__ == '__main__': block and I would add a prompt so somebody running this as a script would know what is expected. For example:

def _tests() -> None:
    assert fibonacci(1) == 0
    assert fibonacci(2) == 1
    assert fibonacci(3) == 1
    assert fibonacci(4) == 2
    assert fibonacci(301) == 222232244629420445529739893461909967206666939096499764990979600

if __name__ == '__main__':
    # First run some tests:
    _tests()

    while True:
        try:
            print(fibonacci(int(input('Enter integer n to compute the nth Fibonacci number: '))))
        except Exception as e:
            #print(e)
            pass
        else:
            break

The name of anything at global scope that you do not want imported if the user executes from fibonacci import * (I am assuming the source is in module fibonacci.py), should start with an underscore character. Alternatively, you can specify a __all__ list at the end the source naming those globals that should be imported. For example:

__all__ = ['fibonacci']

The advantage of using names that start with an underscore is that it also suggests that the global should be considered "private".

Putting It All Together

def fibonacci(n):
    """Find the nth Fibonacci number using matrices and exponents
    (1 1) ** n = (F(n+1) F(n)  )
    (1 0)        (F(n)   F(n-1))"""

    return matrix_2x2_exponent([[1, 1], [1, 0]], n)[1][1]


def multiply_matrices(matrix1, matrix2):
    result = [[0, 0],
              [0, 0]]

    for i in range(len(matrix1)):
        for j in range(len(matrix2[0])):
            for k in range(len(matrix2)):
                result[i][j] += matrix1[i][k] * matrix2[k][j]

    return result



def matrix_2x2_exponent(matrix, n):
    """brings a matrix of dimensions 2x2 to the power n, using recursive algorithm"""
    if n == 0:
        return [[1, 0],
                [0, 1]]  # identity matrix

    result = matrix_2x2_exponent(matrix, n // 2)

    if n % 2 == 1:
        return multiply_matrices(multiply_matrices(result, result), [[1, 1], [1, 0]])
    else:
        return multiply_matrices(result, result)

def _tests() -> None:
    assert fibonacci(1) == 0
    assert fibonacci(2) == 1
    assert fibonacci(3) == 1
    assert fibonacci(4) == 2
    assert fibonacci(301) == 222232244629420445529739893461909967206666939096499764990979600

if __name__ == '__main__':
    # First run some tests:
    _tests()

    while True:
        try:
            print(fibonacci(int(input('Enter integer n to compute the nth Fibonacci number: '))))
        except Exception as e:
            #print(e)
            pass
        else:
            break
\$\endgroup\$
0
6
\$\begingroup\$

Regarding running time of this algorithm:

The nth Fibonacci number is exponential in n (see Binet's formula), so the log of the nth Fibonacci number is linear in n. Therefore, even to print out the digits of the answer, will take linear time, not logarithmic time. (The time it takes to print out the answer is proportional to n, not to log(n).)

And, it's not only printing out the numbers that's the issue--the internal calculations also take longer when the numbers get bigger. Adding two m-digit numbers together can be done in O(m) time: just think of how you would add them by hand. It can't be done any faster than that, because presumably you have to at least read the inputs (and print the output).

To multiply two m-digit numbers, the fastest known algorithm (as of February 2024) takes O(m log(m)) time. It obviously can't be done in less than O(m) time, for the same reasons as above.

It is not realistic to assume that these operations can be done in O(1) time. But, that's what you have to assume, in order to say that your algorithm finds the nth Fibonacci number in O(log(n)) time.

Regarding integer types

And yet, people often do assume that arithmetic operations take O(1) time. If you press them on this, they may say that they are using fixed-length integers, like 64-bit integers or something. And yes, if you use 64-bit integers, then arithmetic operations are O(1). But, fixed-length integers would be kind of a ridiculous choice for this context. As someone pointed out in the comments, the nth Fibonacci number is greater than 2^64 once n is bigger than about 94.

So, if you only have to handle 64-bit integers, then here's what you can do instead. Just pre-compute all the Fibonacci numbers up to F_94 (this only takes 94 additions!) and store them as a list. Then all your algorithm has to do is "return the nth entry from the list". That's O(1) in time and space! But assuming we can agree that this solution wouldn't be good enough, you have to make sure that you are not using fixed-length integers. Fortunately, your solution does not have this problem, because one of the very nice things about Python is that it handles arbitrary-length integers natively.

In the comments, someone recommended using the numpy package to do matrix arithmetic; you have to be careful if you do this because numpy will use fixed-length integers by default. In fact, numpy actually does allow matrices of arbitrary-length integers, but you need to set the dtype to object. (See this StackOverflow answer.) Of course, then you are sacrificing a lot of the speed and performance of numpy.

\$\endgroup\$
1
  • \$\begingroup\$ Note that when talking about "digits" for BigInt multiply, those aren't decimal digits. With an efficient BigInt library, those would be base 2^64 digits on 64-bit CPUs, i.e. working with 64-bit "limbs" of a BigInt. For CPython, it's base 2^30 even on 64-bit CPUs. (See my answer on Did the 2019 discovery of O(N log(N)) multiplication have a practical outcome? re: "digits", and also others re: the fact that O(m log m) multiply is a galactic algorithm; for numbers that fit on real computers, Toom Cook or Karatsuba are still best.) \$\endgroup\$ Feb 22 at 0:29
5
\$\begingroup\$

Use libraries

Is there any reason for why you don't use numpy or a similar linear algebra library? These libraries not only make your implementation much easier, but also can speed up your code quite a bit. With numpy your code could be reduced to just a few lines of Python code.

Call Stack

For large enough n (admittedly, very, very large n), the recursion might fill up your call stack and the program will throw a runtime error. Consider using a loop to avoid this. A loop is also typically a little bit faster than recursion* because of less context switches.

*except for tail recursion, which usually can be optimized away by the compiler/interpreter.

Runtime

In every loop, you decrease n by its half. Consequently, after about log n iterations, it'll meet the terminal condition n == 0. There are no other loops dependent on n, so this algorithm should indeed be O(log n).

\$\endgroup\$
2
  • 4
    \$\begingroup\$ Regarding tail recursion, Python does not have tail-call optimization, so tail recursion still has all the same issues that deep recursion of other types does. \$\endgroup\$ Feb 20 at 14:33
  • 1
    \$\begingroup\$ @Green绿色, thanks for the response. The reason why I don't use numpy is that I am preparing for competitive coding competitions, and I would rather not rely on a non-built-in library in case those happen to be prohibited. \$\endgroup\$ Feb 20 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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