# Unsigned 64-bit integer operations

Module std::math::u64 contains a set of procedures which can be used to perform unsigned 64-bit integer operations. These operations fall into the following categories:

• Arithmetic operations: Addition, multiplication, division, etc.
• Comparison operations: Equality, less than, greater than etc.
• Bitwise operations: Binary AND, OR, XOR, bit shifts etc.

All procedures assume that an unsigned 64-bit integer (u64) is encoded using two elements, each containing an unsigned 32-bit integer (u32). When placed on the stack, the least-significant limb is assumed to be deeper in the stack. For example, a u64 value a consisting of limbs a_hi and a_lo would be position on the stack like so:

[a_hi, a_lo, ... ]


Procedures which check whether the input values are encoded correctly are designated with checked prefix. For example, checked_add would fail if any of the top 4 elements on the stack contains a value greater than $$2^{32} - 1$$. In contrast, wrapping_add and overflowing_add would not perform these checks, and therefore, if any of the top 4 stack elements is greater than $$2^{32} - 1$$, the operation will not fail but rather will produce an undefined result. Thus, when using versions of procedures which are not checked, it is important to be certain that input values are 32-bit limbs encoding valid u64 values.

## Arithmetic operations¶

Procedure Description
checked_add Performs addition of two unsigned 64-bit integers and fails if the result would overflow.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = (a + b) % 2^64
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [overflow_flag, c_hi, c_lo, …], where c = (a + b) % 2^64
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = (a + b) % 2^64
checked_sub Performs subtraction of two unsigned 64-bit integers and fails if the result would underflow.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = (a - b) % 2^64
overflowing_sub Performs subtraction of two unsigned 64-bit integers preserving the overflow.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [underflow_flag, c_hi, c_lo, …], where c = (a - b) % 2^64
wrapping_sub Performs subtraction of two unsigned 64-bit integers discarding the overflow.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = (a - b) % 2^64
checked_mul Performs multiplication of two unsigned 64-bit integers and fails if the result would overflow.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = (a * b) % 2^64
overflowing_mul Performs multiplication of two unsigned 64-bit integers preserving the overflow.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi_hi, c_hi_lo, c_lo_hi, c_lo_lo, …], where c = (a * b) % 2^64
wrapping_mul Performs multiplication of two unsigned 64-bit integers discarding the overflow.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = (a * b) % 2^64
checked_div Performs division of two unsigned 64-bit integers discarding the remainder.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a // b
unchecked_div Performs division of two unsigned 64-bit integers discarding the remainder.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a // b
checked_mod Performs modulo operation of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a % b
unchecked_mod Performs modulo operation of two unsigned 64-bit integers.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a % b
checked_divmod Performs divmod operation of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [r_hi, r_lo, q_hi, q_lo …], where r = a % b, q = a // b
unchecked_divmod Performs divmod operation of two unsigned 64-bit integers.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [r_hi, r_lo, q_hi, q_lo …], where r = a % b, q = a // b

## Comparison operations¶

Procedure Description
checked_lt Performs less-than comparison of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a < b, and 0 otherwise.
unchecked_lt Performs less-than comparison of two unsigned 64-bit integers.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a < b, and 0 otherwise.
checked_gt Performs greater-than comparison of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a > b, and 0 otherwise.
unchecked_gt Performs greater-than comparison of two unsigned 64-bit integers.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a > b, and 0 otherwise.
This takes 11 cycles.
checked_lte Performs less-than-or-equal comparison of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a <= b, and 0 otherwise.
unchecked_lte Performs less-than-or-equal comparison of two unsigned 64-bit integers.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a <= b, and 0 otherwise.
checked_gte Performs greater-than-or-equal comparison of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a >= b, and 0 otherwise.
unchecked_gte Performs greater-than-or-equal comparison of two unsigned 64-bit integers.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a >= b, and 0 otherwise.
checked_eq Performs equality comparison of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a == b, and 0 otherwise.
unchecked_eq Performs equality comparison of two unsigned 64-bit integers.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a == b, and 0 otherwise.
checked_neq Performs inequality comparison of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a != b, and 0 otherwise.
unchecked_neq Performs inequality comparison of two unsigned 64-bit integers.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c, …], where c = 1 when a != b, and 0 otherwise.
checked_eqz Performs comparison to zero of an unsigned 64-bit integer.
The input value is assumed to be represented using 32-bit limbs, fails if it is not.
The stack transition looks as follows:
[a_hi, a_lo, …] -> [c, …], where c = 1 when a == 0, and 0 otherwise.
unchecked_eqz Performs comparison to zero of an unsigned 64-bit integer.
The input value is assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[a_hi, a_lo, …] -> [c, …], where c = 1 when a == 0, and 0 otherwise.
checked_min Compares two unsigned 64-bit integers and drop the larger one from the stack.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a when a < b, and b otherwise.
unchecked_min Compares two unsigned 64-bit integers and drop the larger one from the stack.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a when a < b, and b otherwise.
checked_max Compares two unsigned 64-bit integers and drop the smaller one from the stack.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a when a > b, and b otherwise.
unchecked_max Compares two unsigned 64-bit integers and drop the smaller one from the stack.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a when a > b, and b otherwise.

## Bitwise operations¶

Procedure Description
checked_and Performs bitwise AND of two unsigned 64-bit integers.
The input values are assumed to be represented using 32-bit limbs, but this is not checked.
The stack transition looks as follows:
[[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a AND b.
checked_or Performs bitwise OR of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a OR b.
checked_xor Performs bitwise XOR of two unsigned 64-bit integers.
The input values are expected to be represented using 32-bit limbs, and the procedure will fail if they are not.
The stack transition looks as follows:
[b_hi, b_lo, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a XOR b.
overflowing_shl Performs left shift of one unsigned 64-bit integer preserving the overflow and
using the pow2 operation.
The input value to be shifted is assumed to be represented using 32-bit limbs.
The shift value should be in the range [0, 64), otherwise it will result in an error.
The stack transition looks as follows:
[b, a_hi, a_lo, …] -> [d_hi, d_lo, c_hi, c_lo, …], where (d,c) = a << b,
which d contains the bits shifted out.
This takes 35 cycles.
unchecked_shl Performs left shift of one unsigned 64-bit integer using the pow2 operation.
The input value to be shifted is assumed to be represented using 32-bit limbs.
The shift value should be in the range [0, 64), otherwise it will result in an error.
The stack transition looks as follows:
[b, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a << b mod 2^64.
This takes 28 cycles.
overflowing_shr Performs right shift of one unsigned 64-bit integer preserving the overflow and
using the pow2 operation.
The input value to be shifted is assumed to be represented using 32-bit limbs.
The shift value should be in the range [0, 64), otherwise it will result in an error.
The stack transition looks as follows:
[b, a_hi, a_lo, …] -> [d_hi, d_lo, c_hi, c_lo, …], where c = a >> b, d = a << (64 - b).
This takes 94 cycles.
unchecked_shr Performs right shift of one unsigned 64-bit integer using the pow2 operation.
The input value to be shifted is assumed to be represented using 32-bit limbs.
The shift value should be in the range [0, 64), otherwise it will result in an error.
The stack transition looks as follows:
[b, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a >> b.
This takes 44 cycles.
unchecked_rotl Performs left rotation of one unsigned 64-bit integer using the pow2 operation.
The input value to be shifted is assumed to be represented using 32-bit limbs.
The shift value should be in the range [0, 64), otherwise it will result in an error.
The stack transition looks as follows:
[b, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a << b mod 2^64.
This takes 35 cycles.
unchecked_rotr Performs right rotation of one unsigned 64-bit integer using the pow2 operation.
The input value to be shifted is assumed to be represented using 32-bit limbs.
The shift value should be in the range [0, 64), otherwise it will result in an error.
The stack transition looks as follows:
[b, a_hi, a_lo, …] -> [c_hi, c_lo, …], where c = a << b mod 2^64.
This takes 40 cycles.

Last update: December 21, 2023
Authors: kmurphypolygon