NBKFlexibleWidthKit

[oscbyspro]

I'm working on a Big[U]Int™ module. That's it. That's the tweet GitHub post.

[oscbyspro]

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.

[oscbyspro]

2's complement or sign(um)-magnitude, that is the question 💭

[oscbyspro]

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.

[oscbyspro]

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.

[oscbyspro]

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 💭

[oscbyspro]

I decided to go with sign-magnitude and embrace negative zero 🤗

[oscbyspro]

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.

[oscbyspro]

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.

[oscbyspro]

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.

[oscbyspro]

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.

[oscbyspro]

Given that auto-normalization is the main feature of these integers, NBKNormalWidthKit is perhaps a more apt name.

[oscbyspro]

Hm. I wonder if I should make it UIntXL generic over its element type...