Cairo’s Relative Jump Exercise

What happens in the following code? (you can start by running it and looking at the memory; note that you will need the –no_end flag)

func main():
    [fp + 1] = 2; ap++
    [fp] = 5201798304953761792; ap++
    jmp rel -1
end

Solution

The exercise presents another infinity loop so we not only need to use the –no_end flag but the –steps=16 flag too.

After compiling and executing the exercise code we get the following output:

$ cairo-compile exercise.cairo --output exercise.json
$ cairo-run --program=exercise.json \
--print_memory --relocate_prints --no_end --steps=16
>>>
Addr  Value
-----------
⋮
1     5190257839498559489
2     2
3     5190257839498559488
4     5201798304953761792
5     74168662805676031
6     -1
7     18
8     18
9     5201798304953761792
10    2
11    4
12    8
13    16
14    32
15    64
16    128
17    256

The highlighted output shows that the program is adding an instruction to memory (as opposed to letting the compiler add the instructions for you) and an integer using the fp pointer. The relative jump is re-executing the added instruction while advancing the ap counter and the result is a progression where each number added to memory is the previous number multiplied by 2.

Instructions might require the use of 1 or 2 field elements (memory cells) and based on the previous output it is not clear if the added integer is part of the instruction or the starting value of the progression. To verify this, we can change the integer to 3 and check if the progression changes to multiples of this number.

func main():
    [fp + 1] = 3; ap++
    [fp] = 5201798304953761792; ap++
    jmp rel -1
end

Recompiling and executing the modified code gives us the following result:

Addr  Value
-----------
⋮
1     5190257839498559489
2     3
3     5190257839498559488
4     5201798304953761792
5     74168662805676031
6     -1
7     18
8     18
9     5201798304953761792
10    3
11    6
12    12
13    24
14    48
15    96
16    192
17    384

We can see that the progression is still the previous number multiplied by 2 only this time starting with the number 3 instead of 2. We can infer that the integer added as part of the code is not the multiplier but the initial value of the sequence and that the added instruction requires a single field element (memory cell) and its job is to simply double the last value referenced by the ap pointer.

Reference

The exercise in this article can be found in this section of the Cairo docs.