…rather, the remainder will fit in width min(X, Y) Nevin
On Tuesday, January 31, 2017, Nevin Brackett-Rozinsky < [email protected]> 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 < > [email protected] > <javascript:_e(%7B%7D,'cvml','[email protected]');>> wrote: > >> > On Jan 30, 2017, at 11:31 AM, Max Moiseev <[email protected]> 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 >> [email protected] >> https://lists.swift.org/mailman/listinfo/swift-evolution >> >
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
