Range Check Builtin

The Range Check builtin is used to check whether a field element is in the range \([0,n]\). It is used when instantiating and comparing the various integer types. There's two variants of this builtin, the standard one that operates on a \(2^{128}-1\) upper bound and another variant named Range Check 96 that operates on a \(2^{96}-1\) upper bound. We will focus on the standard one in this section, but the same principles apply to the 96 variant.

While it's possible to implement range checking using pure Cairo code (for example, by decomposing a number into its binary representation and verifying each bit), using the builtin is significantly more efficient. A pure Cairo implementation would require at least 384 instructions to verify a single range check, whereas the builtin achieves the same result with computational cost equivalent to about 1.5 instructions. This efficiency makes the Range Check builtin essential for the implementation of bounded integer arithmetic and other operations that require value range verification.

Cells organization

The Range Check builtin enforces that all values written to its memory cells are within the range \([0,2^{128}-1]\). The memory cells constrained by this builtin are called range-checked cells as every values written to this memory segment must be contained within the range \([0,2^{128}-1]\) otherwise an out of range error will be thrown. These range-checked cells must store valid field elements, not relocatable values.

In the following example, a Cairo program writes 0, 256 and \(2^{128}-1\) to the Range Check memory segment, since these 3 field elements are constrained within the \([0,2^{128}-1]\) range, the program execution is valid.

On the next example however, the program tries to write \(2^{128}\) to memory cell 2:2, which is not contained within the builtin valid range. An out of range error is thrown and the program execution aborted.

In the final example, the program attempts to write a relocatable value, a pointer to the cell 1:7 which is not allowed by the builtin as it only accepts field elements.

Implementation References

These implementation references of the Range Check builtin might not be exhaustive.

• TypeScript Range Check Builtin
• Python Range Check Builtin
• Rust Range Check Builtin
• Go Range Check Builtin
• Zig Range Check Builtin

Resources on Range Check

If you're interested in how the Range Check builtin works and its usage in the Cairo VM, take a look at these references:

• Starknet, CairoZero documentation, Range Checks section of Builtins and implicit arguments
• Lior G., Shahar P., Michael R., Cairo Whitepaper, Sections 2.8 and 8