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

[Nicola Salmoria]

On Mon, Jun 27, 2016 at 12:38 AM, Károly Lőrentey <karoly at lorentey.hu>
wrote:

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

AbsoluteValue is currently part of the signature of doubleWidthMultiply()
in FixedWidthInteger. I suppose that moving it to SignedInteger would
require having FixedWithSignedInteger and FixedWidthUnsignedInteger, with
different signatures for the function.


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

If it's guaranteed to be free, no objections. I separated them because in
one case I need the quotient and not the remainder, and in another case the
opposite.


> (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.)
>

When the divisor is positive the check is simple, but as we have seen with
the edge case Int.min / -1, when the divisor is negative things get a lot
more complicated. So I think it's better to leave the check in the library,
allowing it to take advantage of hardware support.


>     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
>
>
Nicola
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160627/02f3ba98/attachment.html>