On Mon, Jun 27, 2016 at 12:38 AM, Károly Lőrentey <kar...@lorentey.hu> wrote:
> > > 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. > 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
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution