speed of mpq_cmp vs mpq_sub
Torbjörn Granlund
tg at gmplib.org
Wed May 25 13:23:08 UTC 2016
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
More information about the gmp-discuss
mailing list