> ## Documentation Index
> Fetch the complete documentation index at: https://docs.rhymeq.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Fibonacci Series: Generating Fibonacci Values with Interference

In the previous tutorial, we used **phase** to mark Fibonacci values.

This time, we use **pairing and interference** to generate Fibonacci values. We want to generate the first $2^k$ Fibonacci numbers.

Let's see how it works.

## Starting with the `quint()`

We start with just one value using `quint()`:

```python theme={null}
u = quint(2)
```

So `u` contains the value `2` with amplitude `1`, which is the starting value of our Fibonacci series.

The debugger shows:

![Debugger showing value 2 with amplitude 1](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/fibonacci_magnitude_1.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=2e3768e4214cc1137aa454e40e96605a)

Now we want to generate more Fibonacci values.

To do this, we need to work with both the **values and their indices**.

## Finding Fibonacci numbers

First, we need two small Python functions to work with Fibonacci numbers and their positions.

`fib()` gives us the Fibonacci number at a given index:

```python theme={null}
def fib(i: int) -> int:
    a, b = 2, 3

    for _ in range(i):
        a, b = b, a + b

    return a
```

For example:

```text theme={null}
fib(0) → 2
fib(1) → 3
fib(2) → 5
fib(3) → 8
```

`fib_index()` does the opposite. It gives us the index of a Fibonacci value:

```python theme={null}
def fib_index(x: int) -> int:
    a, b = 2, 3
    i = 0

    while a < x:
        a, b = b, a + b
        i += 1

    return i
```

So:

```text theme={null}
fib_index(2) → 0
fib_index(3) → 1
fib_index(5) → 2
fib_index(8) → 3
```

This lets us move between a Fibonacci **value** and its **index**.

## Pairing Fibonacci values

Now comes the interesting part.

We want to pair a Fibonacci number `x` with the Fibonacci number whose index is obtained by flipping bit `bit_idx` of its index.

```python theme={null}
def pair(x: int, bit_idx: int) -> int:
    i = fib_index(x)
    j = i ^ (1 << bit_idx)

    return fib(j)
```

The idea is simple.

First, we find the index of `x`:

```python theme={null}
i = fib_index(x)
```

Then we flip bit `bit_idx` of that index:

```python theme={null}
j = i ^ (1 << bit_idx)
```

This gives us the index of the Fibonacci value to pair with `x`.

For example, when `bit_idx = 2`, we pair the indices:

```text theme={null}
0 ↔ 4
1 ↔ 5
2 ↔ 6
3 ↔ 7
```

The corresponding Fibonacci values are paired in the same way.

So `pair()` is our rule for saying: *"This Fibonacci value is paired with that Fibonacci value."*

## Building more Fibonacci values

Now we use these pairs with `interfere()`.

We want to generate the first $2^k$ Fibonacci values. For our example, `k = 3`, so we want:

```
2, 3, 5, 8, 13, 21, 34, 55
```

```python theme={null}
k = 3

u = quint(2)

for bit_idx in reversed(range(k)):
    u.interfere(
        lambda x: pair(x, bit_idx),
        lambda x: (fib_index(x) & (1 << bit_idx)) == 0
    )
```

`interfere()` takes the pairs that we want to combine.

The **left side of each pair** is selected by:

```python theme={null}
(fib_index(x) & (1 << bit_idx)) == 0
```

This selects the Fibonacci values whose index has bit `bit_idx` equal to `0`.

We start with index `0`, which has the value:

```text theme={null}
2
```

At the first step, we have:

```text theme={null}
2, 13
```

The debugger now shows:

![Debugger showing 2 and 13 with equal amplitudes](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/fibonacci_magnitude_pair.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=070502800b47f208fb90d7f1902c7717)

At the second step, we have:

```
2, 5, 13, 34
```

![Debugger showing 2, 13, 5 and 34 with equal amplitudes](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/fibonacci_magnitude_2.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=178256623c357af75e9f73fcf161a3e3)

Finally, we generate all 8 Fibonacci values:

```
2, 3, 5, 8, 13, 21, 34, 55
```

The debugger shows all eight values with equal amplitudes:

![Debugger showing the final Fibonacci amplitudes](https://mintcdn.com/rhyme-q/JlURJlNdnA85HOaP/images/basic-tutorials/fibonacci_magnitude_final.png?fit=max\&auto=format\&n=JlURJlNdnA85HOaP\&q=85\&s=acfbc0a94b8a79ee2103f1a481474e96)

So step by step, pairing and interference **build the Fibonacci sequence**.

## What happened?

We started with the first Fibonacci value, `2`. Then, for the later values, we:

```text theme={null}
    work with Fibonacci values
                ↓
        find their indices
                ↓
    pair the Fibonacci values
                ↓
        interfere the pairs
                ↓
    build the Fibonacci sequence
```

The result is a collection of Fibonacci values with equal amplitudes.

So this time, instead of using phase to **mark** Fibonacci numbers, we use **pairing and interference to generate the Fibonacci sequence**.

**That's how we generate the Fibonacci sequence using interference in Rhyme!**


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.