nim-lang / bigints

BigInts for Nim
MIT License
124 stars 32 forks source link

Fix `shl`, `shr` & simplify `isZero` #133

Closed konsumlamm closed 1 year ago

konsumlamm commented 1 year ago

Now a: BigInt is zero if and only if a.limbs is empty. This simplifies isZero and reduces special cases to consider when consuming a BigInt.

While checking that all functions uphold this invariant, I noticed that shl and shr were buggy:

konsumlamm commented 1 year ago

Division is making too much problems, perhaps I'll reconsider this once division has been rewritten.

dlesnoff commented 1 year ago

If you have some failing checks, maybe this could be used for fixing the division algorithm. Do not hesitate to share these checks on the #123 issue.

konsumlamm commented 1 year ago

The problems are that unsignedDivRem relies on 0 having a limb in a lot of places and trying to replace those cases manually is a pain. Some of these cases should go away once we have operations with SomeInteger operands, but eventually it should probably get rewritten.