# Nondeterministic jumps¶

We can now describe a code pattern, called “nondeterministic jumps”, that combines Conditional jumps and Hints. A nondeterministic jump is a jump instruction that may or may not be executed, according to the prover’s decision (rather than according to a condition on values which were computed before). To do this, use the Cairo instruction:

jmp label if [ap] != 0; ap++


The idea is to use an unused memory cell ([ap]) to decide whether or not to jump. Do not forget to increase ap to make sure the following instructions will not use this memory cell.

As with every nondeterministic instruction, a hint must be attached to let the prover know whether to jump or not. For example:

%{
memory[ap] = 1 if x > 10 else 0
%}
jmp label if [ap] != 0; ap++


## Exercise¶

The following code tries to compute the expression $$\lfloor x / 2 \rfloor$$ using the formula

$\begin{split}\lfloor x / 2 \rfloor = \begin{cases} x / 2, & \text{x is even} \\ (x - 1) / 2, & \text{x is odd} \\ \end{cases}\end{split}$

(recall that since we’re working in a field, the operation / 2 is division by 2 in the field, rather than integer division).

Can you explain what’s wrong with the following code?

func div2(x):
%{ memory[ap] = ids.x % 2 %}
jmp odd if [ap] != 0; ap++

even:
# Case n % 2 == 0.
[ap] = x / 2; ap++
ret

odd:
# Case n % 2 == 1.
[ap] = x - 1; ap++
[ap] = [ap - 1] / 2; ap++
ret
end


In Integer division you will see how to implement this function using the range-check builtin.

Hint

Consider the verifier point of view. Can you give an example of what a malicious prover can do so that div2 will return the wrong value?

Hint2

Try to change the hint to %{ memory[ap] = 1 - (ids.x % 2) %} and see what happens when you call div2(2). Do you get the expected result (1)?