[swift-evolution] protocol-oriented integers (take 2)
Nevin Brackett-Rozinsky
nevin.brackettrozinsky at gmail.com
Tue Jan 31 05:59:59 CST 2017
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> wrote:
> > On Jan 30, 2017, at 11:31 AM, Max Moiseev <moiseev at apple.com
> <javascript:;>> 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 <javascript:;>
> 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/14b4d8d3/attachment.html>
More information about the swift-evolution
mailing list