search

oscbyspro / Ultimathnum

Binary arithmetic reimagined in Swift
Apache License 2.0
4 stars 1 forks source link

Negative and infinite large-storage multiplication edge case #6

Closed oscbyspro closed 1 month ago

oscbyspro commented 1 month ago

I found a multiplication bug similar to the one in (#3). It's for a similar reason, but when the storage is large this time. If both inputs have bodies filled with 0s and an appendix of 1, then the product should be the combined number of 0s followed by a single 1. This is the only case that does not fit in the combined body allocation.

Test().multiplication(InfiniInt<I8>(repeating: 1) << 16, InfiniInt<I8>(repeating: 1) << 16, Fallible(1 << 32, error: false)) // value: 0 ⚠️
Test().multiplication(InfiniInt<U8>(repeating: 1) << 16, InfiniInt<U8>(repeating: 1) << 16, Fallible(1 << 32, error: true )) // value: 0 ⚠️

I'll be busy for a few days but it should be easy to fix.

Also, I bet my life would be easier if I stored the appendix bit as the last bit in the body instead.

oscbyspro commented 1 month ago

I wonder if I can salvage the current algorithm by looking at its overflow indicators. That'd be nice. Another idea is to just drop ascending zero elements and pad the product with them. It would make things like x * (1 << big) really fast too.

oscbyspro commented 1 month ago

I suppose I could also do the standard sign-magnitude-esque-2's-complement shuffle before and after the unsigned multiplication. I don't want to do that, however, because then multiplication would no longer be a borrowing operation.

Edit: It's a consuming operation at the moment, but it really ought to be borrowing is what I'm saying.

oscbyspro commented 1 month ago

I've written a solution based on the zero-prefix-dropping approach. It works, but I think it's inelegant. I might opt for the compact storage alternative (#7) instead. The latter simply does not have this problem, which seems a bit more refined.

oscbyspro commented 1 month ago

Yeah, I'll just use compact storage because it's the lesser the headache.

oscbyspro commented 1 month ago

The commit message says "input combination" but I suppose it's more like "input shape". There's obviously different versions of (body: 0s, appendix: 1) times (body: 0s, appendix: 1) but all of them take the same multiplication path.

oscbyspro commented 1 month ago

If anyone ever asks, the zero-dropping approach can be summarized as: If we are going to count zeros to catch an edge case, let us count in a way that benefits the other cases too.

oscbyspro commented 1 month ago

The (a << x) times (b << y) optimization is pretty nifty.

I wonder if I'll get a chance to leverage it deliberately.