GCD and XGCD algorithms

[oscbyspro]

The (extended) Euclidean algorithm is almost always useful but I might limit it to unsigned inputs and mixed outputs:

public let divisor:        T.Magnitude // unsigned
public let lhsCoefficient: T.Signitude //   signed
public let rhsCoefficient: T.Signitude //   signed

This is because the unsigned algorithm is a bit simpler and more elegant, and I haven't yet found a real use for extending signed inputs. I also don't think that the derived quotients are all that useful but I might keep them around, dunno. Edit: Oh, wait, I remember testing it and thinking the quotients were annoying because they overflow for some inputs. Hm. That might have been for signed inputs. I suppose I'll have to test it again.

[oscbyspro]

Hm. Maybe something like this, since the struct approach felt a bit cumbersome:

extension BinaryInteger {
    @inlinable public consuming func euclidean (_ other: consuming Self) -> Magnitude { ... }
}

extension UnsignedInteger {
    @inlinable public consuming func euclidean1(_ other: consuming Self) -> 
    (divisor: Self, lhsCoefficient: Signitude) { ... }

    @inlinable public consuming func euclidean2(_ other: consuming Self) -> 
    (divisor: Self, lhsCoefficient: Signitude, rhsCoefficient: Signitude) { ... }
}

Perhaps I should put the half and full extensions in an opt-in module. I'm not sure yet.

[oscbyspro]

It turns out that the extended algorithm's bit cast overflows in 2 cases, and both are OK.

x = (x.1, x.0 &- x.1 &* S(raw: division.quotient))
y = (y.1, y.0 &- y.1 &* S(raw: division.quotient))

A) (lhs: 1, rhs: > S.max) or (lhs: > S.max, rhs: 1)
B) (lhs: > S.max, rhs: lhs ± 1) or (lhs: rhs ± 1, rhs: > S.max) where both > S.max

It's always in the last iteration of the loop so the results are stored in discarded variables.

---

Here's the quotient and remainder at the moment when the overflow occurs in each case:

A) (quotient: max(lhs, rhs), remainder: 0)
B) (quotient: min(lhs, rhs), remainder: 0)

[oscbyspro]

Hm. I suppose I haven't yet thought about infinite values.

1. XGCD(infinite, infinite) just works.
2. XGCD(infinite, ..finite) gets stuck in an infinite division loop (unsurprisingly).

So I suppose I should just precondition trap the infinite-finite case.

Edit: Nevermind, I think I should just trap all infinite inputs.

Edit: The remainder shuffle turns infinite-by-infinite division into infinite-by-finite division.

precondition(!self .isInfinite) // constant unless unsigned InfiniInt<T>
precondition(!other.isInfinite) // constant unless unsigned InfiniInt<T>

[oscbyspro]

I'm a bit vexed with the presence of these preconditions. There's no appropriate outputs in the infinite case, so I can't reasonable return a Fallible<T>. I don't want to pay for validation in the every other case, so Optional<T> is not viable either. I suppose there's at least one thing I can do that solves this kind of conundrum in general. I can add meta data types to BinaryInteger with information such as: values-of-this-type-are-always-finite. There are then multiple options, but I believe the simplest is to throw Infinity or some such. That way I can extend all binary integers while only adding the possibility of errors to a subset of them. I can't just solve it with a new protocol, because then I limit when these methods are available. I suppose I could do that, but these methods ought to extend the UXL type too.

protocol BinaryInteger { associatedtype Infinity: Error = Never }

I wonder if this is the only such type I need. It very well might be. All signed integers can be negative, for example.

---

I suppose I could also hoist the preconditions like I do with Divisor<T> but...

The Divisor<T> model is special because all binary integers can be zero but few can be infinite. That kind solution would also be twice as annoying given that both the left-hand-side and the right-hand-side need to satisfy the precondition.

[oscbyspro]

Assuming I go down the road laid out in the above comment, I wonder if I should do something similar w.r.t. infinite division.

[oscbyspro]

Since this issue has already derailed, I came up with a cool abstraction w.r.t. the above:

public protocol Breakpoint: Swift.Error {
    @inlinable static func breakpoint() throws(Self)
}

extension Swift.Never: Breakpoint {
    @inlinable public static func breakpoint() { }
}

public protocol BinaryInteger {
    associatedtype Infinity: Breakpoint = Never
}

extension BinaryInteger {
    @inlinable public func raiseIsInfiniteOrStaticNoOp() throws(Self.Infinity) {
        if  self.isInfinite else {
            try Self.Infinity.breakpoint()
        }
    }
}

[oscbyspro]

Note to self: Fallible<T, E> plus typed throws could remove the need for arithmetic Fallible<T> extensions. Imagine the above, where Fallible<T, E> stores T and E.Payload where E: Breakpoint. That might solve the problems I had with the typed throws approach in the early stages of this project, which was based on throws(Overflow<Self>). In this case, the Never.Payload would be some Equatable void-like thing. A call to prune() without arguments would have to throw a common error because error erasure was annoying. Like, the E type could be Bad or Never. Hm.

Note: plus(_:) -> Self.Addition is bad, but I will not explain why for free.

Note: plus(_:) throws(Overflow<Self>) -> Self is bad, but I will not explain why for free.

[oscbyspro]

I suppose there's a less intrusive alternative insofar as it does not require additional associated types. The simplest solution might simply be to write transparent protocol-based wrappers around an unchecked internal method. One that throws and one that doesn't. Hm.

[oscbyspro]

Perhaps hoisting these checks with a Natural<T> or Finite<T> trusted input model is the most flexible solution when accompanied by some ergonomic FiniteInteger extensions. If that happens to be the case, then I should probably just rename Divisor<T> as Nonzero<T>.