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.cairo
command.
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.
Top comments (0)