<jupyter_start><jupyter_text>Fibonacci numbers by matrix multiplicationSource: <NAME>, <NAME>, <NAME>, *Algorithms*, 2008Complexity: $O(\log{}n)$<jupyter_code>import numpy as np
from visualization.fibonacci_matrices import visualize
@visualize
def fib_matrix(n):
    X = np.array([[0, 1],
                  [1, 1]])
    F01 = np.array([[0],
                    [1]])

    X_to_n = X
    for _ in range(n):
        X_to_n = X_to_n @ X
    return (X_to_n @ F01)[0,0]
fib_matrix(20)<jupyter_output>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
{'fraction_non_alphanumeric': 0.15397631133671744, 'fraction_numerical': 0.10998307952622674, 'mean_word_length': 2.9731543624161074, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '613644', 'license': 'Apache-2.0', 'n_tokens_mistral': 300, 'n_tokens_neox': 234, 'n_words': 60, 'path': 'mathematics/fibonacci_matrices.ipynb', 'repo_name': 'rafalpotempa/fantastic-algorithms', 'size': '611'}