> On 2016-06-25, at 14:23, Nicola Salmoria via swift-evolution
> <swift-evolution@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
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
