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

[Stephen Canon]

It’s

(a) the inverse operation of doubleWidthMultiply.
(b) an important building block for fast “small bignum arithmetic” (2-16 ish words). If you have this operation, it’s easy to build the divide that does DoubleWidth<T> / DoubleWidth<T>.
(c) the widest divide operation that maps reasonably cleanly to common hardware when T = Word.

– Steve

> On Jan 31, 2017, at 6:59 AM, Nevin Brackett-Rozinsky via swift-evolution <swift-evolution at swift.org> 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 <mailto: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 <https://lists.swift.org/mailman/listinfo/swift-evolution>
> _______________________________________________
> 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/71e23b65/attachment.html>