[swift-evolution] [Review] SE-0104: Protocol-oriented integers

[David Sweeris]

As someone who’ll likely make use of this protocol, I’m in favor of a “halfWidthDivide” (or whatever it’s called). As someone who’ll likely end up writing at least one type which will conform to `Integer`, I’m not looking forward to implementing 503 little functions & computed properties (although I’ll admit it’ll be worth it to get a nice integer protocol). Is there any chance the protocol be able to provide default implementations for any of the “metadata” kind of stuff?

Also, speaking of default implementations, “wouldn’t it be nice if...” we only had to define everything explicitly for `IntN`, `UIntN` and `DoubleWidth<T>`, and the compiler was smart enough to figure out that, say, `DoubleWidth<Int8>` was semantically identical to `Int16` and would automatically promote it to the native type whenever possible… That way we wouldn’t need the .gyb files to write the code for all the integer types, *and* we wouldn’t have to pay the speed penalty for having, say, "func *(Int, Int)->Int" be the same code path as "func *(DoubleWidth<DoubleWidth<DoubleWidth<Int8>>>, DoubleWidth<DoubleWidth<DoubleWidth<Int8>>>) -> DoubleWidth<DoubleWidth<DoubleWidth<Int8>>>”, *and* we’d get arbitrary-width ints for free (well, “arbitrary” in terms of powers of 2).

- Dave Sweeris

> On Jun 24, 2016, at 2:01 PM, Károly Lőrentey via swift-evolution <swift-evolution at swift.org> wrote:
> 
> The operation I want is the inverse of doubleWidthMultiply, where you have a (high, low) word pair and you want to divide it by a single word, getting a quotient and remainder. This is an important building block for implementing arbitrary precision division. Intel’s DIV can do this in a single instruction, while doing it in code requires a lot of work:
> 
> https://github.com/lorentey/BigInt/blob/swift3/Sources/BigDigit.swift#L119-L176
> 
>> On 2016-06-24, at 20:52, Haravikk <swift-evolution at haravikk.me> wrote:
>> 
>> 
>>> On 24 Jun 2016, at 18:17, Károly Lőrentey via swift-evolution <swift-evolution at swift.org> wrote:
>>> I’m especially stoked about `FixedWidthInteger.doubleWidthMultiply`, which will likely lead to a measurable speedup. Why is there no `doubleWidthQuotientAndRemainder` or `doubleWidthDivide`, though?
>> 
>> Double-width isn't needed for these as it's impossible for an integer to become larger when dividing (the smallest value you can divide by and get a result is 2, which will halve the value), and the remainder can't be larger than the original value.
>> 
>> 
>> Anyway, I'm hugely in favour of this proposal, it's desperately needed!
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution