stillwater-sc / universal / 26003086638

84%

master: 84%

Build Type

push

github

Committed by web-flow

Commit Message

fix(einteger): correct borrow propagation in Knuth Algorithm D step D4 (#861)

The multi-limb long-division in einteger::operator/= used an unsigned
diff/borrow pair in Knuth's step D4. The idiomatic underflow indicator
`diff >> bitsInBlock` only yields -1/0 with arithmetic right shift on
a signed type; with uint64 it returns 0x...FFFFFFFF on underflow and
`p_hi - 0xFFFFFFFF` wraps to a huge unsigned value that corrupts the
next iteration's borrow_in, producing a quotient too large by exactly
one limb for some inputs. Switch diff/borrow to int64 so the shift
acts as a proper sign extension.

In the same step also fix two hardcoded 32-bit shifts that prevented
the multi-limb division and remainder-denormalization paths from
working with uint8_t and uint16_t blocks: the carry shift in the
"subtracted too much, add back" branch and the remainder normalization
loop now use `bitsInBlock` instead of a literal 32. The low-bits mask
in D4 is derived from BASE-1 so it tracks the block width.

Add a regression test (RegressionIssue842) that computes
(3141592653589793 << 100) / 5^15 with einteger<uint8_t/16_t/32_t> and
compares against an independent integer<2048> reference via decimal
string. Pre-fix the uint32_t case (the default einteger<> the bug was
originally reported against) computed an off-by-2^64 quotient.

Resolves #842

Co-authored-by: Claude Opus 4.7 (1M context) <noreply@anthropic.com>

Coverage Stats

11 of 12 new or added lines in 1 file covered. (91.67%)

12 existing lines in 2 files now uncovered.

46685 of 55524 relevant lines covered (84.08%)

6352977.91 hits per line