[swift-users] A sample Rational number type

[Hooman Mehr]

> 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.

> 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. 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.

> 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. It would be nice if compiler could detect the shift loops and replace the whole loop with x86 BSFL instruction.

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.