[swift-evolution] protocol-oriented integers (take 2)

Nevin Brackett-Rozinsky nevin.brackettrozinsky at gmail.com
Tue Jan 31 06:16:12 CST 2017


…rather, the remainder will fit in width min(X, Y)

Nevin

On Tuesday, January 31, 2017, Nevin Brackett-Rozinsky <
nevin.brackettrozinsky at gmail.com> wrote:

> What, exactly, is the intended purpose of doubleWidthDivide?
>
> I ask because, outside of degenerate cases, a quotient and remainder will
> fit in the same size type as the operands.
>
> So widthX / widthY will have quotient that fits in width X, and remainder
> that fits in width Y.
>
> In general, we cannot assume either one would be any smaller than that.
>
> Nevin
>
>
> On Monday, January 30, 2017, Brent Royal-Gordon via swift-evolution <
> swift-evolution at swift.org
> <javascript:_e(%7B%7D,'cvml','swift-evolution at swift.org');>> wrote:
>
>> > On Jan 30, 2017, at 11:31 AM, Max Moiseev <moiseev at apple.com> wrote:
>> >
>> > doubleWidthDivide should not return a DoubleWidth<T> for two reasons:
>> > 1. The components of it’s return type are not high and low, but are
>> quotient and remainder instead.
>> > 2. In DoubleWidth<T> high is T and low is T.Magnitude, which is not the
>> case for quotient and remainder.
>>
>> You're right about the return value; for `doubleWidthDivide(_:_:)`, I was
>> thinking about changing the dividend. Specifically, I'm thinking we should
>> change these to:
>>
>>         static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) ->
>> DoubleWidth<Self>
>>         static func doubleWidthDivide(_ lhs: DoubleWidth<Self>, _ rhs:
>> Self) -> (quotient: Self, remainder: Self)
>>
>> I'm also thinking a little bit about spelling of these operations. I'd
>> *love* to be able to call them `*` and `/` and let the type system sort
>> things out, but that would cause problems, especially for multiply (since
>> the return value is the only thing different from a normal `*`). We could
>> invent a new operator, but that would be a bit much. Could these be simply
>> `multiply` and `divide`, and we'll permit the `DoubleWidth`
>> parameter/return type to explain itself?
>>
>> I'm also thinking the second parameter should be labeled `by`, since
>> that's the way people talk about these operations. Applying both of these
>> suggestions, we'd get:
>>
>>         static func multiply(_ lhs: Self, by rhs: Self) ->
>> DoubleWidth<Self>
>>         static func divide(_ lhs: DoubleWidth<Self>, by rhs: Self) ->
>> (quotient: Self, remainder: Self)
>>
>>         let x = Int.multiply(a, by: b)
>>         let (aʹ, r) = Int.divide(x, by: b)
>>         assert(a == aʹ)
>>         assert(r == 0)
>>
>> Should the standard library provide extensions automatic definitions of
>> multiplication and division in terms of their double-width equivalents?
>>
>>         extension FixedWidthInteger {
>>                 func multipliedWithOverflow(by other: Self) ->
>> (partialValue: Self, overflow: ArithmeticOverflow) {
>>                         let doubledResult = Self.multiply(self, by: other)
>>                         let overflowed = doubledResult.high !=
>> (doubledResult < 0 ? -1 : 0)
>>                         return (Self(bitPattern:
>> doubledResult.lowerValue), overflowed ? .overflowed : .none)
>>                 }
>>
>>                 func quotientAndRemainder(dividingBy other: Self) ->
>> (quotient: Self, remainder: Self) {
>>                         precondition(other != 0, "Divide by zero")
>>                         return Self.divide(DoubleWidth(self), by: other)
>>                 }
>>
>>                 func dividedWithOverflow(by other: Self) ->
>> (partialValue: Self, overflow: ArithmeticOverflow) {
>>                         guard other != 0 else { return (self,
>> .overflowed) }
>>
>>                         let result = Self.divide(self, by: other)
>>                         return (result.quotient, .none)
>>                 }
>>
>>                 static func * (lhs: Self, rhs: Self) -> Self {
>>                         let result = lhs.dividedWithOverflow(by: rhs)
>>                         precondition(result.overflow == .none,
>> "Multiplication overflowed")
>>                         return result.partialValue
>>                 }
>>
>>                 static func / (lhs: Self, rhs: Self) -> Self {
>>                         let result = lhs.quotientAndRemainder(dividingBy:
>> rhs)
>>                         return result.quotient
>>                 }
>>
>>                 static func % (lhs: Self, rhs: Self) -> Self {
>>                         let result = lhs.quotientAndRemainder(dividingBy:
>> rhs)
>>                         return result.remainder
>>                 }
>> }
>>
>> Hmm...having actually written this out, I now have a couple of concerns:
>>
>> 1. There's a lot of jumping back and forth between instance methods and
>> static methods. Can we standardize on just static methods? Or make sure
>> that the user-facing interfaces are all either operators or instance
>> methods?
>>
>> 2. There is no quotient-and-remainder-with-overflow, either regular or
>> double-width. Can we do that?
>>
>> 3. "Overflow" is not really a good description of what's happening in
>> division; the value is undefined, not overflowing. Is there a better way to
>> express this?
>>
>> 4. For that matter, even non-fixed-width division can "overflow"; should
>> that concept be hoisted higher up the protocol hierarchy?
>>
>> 5. For *that* matter, should we simply make these operations throw
>> instead of returning a flag?
>>
>>         enum ArithmeticError<NumberType: Arithmetic>: Error {
>>                 // Are generic errors permitted?
>>                 case overflow(partialValue: NumberType)
>>                 case undefined
>>         }
>>
>>         // Should these throwing definitions be higher up so that, when
>> working with `Arithmetic`
>>         // or similar types, you have an opportunity to handle errors
>> instead of always trapping?
>>         protocol FixedWidthInteger: BinaryInteger {
>>                 ...
>>                 func adding(_ other: Self) throws -> Self
>>                 func subtracting(_ other: Self) throws -> Self
>>                 func multiplied(by other: Self) throws -> Self
>>                 func divided(by other: Self) throws -> Self
>>                 ...
>>         }
>>
>> I'm *really* tempted to suggest adding throwing variants of the actual
>> operators (strawman example: `^+`, `^-`, `^*`, `^/`, `^%`), but they may be
>> too specialized to really justify that.
>>
>> > Having said that, there is a solution for doubleWidthMultiply, that I
>> think is worth trying:
>> >
>> > enum DoubleWidth<T> {
>> >   case .parts(high: T, low: T.Magnitude)
>> >
>> >   var high: T { switch self { case .parts(let high, _): return high } }
>> >   var low: T.Magnitude { switch self { case .parts(_, let low): return
>> low } }
>> > }
>> >
>> > This way it will be possible to both do pattern-matching on the result
>> of doubleWidthMultiply, and use it as a whole, accessing r.high and r.low
>> when needed.
>>
>> This sounds like a good idea to me. (Unless we want to create a protocol
>> for destructuring, but I assume that's out of scope.)
>>
>> --
>> Brent Royal-Gordon
>> Architechies
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170131/a65e9eda/attachment.html>


More information about the swift-evolution mailing list