<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="" applecontenteditable="true"><div class="">It’s</div><div class=""><br class=""></div><div class="">(a) the inverse operation of doubleWidthMultiply.</div><div class="">(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&lt;T&gt; / DoubleWidth&lt;T&gt;.</div><div class="">(c) the widest divide operation that maps reasonably cleanly to common hardware when T = Word.</div><div class=""><br class=""></div><div class="">– Steve</div><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 31, 2017, at 6:59 AM, Nevin Brackett-Rozinsky via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>&gt; wrote:</div><br class="Apple-interchange-newline"><div class="">What, exactly, is the intended purpose of doubleWidthDivide?<br class=""><br class="">I ask because, outside of degenerate cases,&nbsp;a&nbsp;quotient and remainder will fit in the same size&nbsp;type as the operands.<div class=""><br class=""></div><div class="">So widthX / widthY will have quotient that fits in width X, and remainder that fits in width Y.</div><div class=""><br class=""></div><div class="">In general, we cannot assume either one would be any smaller than that.</div><div class=""><br class=""></div><div class="">Nevin<br class=""><br class=""><br class="">On Monday, January 30, 2017, Brent Royal-Gordon via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>&gt; wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">&gt; On Jan 30, 2017, at 11:31 AM, Max Moiseev &lt;<a href="javascript:;" onclick="_e(event, 'cvml', 'moiseev@apple.com')" class="">moiseev@apple.com</a>&gt; wrote:<br class="">
&gt;<br class="">
&gt; doubleWidthDivide should not return a DoubleWidth&lt;T&gt; for two reasons:<br class="">
&gt; 1. The components of it’s return type are not high and low, but are quotient and remainder instead.<br class="">
&gt; 2. In DoubleWidth&lt;T&gt; high is T and low is T.Magnitude, which is not the case for quotient and remainder.<br class="">
<br class="">
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:<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self) -&gt; DoubleWidth&lt;Self&gt;<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; static func doubleWidthDivide(_ lhs: DoubleWidth&lt;Self&gt;, _ rhs: Self) -&gt; (quotient: Self, remainder: Self)<br class="">
<br class="">
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?<br class="">
<br class="">
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:<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; static func multiply(_ lhs: Self, by rhs: Self) -&gt; DoubleWidth&lt;Self&gt;<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; static func divide(_ lhs: DoubleWidth&lt;Self&gt;, by rhs: Self) -&gt; (quotient: Self, remainder: Self)<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; let x = Int.multiply(a, by: b)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; let (aʹ, r) = Int.divide(x, by: b)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; assert(a == aʹ)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; assert(r == 0)<br class="">
<br class="">
Should the standard library provide extensions automatic definitions of multiplication and division in terms of their double-width equivalents?<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; extension FixedWidthInteger {<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; func multipliedWithOverflow(by other: Self) -&gt; (partialValue: Self, overflow: ArithmeticOverflow) {<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; let doubledResult = Self.multiply(self, by: other)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; let overflowed = doubledResult.high != (doubledResult &lt; 0 ? -1 : 0)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return (Self(bitPattern: doubledResult.lowerValue), overflowed ? .overflowed : .none)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; func quotientAndRemainder(<wbr class="">dividingBy other: Self) -&gt; (quotient: Self, remainder: Self) {<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; precondition(other != 0, "Divide by zero")<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return Self.divide(DoubleWidth(self), by: other)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; func dividedWithOverflow(by other: Self) -&gt; (partialValue: Self, overflow: ArithmeticOverflow) {<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; guard other != 0 else { return (self, .overflowed) }<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; let result = Self.divide(self, by: other)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return (result.quotient, .none)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; static func * (lhs: Self, rhs: Self) -&gt; Self {<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; let result = lhs.dividedWithOverflow(by: rhs)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; precondition(result.overflow == .none, "Multiplication overflowed")<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return result.partialValue<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; static func / (lhs: Self, rhs: Self) -&gt; Self {<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; let result = lhs.quotientAndRemainder(<wbr class="">dividingBy: rhs)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return result.quotient<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; static func % (lhs: Self, rhs: Self) -&gt; Self {<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; let result = lhs.quotientAndRemainder(<wbr class="">dividingBy: rhs)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return result.remainder<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<br class="">
}<br class="">
<br class="">
Hmm...having actually written this out, I now have a couple of concerns:<br class="">
<br class="">
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?<br class="">
<br class="">
2. There is no quotient-and-remainder-with-<wbr class="">overflow, either regular or double-width. Can we do that?<br class="">
<br class="">
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?<br class="">
<br class="">
4. For that matter, even non-fixed-width division can "overflow"; should that concept be hoisted higher up the protocol hierarchy?<br class="">
<br class="">
5. For *that* matter, should we simply make these operations throw instead of returning a flag?<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; enum ArithmeticError&lt;NumberType: Arithmetic&gt;: Error {<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Are generic errors permitted?<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case overflow(partialValue: NumberType)<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case undefined<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; }<br class="">
<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; // Should these throwing definitions be higher up so that, when working with `Arithmetic`<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; // or similar types, you have an opportunity to handle errors instead of always trapping?<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; protocol FixedWidthInteger: BinaryInteger {<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ...<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; func adding(_ other: Self) throws -&gt; Self<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; func subtracting(_ other: Self) throws -&gt; Self<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; func multiplied(by other: Self) throws -&gt; Self<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; func divided(by other: Self) throws -&gt; Self<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ...<br class="">
&nbsp; &nbsp; &nbsp; &nbsp; }<br class="">
<br class="">
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.<br class="">
<br class="">
&gt; Having said that, there is a solution for doubleWidthMultiply, that I think is worth trying:<br class="">
&gt;<br class="">
&gt; enum DoubleWidth&lt;T&gt; {<br class="">
&gt;&nbsp; &nbsp;case .parts(high: T, low: T.Magnitude)<br class="">
&gt;<br class="">
&gt;&nbsp; &nbsp;var high: T { switch self { case .parts(let high, _): return high } }<br class="">
&gt;&nbsp; &nbsp;var low: T.Magnitude { switch self { case .parts(_, let low): return low } }<br class="">
&gt; }<br class="">
&gt;<br class="">
&gt; 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.<br class="">
<br class="">
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.)<br class="">
<br class="">
--<br class="">
Brent Royal-Gordon<br class="">
Architechies<br class="">
<br class="">
______________________________<wbr class="">_________________<br class="">
swift-evolution mailing list<br class="">
<a href="javascript:;" onclick="_e(event, 'cvml', 'swift-evolution@swift.org')" class="">swift-evolution@swift.org</a><br class="">
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" target="_blank" class="">https://lists.swift.org/<wbr class="">mailman/listinfo/swift-<wbr class="">evolution</a><br class="">
</blockquote></div>
_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></blockquote></div><br class=""></body></html>