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\ 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>.