fibonacci.py

View source code here on GitHub!

Includes

python.src.lib.fibonacci.fib() → Iterator[int]

This generator goes through the fibonacci sequence

Generating each new element happens in constant time.

python.src.lib.fibonacci.fib_by_3(start_index: int = 0) → Iterator[int]

This generator goes through the fibonacci sequence skipping by 3s. This works because:

F[n] = F[n-1]          + F[n-2]
F[n] = F[n-2] + F[n-3] + F[n-2]
F[n] = 2 * F[n-2]            + F[n-3]
F[n] = 2 * (F[n-3] + F[n-4]) + F[n-3]
F[n] = 3 * F[n-3] + 2 * F[n-4]
F[n] = 3 * F[n-3] + F[n-4] + F[n-5] + F[n-6]
F[n] = 4 * F[n-3]                   + F[n-6]

Generating each new element happens in constant time, and setup takes \(O(n)\) where \(n\) is the given start index.

 1from typing import Iterator
 2
 3from .iters import consume
 4
 5
 6def fib() -> Iterator[int]:
 7    """This generator goes through the fibonacci sequence
 8
 9    Generating each new element happens in constant time."""
10    a, b = 0, 1
11    while True:
12        yield b
13        a, b = b, a + b
14
15
16def fib_by_3(start_index: int = 0) -> Iterator[int]:
17    """This generator goes through the fibonacci sequence skipping by 3s. This works because:
18
19    .. code-block:: python
20
21        F[n] = F[n-1]          + F[n-2]
22        F[n] = F[n-2] + F[n-3] + F[n-2]
23        F[n] = 2 * F[n-2]            + F[n-3]
24        F[n] = 2 * (F[n-3] + F[n-4]) + F[n-3]
25        F[n] = 3 * F[n-3] + 2 * F[n-4]
26        F[n] = 3 * F[n-3] + F[n-4] + F[n-5] + F[n-6]
27        F[n] = 4 * F[n-3]                   + F[n-6]
28
29    Generating each new element happens in constant time, and setup takes :math:`O(n)` where :math:`n` is the given
30    start index."""
31    orig = fib()
32    a = 0
33    consume(orig, start_index)
34    next(orig)  # start + 1
35    next(orig)  # start + 2
36    b = next(orig)  # start + 3
37    del orig
38    yield a
39    while True:
40        yield b
41        a, b = b, a + b * 4

Tags: python-iterator, fibonacci-number