Robbepop / apint

Arbitrary precision integers library.
Other
26 stars 4 forks source link

Make a list of invariants that maintainers are suppossed to uphold #26

Open AaronKutch opened 6 years ago

AaronKutch commented 6 years ago

Some of my functions rely on the unused bits of inputs being cleared. I currently assume that all functions (except maybe for functions that allow access to the raw Digits) will not produce ApInts with unused bits. Are there any other invariants that should be upheld, because we should document it and put it in lib.rs or mod.rs?

Robbepop commented 6 years ago

This is a good idea and I thought that this already existed but can't find it myself. Basically there are only a few invariants for the public APIs of ApInt:

These properties are of course propagated to Int and Uint since they are simple wrappers around ApInt.

AaronKutch commented 6 years ago

Add to that

Before I got into writing these algorithms I thought that left or right shifts more than or equal to the bitwidth should return 0 instead of erroring. I realize now that having the invariant allows for certain optimizations and prevents corner cases around usize::MAX. Every time I have encountered a situation where not having that invariant was useful performance wise, there was not that much of a performance gain and there existed a branch I could make to a specialization. For example, in a usage of the experimental rotate_right function, whenever the shift was the same as the BitWidth I would just return the ApInt without calling any function on it. There was also a situation I encountered in the division function,

                duo_sig_dd = if duo_lz == 0 {
                    DoubleDigit::from_lo_hi(duo[duo_sd - 1],duo[duo_sd])
                } else {
                    (duo[duo_sd].dd() << (duo_lz + digit::BITS)) |
                    (duo[duo_sd - 1].dd() << duo_lz) |
                    (duo[duo_sd - 2].dd() >> (digit::BITS - duo_lz))
                };

I'm thinking that we should include the reasoning to why these invariants are in public documentation, because only two months ago I thought some were ridiculous.