# Ein paar mehr Fibonacci Funktionen in Python


def fib_rec(n):
    assert n > 0
    if n == 1 or n == 2:
        return 1
    return fib_rec(n-1) + fib_rec(n-2)


import functools
@functools.cache
def fib_rec_mem(n):
    assert n > 0
    if n == 1 or n == 2:
        return 1
    return fib_rec_mem(n-1) + fib_rec_mem(n-2)


def fib_tail_rec(n):
    assert n > 0
    def helper(n, acc, prev):
        if n < 1:
            return acc
        return helper(n-1, prev + acc, acc)
    return helper(n, 0, 1)


def fib_iter(n):
    assert n > 0
    steps = [1,1] + [0] * (n-2)
    for i in range(2,n):
        steps[i] = steps[i-1] + steps[i-2]
    return steps[n-1]


def fib_iter_const(n):
    assert n > 0
    a, b = 1, 1
    for i in range(n-2):
        a, b = a + b, a
    return a


# Aufgrund von numerischen Instabilitäten von Gleitkommazahlen
# scheitert diese und die nachfolgenden Implementierungen für Werte ab
# jeweils ≈93 und ≈72.
import numpy as np
def fib_matrix(n):
    assert n > 0
    return np.linalg.matrix_power(np.matrix([[1,1],[1,0]]), n-1)[0,0]


import math
def fib_binet(n):
    assert n > 0
    φ = (1 + math.sqrt(5)) / 2
    ψ = (1 - math.sqrt(5)) / 2
    return math.floor((φ**n - ψ**n) / math.sqrt(5))


import sympy
def fib_binet_sym(n):
    assert n > 0
    from sympy.abc import x
    [ψ, φ] = sympy.solve(x**2 - x - 1, [x])
    return sympy.floor((φ**n - ψ**n) / sympy.sqrt(5))


def fib_rec_linear(n):
    assert n > 0
    if n == 1: return 1
    φ = (1 + math.sqrt(5)) / 2
    return round(φ * fib_rec_linear(n-1))


def fib_iter_linear(n):
    assert n > 0
    φ = (1 + math.sqrt(5)) / 2
    a = 1
    for i in range(n-2):
        a = round(φ * a)
    return a


def fib_comp(n):
    assert n > 0
    def comp(m):
        if m < 0: return 0
        if m == 0: return 1
        return sum(comp(m-i) for i in range(1,n+1,2))
    return comp(n)


import re
def fib_odd_bits(n):
    assert n > 0
    p = re.compile(r"^(((00)*0(11)*1)*((00)*0)|((11)*1(00)*0)*((11)*1))$")
    return sum(bool(p.match(f"{{:0{n}b}}".format(i)))
               for i in range(1<<(n-1)))

from itertools import combinations as combs
def fib_subsets(n):
    assert n > 0
    return sum(min(ss) == len(ss)
               for l in range(1, n+1)
               for ss in combs(range(1,n+1), l))


def fib_bsubsets(n):
    assert n > 0
    pc = int.bit_count
    return sum(0 == (i & ((1<<pc(i))-1)) and 0 != (i & (1<<pc(i)))
               for i in range(1,1<<n+1))


def fib_frac(n):
    assert n > 0
    φ = (1 + math.sqrt(5)) / 2
    return round(φ**(n+1) / (φ + 2))


def fib_frac_sym(n):
    assert n > 0
    φ = (1 + sympy.sqrt(5)) / 2
    return round(float(φ**(n+1) / (φ + 2)))


if __name__ == '__main__':
    # https://oeis.org/A000045
    expected = [
        1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,
        987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025,
        121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578,
        5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155
    ]

    from datetime import datetime
    def test(fn, limit=len(expected)):
        start = datetime.now() # poor man's benchmarking
        all(n == fn(i+1) for (i, n) in enumerate(expected) if i < limit)

        try:
            fn(-1)
            assert False, "Definiert für negative Werte"
        except AssertionError:
            pass

        s = datetime.now() - start
        print(f"{fn.__name__} passt alles für n < {limit} ({s})...")

    test(fib_rec)
    test(fib_rec_mem)
    test(fib_tail_rec)
    test(fib_iter)
    test(fib_iter_const)
    test(fib_matrix)
    test(fib_binet)
    test(fib_binet_sym)
    test(fib_rec_linear)
    test(fib_iter_linear)
    test(fib_comp)
    test(fib_odd_bits)
    test(fib_subsets, limit=25)
    test(fib_bsubsets, limit=25)
    test(fib_frac)
    test(fib_frac_sym)


# $ python3 fib.py
# fib_rec passt alles für n < 40 (0:00:22.716574)...
# fib_rec_mem passt alles für n < 40 (0:00:00.000020)...
# fib_tail_rec passt alles für n < 40 (0:00:00.000061)...
# fib_iter passt alles für n < 40 (0:00:00.000053)...
# fib_iter_const passt alles für n < 40 (0:00:00.000022)...
# fib_matrix passt alles für n < 40 (0:00:00.000684)...
# fib_binet passt alles für n < 40 (0:00:00.000025)...
# fib_binet_sym passt alles für n < 40 (0:00:00.873951)...
# fib_rec_linear passt alles für n < 40 (0:00:00.000006)...
# fib_iter_linear passt alles für n < 40 (0:00:00.000068)...
# fib_comp passt alles für n < 40 (0:12:18.575217)...
# fib_odd_bits passt alles für n < 40 (0:00:00.000159)...
# fib_subsets passt alles für n < 25 (0:00:14.901603)...
# fib_bsubsets passt alles für n < 25 (0:00:10.872632)...
# fib_frac passt alles für n < 40 (0:00:00.000025)...
# fib_frac_sym passt alles für n < 40 (0:00:00.008548)...
#
# $ lscpu
# Architecture:             x86_64
#   CPU op-mode(s):         32-bit, 64-bit
#   Address sizes:          39 bits physical, 48 bits virtual
#   Byte Order:             Little Endian
# CPU(s):                   8
#   On-line CPU(s) list:    0-7
# Vendor ID:                GenuineIntel
#   Model name:             11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
#     CPU family:           6
#     Model:                140
#     Thread(s) per core:   2
#     Core(s) per socket:   4
#     Socket(s):            1
#     Stepping:             1
#     CPU(s) scaling MHz:   19%
#     CPU max MHz:          4200.0000
#     CPU min MHz:          400.0000
# ...
#
# $ python3 --version
# Python 3.12.6