Implement the function y = x^n.
Solution
Cairo doesn’t have for or while loops so the only way to solve this problem is by using recursion. In fact, Cairo doesn’t support any type of recursion, it only supports tail recursion.
We start by defining the function signature.
func main():
pow_n(x=2, n=3)
return ()
end
func pow_n(x: felt, n: felt) -> (y: felt):
# calculates y=x^n
end
We don’t want to implement the tail recursion directly on pow_n because we need a third parameter for the recursion, the base value or x, and defining it directly on pow_n would leak some implementation details to the caller (main). To keep the public interface clean, let’s define another function that takes care of the tail recursion implementation.
func main():
pow_n(x=2, n=3)
return ()
end
func pow_n(x: felt, n: felt) -> (y: felt):
let (res) = pow_n_tail(acc=x, iter=n, base=x)
return (y=res)
end
func pow_n_tail(acc: felt, iter: felt, base: felt) -> (res: felt):
# implementation
end
On each pass of the recursion, we will multiply the accumulator (acc) by the base value (base) and decrease our iterator (iter) by one. We will then call the function again with updated values.
func main():
pow_n(x=2, n=3)
return ()
end
func pow_n(x: felt, n: felt) -> (y: felt):
let (res) = pow_n_tail(acc=x, iter=n, base=x)
return (y=res)
end
func pow_n_tail(acc: felt, iter: felt, base: felt) -> (res: felt):
let acc = acc * base
let iter = iter - 1
return pow_n_tail(acc, iter, base)
end
Of course we don’t want the recursion to go on forever, we need to stop when the iterator reaches the value 0 and at that point we can return the result of the calculation.
Because Cairo doesn’t support if clauses, we will have to rely on conditional jumping to distinguish both cases, when the iterator is 0 and when it’s not.
func main():
pow_n(x=2, n=3)
return ()
end
func pow_n(x: felt, n: felt) -> (y: felt):
let (res) = pow_n_tail(acc=x, iter=n, base=x)
return (y=res)
end
func pow_n_tail(acc: felt, iter: felt, base: felt) -> (res: felt):
jmp body if iter != 0
return (res=acc)
body:
let acc = acc * base
let iter = iter - 1
return pow_n_tail(acc, iter, base)
end
We are ready to compile and run our code to verify its operation. If everything goes well we should get the value 16 (2^3).
$ cairo-compile exercise.cairo --output exercise.json
$ cairo-run --program=exercise.json --print_memory --relocate_prints
>>>
Addr Value
-----------
⋮
1 5189976364521848832
2 2
3 5189976364521848832
4 3
5 1226245742482522112
6 3
7 2345108766317314046
8 5191102242953854976
9 5191102247248822272
10 5191102242953854976
11 1226245742482522112
12 3
13 2345108766317314046
14 146226256843603964
15 4
16 5191102238658887680
17 2345108766317314046
18 5209116645758042112
19 5198983563776393216
20 -1
21 5191102247248822272
22 1226245742482522112
23 -8
24 2345108766317314046
25 52
26 52
27 2
28 3
29 27
30 7
31 2
32 3
33 2
34 31
35 13
36 4
37 2
38 2
39 36
40 24
41 8
42 1
43 2
44 41
45 24
46 16
47 0
48 2
49 46
50 24
51 16
As you can see, the program worked as expected.
References
The exercise in this article can be found in this section of the Cairo docs.
Hi, I’m enjoying reading your solutions as I work through How Cairo Works. I am doing the exercises first, then comparing notes with your solutions. One thing I noticed on this one: I’m not sure that Cairo only supports tail recursion. Consider this program, which works correctly:
func main():
[ap] = 2 ;ap++
[ap] = 4 ;ap++
call fto
[ap - 1] = 16
ret
end
func fto(x, n) -> (res: felt):
jmp f_body if n != 0
[ap] = 1 ;ap++
ret
f_body:
[ap] = x ;ap++
[ap] = n - 1 ;ap++
call fto
[ap] = x * [ap - 1] ;ap++
ret
end
It doesn’t use an accumulator, the result is calculated as
fto(x, 0) = 1
fto(x, n) = x * fto(x, n-1) for n > 0.
So it is not tail recursive. Also, it seems to be just as efficient, in terms of the number of steps taken and memory slots used, as the tail recursive approach. I think the big advantage of tail recursion, that you don’t need to maintain a stack of calls, is unimportant with a read once memory model. Any memory you have already written to is lost anyway, whether you will need to read it again or not.
Oops, I meant “write once” not “read once”.
I think you might be right, I never stopped to think that in a write-once memory model recursion technically can’t be optimized because you can’t overwrite a memory cell. I’ll ask inside StarkWare to see if I get a different explanation
Apparently there is an optimization with tail recursion in Cairo, just not as powerful as you would normally get: https://stackoverflow.com/questions/72321871/when-to-use-tail-call-optimization-in-a-cairo-smartcontract
OK, that’s interesting thanks!
Hello David , here a version in cairo 0.10:
%builtins output
from starkware.cairo.common.serialize import serialize_word
func main{output_ptr: felt*}(){
let (a)= pow_n(x=2, n=3);
serialize_word(a);
ret;
}
func pow_n(x: felt, n: felt) -> (y: felt){
let (resul) =calculo(acc=x, iter=n, base=x);
return (y=resul);
}
func calculo(acc: felt, iter:felt, base: felt) -> (res: felt){
if (iter==0){
return (res=acc);
}
let acc= acc * base;
let iter=iter -1;
return calculo(acc, iter, base);
}
cairo-run –program=exercise.json --print_output –layout=small