CoCoA » CoCoALib

I have implemented a variant of myIsRational which uses SimplestBigRatBetween. The implementation is certainly much shorter than the current impl.

However a speed test indicates that explicitly reimplementing the algorithm is about 3 times faster when all rationals to be recovered are quite simple (all rationals of the form N/D with N and D coprime and less than some bound -- I used 400 as the bound).

Frankly, I'm astonished. I had expected calling SimplestBigRatBetween to be just a little slower for such simple fractions (because of the overhead of converting floats to exact rationals). I also expect SimplestBigRatBetween to be faster when the rationals to be recovered are more complicated (so the internal loop makes more iterations).

Now I'm puzzled.

I have just tried a speed test with more complicated rationals (all of the form p1/p2 where p1 and p2 are distinct 10-digit primes). Strangely this was even more favourable for the float approach over calling SimplestBigRatBetween. I'd better look at the code of SimplestBigRatBetween, sigh!

NOTE: the times were 2.7s for "float", and 11.2s for SimplestBigRatBetween -- makes no sense! :-(

I have just tried another timing test with a list of about 90000 copies of fibonacci(400)/fibonacci(401) mapped into RingTwinFloat(280).

I measured about 54s using "floats", against 360s using SimplestBigRatBetween. That's almost a factor of 7 in favour of "floats"... I'm amazed (actually disbelieving).

The source code for SimplestBigRatBetween looks to be fine: it uses ContFracIter so ought to avoid any wasteful computation. Time for some tedious profiling... sigh!

One possible explanation for ContFracIter being so slow is that its implementation is "very clean" (e.g. it uses BigRat values internally). Perhaps once we impl "move operators" the situation will improve (but I'd be amazed to see a factor of 7 improvement).