two questions on GMP & C float

[Marc Glisse]

On Sat, 16 May 2009, Sylvain Pion wrote:

> interval arithmetics library is switching FPU rounding mode down. Does GMP 
> use FPU or may I leave rounding mode set to "down" for the interval 
> arithmetics library to work even during calls to GMP?

I believe that in the few cases where GMP uses floats, it only uses exact 
computations on those and the rounding mode is irrelevant (this may not be 
true if you have some non-IEEE double type not using base 2, but I don't 
expect that to be the case).

>> Another question. If I know beforehand that the floats I am converting to 
> mpq have some right mantissa bits cleared, will the mpq numbers be faster?

The conversion from double to mpq basically copies the bits in the 
mantissa as a group, and then removes the tailing zeros 1 by 1 (the last 
part is the easiest to optimize for you, there are faster ways to count 
the trailing zeros when you expect there may be more than 1 or 2). You can 
always copy the code from extract-dbl.c, optimize it for your case (remove 
the last 40 zeros at once) and benchmark the result, but I would be 
surprised if the conversion from float (or are they half-floats ?) to mpq 
was hot enough in your code that the gain would be noticable. Did you 
profile this?

> Will the mpq representation use less bits?

The representation is the unique reduced form.

> In the case of a float, there is a big chance that lots of zeros will end
> up in the denominator or the numerator, because one of them will have
> a large power of 2 factor.  Just consider 3.1415 as mpq.

That is quite a different issue though. These 0s are useful.

> I have the same application as Vojtěch, geometric predicates, which are
> usually signs of polynomial expressions with machine floats as input.
> The ideal way to compute these exactly is IMO to use MPFR instead of mpq_t.
>
> Of course, once you use a division, you will need a rational type, so MPFR
> is not enough, but maintaining a quotient of 2 "exact" MPFR will at least
> compress the zeroes, which an mpq does not.

mpfr/mpz, so you have only one exponent? Or does using mpfr/mpfr reduce 
the length of the code?

I was just thinking:

assume the parameters are all integers and your predicate is a polynomial 
with integer coefficients. Since you used interval arithmetics first, in 
the few cases where you are doing the exact computation, you know the 
result is going to be close to 0 (and you have a bound on that). You could 
thus do the computations modulo some slightly larger number (a power of 
2^64 for instance, an unsigned long may even be sufficient in some cases). 
I don't know how hard that would be in your case, as the parameters are 
not integers, and there are often divisions since noone is very fond of 
the homogeneous kernel :-(

> This is why I recently raised on the MPFR list the idea to add functions
> dedicated to exact "polynomial" operations to MPFR (not that those are
> hard to implement outside MPFR, of course).

What you are asking for is an exact ring and an exact field based on mpz 
and mpq multiplied by a power of 2 (and stored in canonical form with only 
odd integers, except possibly for 0).

I don't think this fits with the goals of mpfr (where is the *R*ounding?). 
If anything, it would fit better within gmp (than it would fit with mpfr 
or even than mpf fits with gmp)...

-- 
Marc Glisse