Cairo lang: Sum even numbers in an array

Setting up

We use protostar to set up a simple Cairo project where we can implement and test our function.

protostar init sum-even

Algorithm

Cairo does not have a standard for loop built-in. To sum even numbers in an array, we use recursion.

main.cairo

from starkware.cairo.common.bitwise import bitwise_xor
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin, HashBuiltin

func sum_even{bitwise_ptr: BitwiseBuiltin*}(arr_len: felt, arr: felt*, run: felt, idx: felt) -> (
    sum: felt
) {
    if (arr_len == idx) {
        return (run,);
    }

    let val = arr[idx];

    let (xor) = bitwise_xor(val, 1);
    let new_idx: felt = idx + 1;

    if (xor == val + 1) {
        let new_run = run + val;
        return sum_even(arr_len, arr, new_run, new_idx);
    } else {
        return sum_even(arr_len, arr, run, new_idx);
    }
}

The first time I look at Cairo's functions. They seem strange to me. Why are things like {bitwise_ptr: BitwiseBuiltin*} included in most every function?

{bitwise_ptr: BitwiseBuiltin*} is an Implicit argument. {bitwise_ptr: BitwiseBuiltin*} adds argument bitwise_ptr which is a pointer and returns an updated pointer bitwise_ptr = bitwise_ptr + BitwiseBuiltin.SIZE to the function. BitwiseBuiltin.SIZE is the memory size of BitwiseBuiltin type.

The arguments' type: felt is a filed element. When you don't specify variables' types, you use felt. It is like any in Typescript. We use felt* for array arr (The single asterisk indicates that it is a pointer)

If idx equals arr_len, it means that we reach the end of the array. We simply return the sum value.

 if (arr_len == idx) {
       return (run,);
 }

To check if the an number is even, we use bitwise xor

    let val = arr[idx];
    let (xor) = bitwise_xor(val, 1);
    // xor == val + 1 means val is an even number

If a number is even, we add it to the sum. Otherwise, move to the next number.

if (xor == val + 1) {
        let new_run = run + val;
        return sum_even(arr_len, arr, new_run, new_idx);
    } else {
        return sum_even(arr_len, arr, run, new_idx);
    }

To test the function, we make test_sum_even in test_main.cairo

Test

%lang starknet
from starkware.cairo.common.cairo_builtins import BitwiseBuiltin
from starkware.cairo.common.alloc import alloc

from src.main import sum_even

@external
func test_sum_even{bitwise_ptr: BitwiseBuiltin*}() {
    let (array: felt*) = alloc();
    assert array[0] = 2;
    assert array[1] = 1;

    let (sum) = sum_even(2, array, 0, 0);
    assert 2 = sum;

    return ();
}

%lang starknet declares that this file is a Starknet file. Without it, we cannot use @external decorator which allows us to call it by protostar test tests/test.cairocommand.

We also need to supply the implicit argument bitwise_ptr: BitwiseBuiltin* because we use it in our sum_even

To make an array, we call alloc() function which dynamically creates a new memory segment to store the array as a single element. Then we start to add values to the array using the assert statement. assert array[0] = 2; set the value of the first memory cell at the address array (a pointer) to 2. If any value was set previously, it will verify if the previous value equals 2.

Finally, we check if the returned sum is the expected result 2 by using the assert keyword again.

Conclusion

This is an exercise from Encode's Cairo Bootcamp. At the time of writing, I am participating in the Bootcamp. Teaching is the best way to learn. I indeed get a better understanding of Cairo by explaining the code in this article.

Github repo: https://github.com/peterblockman/cairo-sum-even

Hope you enjoy the blog post. Thank you for taking the time to read.