speed of mpq_cmp vs mpq_sub

[Torbjörn Granlund]

paul zimmermann <Paul.Zimmermann at inria.fr> writes:

  if I understand correctly, you propose to compute the partial quotients of
  a/b and c/d in parallel, and stop as soon as two partial quotients differ?
  
  sage: continued_fraction(113/354)
  [0; 3, 7, 1, 1, 7]
  sage: continued_fraction(98/307)
  [0; 3, 7, 1, 1, 6]
  
That's the general idea.

And then one needs to keep track of the parity of the sequence number to
tell which number is greater.  (Here, the 2nd number is greater as
difference happens at an odd step and 7>6.)

  However in the worst-case, this will cost O(M(n) log(n)), assuming a fast
  algorithm, whereas the cross product a*d-b*c would cost O(M(n)) only. Thus
  you should stop the partial quotient computation at 1/log(n) of the total
  size (or before if using a quadratic continued fraction algorithm).
  
I'd have assumed that the gcd experts would have gotten rid of that
pesky log factor by now!

(Yes, sure one would need to get just some number of quotients and then
return to cross multiplying.)

-- 
Torbjörn
Please encrypt, key id 0xC8601622