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@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@swift.org <mailto:swift-evolution@swift.org>> wrote: > > On Jan 30, 2017, at 11:31 AM, Max Moiseev <mois...@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@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@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution
