test_fields.cpp:test_signed_digits() breaks on line 386

[vesselinux]

test_signed_digits breaks on line 386 https://github.com/clearmatics/libff/blob/develop/libff/algebra/fields/tests/test_fields.cpp#L386 . The test breaks in the single case when the size of the digit is 2 bits i.e. for i=2 on line 391 https://github.com/clearmatics/libff/blob/develop/libff/algebra/fields/tests/test_fields.cpp#L391 . For all values of i other than 2 all checks pass. Seems to be a problem with the computation of num_digits https://github.com/clearmatics/libff/blob/develop/libff/algebra/fields/tests/test_fields.cpp#L348:

    const size_t num_digits =
        (FieldT::num_bits + 1 + digit_size - 1) / digit_size;

If modified to

    const size_t num_digits =
        (FieldT::num_bits + 1 + digit_size - 1 + 1) / digit_size;

i.e. if num_digits is increased by 1, then all tests pass for FieldT(-1), but one test fails for FieldT(-2) (the one for i=21) https://github.com/clearmatics/libff/blob/develop/libff/algebra/fields/tests/test_fields.cpp#L348.

[dtebbs]

Thanks @vesselinux . Adding some notes for now, for when this gets tackled properly.

The issues seems to be that the current "optimistic" calculation of the number of rqeuired digits is assuming that we can get away with Field::num_bits, plus 1 for possible overflow from the final digit. Hence we compute ciel((num_bits + 1) / digit_size). In this specific case (num_bits = 255), the plus one simply accounts for the sign bit of the final digit, and for large numbers such as mod - 1, bits 254~252 are all 1.

For digit size of 2, the highest order unsigned digits are then: 01 | 11 | .... where the 2nd digit will overflow to the next digit, but there is no capacity left to accomodate the overflow.

We don't want extra digits when they aren't required (since this will just add work to some multiexp schemes, so the correct calculation for num_digits must also taking into account the value of Field(-1) (in particular the number of leading 1s).

(Needs more thought, but one approach could be to count the leading 1s and check digit sizes up to num_leading_ones - 1. Then find the smallest digit size for which an extra bit is not required, and store this as a stataic member of the Field.)

[AntoineRondelet]

Fixed in #71 which is now merged. Closing this ticket as a consequence.