oscbyspro
NBKFlexibleWidthKit
I'm working on a Big[U]Int™ module. That's it. That's the ~~tweet~~ GitHub post.
I've pondered normalization behaviors for a bit, and I wonder if there's merit in a dynamically-fixed-width type. This hypothetical integer type would be given a size at initialization, then behave much like a fixed-width type unless specifically told to resize or whatnot. I also imagine that you could build a canonical big integer type on top of it. Something like NBKDynamicWidthKit and NBKAutomaticWidthKit, where NBKAutomaticWidthKit provides automatic normalization. Hm.
2's complement or sign(um)-magnitude, that is the question :thought_balloon:
I'm inclined to go with sign-magnitude because then I can leverage the magnitude. I wonder whether I should go sign or signum, however. Integer solutions become infinitely less elegant once you step out of the fixed-width real. A sign is either asymmetrically normalized or produces two zero representations. A signum, on the other hand, duplicates information that is trivially derived by checking whether the magnitude is zero or not. Hm.
One nice thing about allowing both positive and negative zero, however, is that you can manipulate the sign and magnitude independently; there's one less invariant to maintain.
On a side note: I believe a two's complement in-memory solution is easier to implement because the as-if-two's-complement behavior is the biggest headache by far. I'm just not convinced I could make it as performant, because negating arbitrary two's complement is quite expensive compared to toggling a sign bit.
Thought: I wonder if you can mitigate the cost with a lazy magnitude view 💭
I'm thinking of adding a NBKResizableWidthKit (#46), even if it's only to house some kind of resizable-but-never-empty collection of words. I don't really want juggle two sets of invariants in-line (#47). Hm.
Untangling NBKResizableWidthKit (#46) might take a while. Instead of a fixed-width-but-resizable storage model, I might opt for freestanding generic functions. That way the logic can be reused on buffer pointers, etc. I will see what works out.
UIntXL is close to done, but Signed<UIntXL> still needs some work. Maybe I should split NBKSignedKit (#81) into a different feature branch? I have developed them side-by-side because the latter needs proper integer models for testing. Hm.
I have put a lot of effort into separating my models and algorithms. So NBKFlexibleWidthKit mostly handles branching, resizing and normalization logic, while NBKCoreKit takes care of the calculations. I find this approach easy to maintain and reason about. (#85) helps a lot.
Given that auto-normalization is the main feature of these integers, NBKNormalWidthKit is perhaps a more apt name.