Improved algorithms for mpq_class multiply/divide with (un)signed long integers

[Marc Glisse]

[warning: I am not a gmp maintainer]

On Tue, 13 Oct 2009, Douglas Boffey wrote:

> I have rewritten the class members (see the attached patch file) for:
[prod and div of mpq with (un)signed long]

Cool. Did you check if q=n/q (note the reuse of the variable) behaves 
properly?

> In each case, the mp operations involved (apart from trivial sign changes, etc.) are:
>
> one  gcd (N x 1)
> one integer div-exact (N x 1)
> one integer multiply (N x 1)
>
> instead of:
>
> one gcd (M x N) for canonicalising
> one integer multiply (N x 1), although only implicitly x 1

Actually, the current mpq_mul does 2 gcd, 2 mul and 4 div.

> (I don't know whether there are any performance improvements of a _ui() 
> over a non-_ui() function with a single limb in one argument.

In many cases, there is a test that redirects a non-_ui call to the same 
internal function as the _ui call, but the overhead is a bit larger. Also, 
the operations f(var,1) that you are able to skip don't come for free.

You could do the same kind of change for mpq*mpz (look for ZQ to disable 
the automatic mpz->mpq conversion for a specific operation).

Did you experiment to measure how much time you gain?

Now this is code that gets inlined everytime the function is called. 
Increasing the size of that code is thus something that should be avoided 
as much as possible. I tend to believe that if we want this kind of 
optimization, it would be better to add a mpq_mul_z function (and div_z, 
z_div and possibly _ui versions) to the C interface, and call these from 
the C++ wrapper; but that is a matter of opinion.

-- 
Marc Glisse