Skip to main content
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 2k2^k Fibonacci numbers. Let’s see how it works.

Starting with the quint()

We start with just one value using quint():
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
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:
For example:
fib_index() does the opposite. It gives us the index of a Fibonacci value:
So:
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.
The idea is simple. First, we find the index of x:
Then we flip bit bit_idx of that index:
This gives us the index of the Fibonacci value to pair with x. For example, when bit_idx = 2, we pair the indices:
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 2k2^k Fibonacci values. For our example, k = 3, so we want:
interfere() takes the pairs that we want to combine. The left side of each pair is selected by:
This selects the Fibonacci values whose index has bit bit_idx equal to 0. We start with index 0, which has the value:
At the first step, we have:
The debugger now shows:
Debugger showing 2 and 13 with equal amplitudes
At the second step, we have:
Debugger showing 2, 13, 5 and 34 with equal amplitudes
Finally, we generate all 8 Fibonacci values:
The debugger shows all eight values with equal amplitudes:
Debugger showing the final Fibonacci amplitudes
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:
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!