Assessment reports>Barretenberg Bigfield>Discussion>Inefficient loops

Inefficient loops

In some parts of the codebase, unnecessary loops are used — for example, this loop in bigfield<Builder, T>::operator-,

uint512_t constant_to_add = modulus_u512;
// add a large enough multiple of p to not get negative result in subtraction
while (constant_to_add.slice(NUM_LIMB_BITS * 3, NUM_LIMB_BITS * 4).lo <= limb_3_maximum_value) {
    constant_to_add += modulus_u512;
}

which could be replaced by (pseudocode):

constant_to_add_factor = ((limb_3_maximum_value << (3*NUM_LIMB_BITS)) / modulus_u512) + 1;
constant_to_add = constant_to_add_factor  * modulus_u512;

Note, however, that the above loop does not calculate the minimum multiple of so as to avoid a negative result on subtraction. For that, the loop should only advance on < rather than <=. However, even though the documenting comments for operator- emphasize that the minimum should be calculated, this is not actually necessary (though using a larger-than-necessary multiple of has performance downsides):

* We must compute the MINIMUM value of `m` that ensures that none of the bigfield limbs will underflow!
*
* i.e. We must compute the MINIMUM value of `m` such that, for each limb `i`, the following result is positive:
*
* *this.limb[i] + X.limb[i] - other.limb[i]

We recommend to update the documentation accordingly. There is also an inconsistency in the comments regarding usage of "positive" (usually meaning > 0) versus "non-negative" (meaning >= 0). In this case, the goal is preventing an underflow, so >= 0 is the precise condition, and so usage of "non-negative" would be clearer.

To replace the variant of the loop that uses <, one could use the following:

constant_to_add_factor = (((limb_3_maximum_value << (3*NUM_LIMB_BITS)) + modulus_u512 - 1 ) / modulus_u512);
constant_to_add = constant_to_add_factor  * modulus_u512

Similarly, in bigfield<Builder, T>::assert_is_not_equal, the loop

uint512_t target = target_modulus;
size_t overload_count = 0;
while (target < maximum_value) {
    ++overload_count;
    target += target_modulus;
}
return overload_count

could be replaced by

if (maximum_value == 0)
    return 0;
else
    return (maximum_value - 1) / target_modulus

See also Finding ref, according to which the first branch and -1 should be removed as well, corresponding to changing < in the condition of the loop to <=.

Zellic © 2025Back to top ↑