Investigate flexible in-memory 2's complement

[oscbyspro]

I've decided to go with sign-magnitude, but I'm kind of curious how 2's complement stacks up. Perhaps I'll write a prototype when NBKFlexibleWidthKit is done.

[oscbyspro]

I bet I could do it in a week, because actual two's complement is so much more simpler than as-if two's complement.

[oscbyspro]

I hope in-memory two's complement compares well (or at least well enough) because it would be really nice if I did not have to manage the whole as-if two's complement circus.

[oscbyspro]

I suppose another thing that vexes me about sign-magnitude-as-if-two's-complement is that the digit type ends up being Int when you'd really want somethings like Signed<UInt>, which is how I modeled it in ANK.

[oscbyspro]

Having said that, signed two's complement normalization is quite clumsy compared to magnitude normalization.

[oscbyspro]

Storing the sign bit separately makes normalization as simple as the unsigned case, at the cost of bit castability. It's also weird and wasteful in the case of resizable integers (#46). Hm. I wonder if there's a better layout? Perhaps somehing like:

/// a collection of at least one digit
struct ResizableInteger<Digit> {
    var body: Array<Digit.Magnitude> // 0 or more elements
    var tail: Digit
}

/// or where the magnitude can have 0 bit width
struct ResizableInteger {
    var body: Magnitude
    var tail: Int

    struct Magnitude {
        var words: Array<UInt> // 0 or more elements
    }
}

Edit: I suppose these layouts are still implementable as arrays.

[oscbyspro]

I never got around to evaluating its viability, but I made two proximal tests/observations:

• 2x formTwosComplement() on lhs and rhs makes long division ≤ 1.3x slower
• 2x formTwosComplement() on the product makes long multiplication ≤ 1.2x slower

[oscbyspro]

Hm. I'll use the next couple of days to try it out.

[oscbyspro]

I haven't gotten to comparing performance yet, but there's something compelling about accessing its words with O(1) complexity. Is it as compelling as O(1) magnitude and negation? Dunno, but the un/signed symmetry is neat.

[oscbyspro]

Well, if it is viable then viability does not come easily.

// Scrappy 2's vs feature/NBKFlexibleWidth 
// Less is brrrrrr. Copying. (self, digit)

add: ( 78,  32) vs (91, 55)
sub: ( 79,  29) vs (92, 49)
mul: (164, 122) vs (88, 58) // (92, 64) with non-magnitude algorithms
div: ( 94,  46) vs (57, 20)

---

Lack of borrowing/consuming is perhaps significant.

[oscbyspro]

The inability to bit cast un/signed values (due to normalization) is also unfortunate.

[oscbyspro]

Seems high-maintenance, while most of sign-magnitude is paid for by the magnitude.

[oscbyspro]

I could write a generic FlexibleWidth\<Digit> model where Digit is either Int or UInt. That would be the most straightforward un/signed two's complement option (in my opinion). I've tried to avoid it, however, because there's only two interesting specializations of it, and it requires @inlinable everywhere. It wouldn't improve IntXL's performance, but it also wouldn't require two private helper protocols.

[oscbyspro]

I think I'll use the next couple of days trying out the generic approach. I'm fine with incrementally making IntXL viable, so long as doing so does not increase the project's complexity disproportionately.

[oscbyspro]

My first impression of a generic FlexibleWidth\<Digit> is not great, as the models are obviously quite different. One can underflow, the other cannot. They also normalize differently. I'm sure the fixed-width-but-resizable storage could be made generic, but I don't think it suits flexible-width.