Generic implementation

[KlausC]

I don't understand the close-to-equal implementation files FastQ32/64.
It would be easy to have a single file, which defines everything in a generic manner.

That would also enable Int128 and BigInt base types.

The base type T in struct FastRational should be restricted to <:Signed.

Int32/Int64 could be replaced by generic T/widen(T) in all methods.

[JeffreySarnoff]

Int128 and BigInt cannot be fast because they do not widen() to a fast integer type.
Other functions can be unified -- they are not now just to make sure everything worked, I developed for one type and then replicated the file after some subtle issue with one of the generic defs occured.

[KlausC]

Int128 and BigInt cannot be fast

my impression was, that your implementation is faster than Rational because the number of calls to gcd is reduced. That would also count for Int128 and BigInt.

I developed for one type and then replicated the file after some subtle issue with one of the generic defs occured

You know, that code duplication is not state of the art :-). Maybe I could help investigating the subtle issues.

[JeffreySarnoff]

Thanks. I will reintegrate tonight on a dev branch and see if it work now.

[JeffreySarnoff]

Re Int128 and BigInt, yes .. however .. that would qualify as FasterRationals and not FastRationals because they widen to BigInt. My earlier implementation would be appropriate for them. That's the one where you found the inv issue. I think this is a two stage process. Get this implementation as clean as can be (no dup code, and whatever else). Then use the two-state type that knows if its reduced.
The fast comes from from fewer gcd's in two ways .. the current implementation uses one of them, as it does not know whether the rational is in reduced form or not.

[JeffreySarnoff]

@KlausC ok .. master is now generic. Note that the 128bit type is faster than the default -- 1.5x..2x only.
please give it a once-over.

I get

        relative speeds
         (32)    (64)    (128)

mul:     25.5    22.8    2.4
muladd:  21.7    18.8    1.9
add:     18.5    16.5    1.6
poly:    14.3    23.9    2.0
matmul:  11.9    15.0    1.8
matlu:   5.7     6.3     1.7
matinv:  3.7     2.7     1.1

[KlausC]

Int128 and BigInt, yes .. however .. that would qualify as FasterRationals and not FastRationals

Playing around, it was difficult to find examples, which don't overflow FastQR64 . That is the same for Rational{Int64} . There is a tendency for the components of rational numbers to blow up after quite a few elementary operations. So I don't see the important use cases, except for BigInt as the base type.

For example:
A = rand(-1:1, 20,20); AR = Rational.(A); AF = FastQ64.(A); @btime inv(AR); @btime inv(AF)

That gives a time factor of 2.
But for 30x30 you get overflow for Int64 and time factor 0.32 for Int128.

[JeffreySarnoff]

yes -- its always that way with Rationals.
In light of this, the current master supports FastQbig (FastRational{BigInt}) and they do outperform Rational{BigInt} 2x..4x on a few different tasks.
Your help has been good to have. Thanks again.