[swift-users] A sample Rational number type
Dave Abrahams
dabrahams at apple.com
Mon Oct 3 11:08:44 CDT 2016
on Sun Oct 02 2016, Hooman Mehr <swift-users-AT-swift.org> wrote:
>> On Oct 2, 2016, at 5:23 PM, Dave Abrahams via swift-users <swift-users at swift.org> wrote:
>> Presumably you mean:
>>
>> let r2 = r±0.0005 // turn a Rational into a Double with no more than
>> // .0005 rounding error
>>
>> ? That is supercute!
>>
>
> It is actually the other way around: It returns a rational given a
> double so that the maximum difference of the created rational with the
> input double is the specified tolerance.
Oh, nifty. How about the other direction?
>> Have you thought about what this would look like after we land
>> https://github.com/apple/swift/pull/3796 (see
>> https://github.com/apple/swift-evolution/blob/master/proposals/0104-improved-integers.md)
>> ?
>>
>
> That is the next thing I want to look at, the next chance I get.
Thank you!
> For now, it isn’t much more than a quick hack on a slow Friday…
>
>> You can also find a working prototype of that code at
>>
> https://github.com/apple/swift/blob/b7622b41756e33bdf3f3415320ffec52aec73281/test/Prototypes/Integers.swift.gyb
>> It would be great to know that the protocols we've designed actually
>> work out for Rational numbers. With these protocols, can you make your
>> Rational generic on the underlying integer type?
>>
>> There's a BigInt implementation based on these protocols here:
>> https://github.com/natecook1000/swift/commit/45c52a75dcc15024649a5e093a5da4ee031595c2
>>
>> It would be really cool to see it work with a generic version of your
>> Rational type.
>
> Interesting idea. A BigInt type can really lift Rational to new
> levels. Interesting case study to see how well the new protocols work.
Quite so! [FWIW, I rather wish that BigInt was using two's complement
representation, as the protocols were designed to make that work
smoothly]
>> It's interesting to see that one wants a different algorithm for GCD
>> when using BigInts:
>> https://en.wikipedia.org/wiki/Binary_GCD_algorithm#cite_note-11
>>
>> I wonder how that should be dispatched…
>
> Moreover, there is something I ran into after posting: On today’s CPU
> architectures with fast integer divide, simple binary CGD is slower
> than basic Euler’s algorithm using remainders. Binary GCD needs the
> equivalent of __builtin_ctz to run faster.
The new integer protocols expose that as a "leadingZeros" property.
> It would be nice if compiler could detect the shift loops and replace
> the whole loop with x86 BSFL instruction.
Talk to the llvm people :-). You'll want to use masking shifts under
the new integer protocols.
> I need to put some thought on whether there is an efficient means of
> switching the algorithm based on the actual size (or nature) of the
> given Int type, otherwise we may have to specialize, which is not good
> from a generics standpoint.
It depends exactly what you mean by that term :-)
--
-Dave
More information about the swift-users
mailing list