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 <=
.