Skip to content

Fibonacci Linear

example_fibonacci_linear

Overall description of this example goes here.

fst(_x: int, f: tuple[int, int]) -> int

Get the first element of a pair.

:param x: A pair containing two integers. :return: The first element of the pair.

Source code in examples/example_fibonacci_linear.py 
11
12
13
14
15
16
17
18
def fst(_x: int, f: tuple[int, int]) -> int:
    """
    Get the first element of a pair.

    :param x: A pair containing two integers.
    :return: The first element of the pair.
    """
    return f[0]

fib_zero_one() -> tuple[int, int]

The pair of Fibonacci numbers at indices 0 and 1.

:return: The pair of Fibonacci numbers at indices 0 and 1.

Source code in examples/example_fibonacci_linear.py 
21
22
23
24
25
26
27
def fib_zero_one() -> tuple[int, int]:
    """
    The pair of Fibonacci numbers at indices 0 and 1.

    :return: The pair of Fibonacci numbers at indices 0 and 1.
    """
    return (0, 1)

fib_next(_y: int, _x: int, f: tuple[int, int]) -> tuple[int, int]

Calculate the pair Fibonacci numbers at a given indices y and y + 1 using the pair of Fibonacci numbers at indices x = y - 1 and y.

:param _y: The indices for which the Fibonacci number is calculated. :param _x: The indices decremented by 1. :param f: The pair of Fibonacci numbers at indices y - 1 and y. :return: The pair of Fibonacci numbers at indices y and y + 1.

Source code in examples/example_fibonacci_linear.py 
30
31
32
33
34
35
36
37
38
39
40
def fib_next(_y: int, _x: int, f: tuple[int, int]) -> tuple[int, int]:
    """
    Calculate the pair Fibonacci numbers at a given indices y and y + 1
    using the pair of Fibonacci numbers at indices x = y - 1 and y.

    :param _y: The indices for which the Fibonacci number is calculated.
    :param _x: The indices decremented by 1.
    :param f: The pair of Fibonacci numbers at indices y - 1 and y.
    :return: The pair of Fibonacci numbers at indices y and y + 1.
    """
    return (f[1], f[0] + f[1])

main()

Source code in examples/example_fibonacci_linear.py 
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def main():
    component_specifications = {
        fst: DSL()
        .parameter("x", "int")
        .argument("f", Constructor("fibs") & Constructor("at", Var("x")))
        .suffix(Constructor("fib") & Constructor("at", Var("x"))),
        fib_zero_one: DSL().suffix(Constructor("fibs") & Constructor("at", Literal(0, "int"))),
        fib_next: DSL()
        .parameter("y", "int")
        .parameter("x", "int", lambda vs: [vs["y"] - 1])
        .argument("f", Constructor("fibs") & Constructor("at", Var("x")))
        .suffix(Constructor("fibs") & Constructor("at", Var("y"))),
    }

    # range of relevant indices for Fibonacci numbers
    parameter_space = {"int": frozenset(range(6000))}

    # CoSy instance with the component specifications and parameter space
    cosy = CoSy(component_specifications, parameter_space)

    # query for the Fibonacci number at index 5000
    query = Constructor("fib") & Constructor("at", Literal(5000, "int"))

    # solve the query and print the only solution
    print("5000th Fibonacci number:", next(iter(cosy.solve(query))))