Générateur de Fibonacci

# Fibonacci sequence generators

# 1. Simple iterative approach
def fibonacci(n):
    """Generate first n Fibonacci numbers."""
    if n <= 0: return []
    if n == 1: return [0]
    seq = [0, 1]
    for _ in range(2, n):
        seq.append(seq[-1] + seq[-2])
    return seq

print(fibonacci(10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# 2. Generator (memory efficient for large sequences)
def fib_generator():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

gen = fib_generator()
first_15 = [next(gen) for _ in range(15)]
print(first_15)

# 3. Binet's formula (fast, but loses precision for large n)
import math
def fib_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round(phi**n / math.sqrt(5))

print([fib_binet(i) for i in range(10)])

# 4. Fast matrix exponentiation O(log n)
def matrix_mult(A, B):
    return [
        [A[0][0]*B[0][0] + A[0][1]*B[1][0],
         A[0][0]*B[0][1] + A[0][1]*B[1][1]],
        [A[1][0]*B[0][0] + A[1][1]*B[1][0],
         A[1][0]*B[0][1] + A[1][1]*B[1][1]]
    ]

def matrix_pow(M, n):
    if n == 1: return M
    if n % 2 == 0:
        half = matrix_pow(M, n // 2)
        return matrix_mult(half, half)
    return matrix_mult(M, matrix_pow(M, n - 1))

def fib_fast(n):
    if n == 0: return 0
    M = [[1, 1], [1, 0]]
    return matrix_pow(M, n)[0][1]

print(fib_fast(50))  # 12586269025 (exact, arbitrary precision)