[swift-users] A sample Rational number type

[Dave Abrahams]

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