[swift-evolution] [Review] SE-0104: Protocol-oriented integers

[Károly Lőrentey]

> On 2016-06-25, at 14:23, Nicola Salmoria via swift-evolution <swift-evolution at swift.org> wrote:
> The first comment I have to make is that, as has already been noted by plx,
> the Arithmetic protocol looks like a "bag of syntax" with loose semantics
> attached. It will be used by signed integers, unsigned integers (naturals),
> floating point numbers; and is an obvious conformance for a Rational type as
> well.
> In the proposal, there is no indication of the expected semantics of the
> four basic operations.
> - Are addition and multiplication commutative?
> - Is multiplication distributive over addition?
> - Is 'rhs != 0' a precondition for division?
> - Presumably associativity must match the associativity of the operators.
> - What is (a / b) * b?
> - Is T(exactly: n) * x guaranteed to be == (x + ... + x) n times?

I’m not sure if this has been mentioned yet, but the semantics of Integer operations also needs to be tied down. In particular, the expected behavior of the remainder operation (in all forms) when given a negative numerator and/or denumerator should be explicitly spelled out.

> Now about the AbsoluteValue associatedtype, which several other people have
> already shown doubts about.
> I found it useful, precisely for the reason stated in the proposal
> (generating the description of a Rational). However, it seems to be mostly
> an implementation detail, used to:
> 1) work around the fact that -Int.min isn't representable in two's complement;
> 2) provide a way to get the unsigned version of an integer type, to be used
> by the doubleWidthMultiply() return type.
> 
> These uses suggest that the Integer protocol might not be the best place for
> this associatedtype: both of the use cases above would not apply to a
> BigInt. It seems more appropriate for it to be part of FixedWidthInteger.
> It might even make sense to rename it UnsignedSelf, to make it clear that
> it's intended to be the unsigned equivalent of Self.

I think absoluteValue would be a better fit in SignedInteger or SignedArithmetic. But if implementation experience suggests it should be in Integer, I don’t mind including AbsoluteValue as an alias to Self (or BigUInt) in the BigInt case.

I’m also a bit suspicious of Integer's static isSigned property. What is its intended usecase? Why do we need it, given that we also have SignedInteger/UnsignedInteger protocols? (Does it ever make sense to implement Integer without also implementing SignedInteger or UnsignedInteger?)

> I also join Karoly's request for double-width division operations. In
> particular I would suggest:
> 
> static func doubleWidthDivideWithOverflow(_ lhs: (high: Self, low:
> AbsoluteValue), by rhs: Self) -> (partialValue: Self, overflow:
> ArithmeticOverflow)
> 
> static func doubleWidthRemainder(_ lhs: (high: Self, low: AbsoluteValue), by
> rhs: Self) -> Self
> 
> Note that I needed to use static members here, because the first argument of
> the division is not Self. Alternatively, the result of doubleWidthMultiply()
> could be a struct, so that double-width division operations could be members
> of that struct.

I suggest to combine generation of the quotient and remainder into a single division operation. (The implementations I know of provide both, so it makes sense to combine them.)

    static func doubleWidthDivide(_ numerator: (high: Self, low: AbsoluteValue), by denumerator: Self) -> (partialQuotient: Self, remainder: Self, overflow: ArithmeticOverflow)

A more spoon-feeding name would be “doubleWidthQuotientAndRemainderWithOverflow(dividing:, by:)”, but yuck.

(I’d personally also be fine with simplifying this by requiring that the division not overflow, i.e., that lhs.high < rhs (assuming rhs > 0), and treating overflow as a precondition failure. I know Rational's addition needs to handle overflow, but perhaps it would be OK to move this check outside the function? I imagine the code is already full of branches like that.)

    static func doubleWidthDivide(_ numerator: (high: Self, low: AbsoluteValue), by denumerator: Self) -> (quotient: Self, remainder: Self)

> These operations are difficult to implement, and are very useful.

The difficulty of their implementation might be a problem for people who want to implement FixedWidthInteger outside stdlib, but don’t care about supporting bignums or rationals. (Is that usecase desirable?) I think it would be possible to provide a divide-n-conquer default implementation for double-width division and multiplication, like the code I linked to earlier. However, without support for splitting a FixedWidthInteger into two narrower halves, the code for this would have to use nthWord, which would essentially involve implementing half of a bigint library. :-/

-- 
Karoly
@lorentey