Cairo exercise: Polynomial Equation

Problem

Write a program poly.cairo that computes the expression:

x^3 + 23x^2+ 45x + 67 = 0, x = 100

1. After the program ends, the value should be at [ap - 1].

2. For this exercise, you may assume that the fp register is constant and initialized to the same value as ap.

Link to the problem in Cairo documentation

Solution

%lang starknet

func compute_poly() -> felt {
    [ap] = 100, ap++;
    [ap] = [ap - 1] + 23, ap++;
    [ap] = [ap - 2] * [ap - 1], ap++;
    [ap] = [ap - 1] + 45, ap++;
    [ap] = [ap - 1] * [ap - 4], ap++;
    [ap] = [ap - 1] + 67, ap++;
    ret;
}

Explain the solution

Cairo receives instructions and operates on memory cells that are immutable and can hold one value. Therefore, first, we need to factor our equation to make instructions for each memory cell.

x(x(x + 23) + 45) + 67 = 0, x = 100

x: [ap] = 100, ap++;

Here we tell Cairo to put 100 to the memory cell at address ap, then we move to the next memory cell by ap++

Note: ap is the allocation pointer pointing to the available memory cells. Read more about it here

x + 23: [ap] = [ap - 1] + 23, ap++

Now we are at the second memory cell. To refer to the value of x which is in the first cell, we use [ap - 1]. We also move the pointer to the next cell by ap++.

x(x+23): [ap] = [ap - 2] * [ap - 1] , ap++

At this step, we get the product of x which is 2 memory cells before the pointer and the previous memory cell's value x + 3. Then we call ap++ again to move to the next cell.

We continue to do the same for the rest of our equation:

x(x + 23) + 45: [ap] = [ap - 1] + 45, ap++;

x(x(x + 23) + 45): [ap] = [ap - 1] * [ap - 4], ap++ ;

x(x(x + 23) + 45) + 67: [ap] = [ap - 1] + 67, ap++;

Test

test_poly.cairo

%lang starknet

from src.poly import compute_poly

@external
func test_compute_poly() {
    let res = compute_poly();
    assert res = 1234567;
    return ();
}

Run protostar test tests/test_poly.cairo to test the function.

Conclusion

In this article, I've shown how to instruct Cairo to compute a polynomial equation. The more I understand Cairo, the more fascinating it becomes to me. Keep on learning!

If you have any questions, feel free to DM me on Twitter. I would love to talk.

Github repo