Cairo lang: Sum even numbers in an array
Tags: cairolang, starknet, web3, ethereum
Published: 2022-11-05 08:32:47

## Setting up

We use [protostar](https://docs.swmansion.com/protostar/docs/tutorials/introduction) to set up a simple Cairo project where we can implement and test our function.

```bash
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`
```javascript
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](https://www.cairo-lang.org/docs/reference/syntax.html#syntax-implicit-arguments). `{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](https://www.cairo-lang.org/docs/hello_cairo/intro.html#the-primitive-type-field-element-felt).  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. 
```javascript
 if (arr_len == idx) {
       return (run,);
 }
```
To check if the an number is even, we use bitwise xor

```javascript
    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.
``` javascript
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
```javascript
%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](https://www.cairo-lang.org/docs/hello_cairo/intro.html?highlight=assert#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.