Re: mpq_cmp_z
My mistake: it is gmp.h is autogenerated so I just had to rerun ./configure. Please forget about my question! Vincent On 02/11/15 11:17, Vincent Delecroix wrote: Hola, A quick question: why mpq_cmp_z is declared in gmpxx.h but not in gmp.h? Vincent On 03/09/15 17:04, Vincent Delecroix wrote: Ciao Marco, On 02/09/15 02:44, Marco Bodrato wrote: Ciao Vincent, Il Sab, 15 Agosto 2015 12:37 pm, Vincent Delecroix ha scritto: Dear all, I am new to this list. I am a regular developer of the SageMath project [1] in which we use mpz_t and mpq_t as our based type for integers and rationals. We often have to compare integers with rationals and I came to the conclusion that it would be convenient to have a GMP function int mpq_cmp_z(mpq_t, mpz_t) We now have this function in our repository: https://gmplib.org/repo/gmp/rev/c95f8df2b57e Great! Thanks so much to all of you for making this new function exists. It shares most of the code with the already existing mpq_cmp function. If you have the possibility to test if it fits your needs (both on the speed side and for the interface) we will be happy to know. I will! Best regards, Vincent ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Hola, A quick question: why mpq_cmp_z is declared in gmpxx.h but not in gmp.h? Vincent On 03/09/15 17:04, Vincent Delecroix wrote: Ciao Marco, On 02/09/15 02:44, Marco Bodrato wrote: Ciao Vincent, Il Sab, 15 Agosto 2015 12:37 pm, Vincent Delecroix ha scritto: Dear all, I am new to this list. I am a regular developer of the SageMath project [1] in which we use mpz_t and mpq_t as our based type for integers and rationals. We often have to compare integers with rationals and I came to the conclusion that it would be convenient to have a GMP function int mpq_cmp_z(mpq_t, mpz_t) We now have this function in our repository: https://gmplib.org/repo/gmp/rev/c95f8df2b57e Great! Thanks so much to all of you for making this new function exists. It shares most of the code with the already existing mpq_cmp function. If you have the possibility to test if it fits your needs (both on the speed side and for the interface) we will be happy to know. I will! Best regards, Vincent ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao Marco, On 02/09/15 02:44, Marco Bodrato wrote: Ciao Vincent, Il Sab, 15 Agosto 2015 12:37 pm, Vincent Delecroix ha scritto: Dear all, I am new to this list. I am a regular developer of the SageMath project [1] in which we use mpz_t and mpq_t as our based type for integers and rationals. We often have to compare integers with rationals and I came to the conclusion that it would be convenient to have a GMP function int mpq_cmp_z(mpq_t, mpz_t) We now have this function in our repository: https://gmplib.org/repo/gmp/rev/c95f8df2b57e Great! Thanks so much to all of you for making this new function exists. It shares most of the code with the already existing mpq_cmp function. If you have the possibility to test if it fits your needs (both on the speed side and for the interface) we will be happy to know. I will! Best regards, Vincent ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes: I know, but when you write conditions like (a>b) you don't just have to test the two cases (a>b) and (ahttps://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao, Il Gio, 3 Settembre 2015 11:14 am, Torbjörn Granlund ha scritto: > "Marco Bodrato" writes: > PS: I'm not very happy for the testing code... too general to finely > explore the corner cases for the size-based branches... > All branches except the SALLOC/BALLOC ones hiding under TMP_* seem to be > covered: https://gmplib.org/devel/lcov/shell/gmp/mpq/cmp.c.gcov.html I know, but when you write conditions like (a>b) you don't just have to test the two cases (a>b) and (ahttp://bodrato.it/ ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes: PS: I'm not very happy for the testing code... too general to finely explore the corner cases for the size-based branches... All branches except the SALLOC/BALLOC ones hiding under TMP_* seem to be covered: https://gmplib.org/devel/lcov/shell/gmp/mpq/cmp.c.gcov.html -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao Vincent, Il Sab, 15 Agosto 2015 12:37 pm, Vincent Delecroix ha scritto: > Dear all, > > I am new to this list. I am a regular developer of the SageMath project > [1] in which we use mpz_t and mpq_t as our based type for integers and > rationals. We often have to compare integers with rationals and I came > to the conclusion that it would be convenient to have a GMP function > > int mpq_cmp_z(mpq_t, mpz_t) We now have this function in our repository: https://gmplib.org/repo/gmp/rev/c95f8df2b57e It shares most of the code with the already existing mpq_cmp function. If you have the possibility to test if it fits your needs (both on the speed side and for the interface) we will be happy to know. I hope its name will not be changed before the official release, but be warned, it is not official yet. Best regards, m PS: I'm not very happy for the testing code... too general to finely explore the corner cases for the size-based branches... -- http://bodrato.it/papers/ ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes: The code with this signature is attached. LGTM. But it is in some sense asymmetric, if you call mpq_cmp(A,B) and B happens to be an integer, the code exploits it. If only A is an integer, the code will not detect nor exploit the information. We presumably don't detect "integrity" in other mpq functions where this could streamline things. I think we can live with the slight asymetry in this function... -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Lazy mpz allocation (Was: Re: mpq_cmp_z)
"Marco Bodrato" writes:
If we change (I'd agree) mpz_init into
void
mpz_init (mpz_ptr x)
{
ALLOC (x) = 0; /* ZERO, any MPZ_REALLOC will allocate */
PTR (x) = & static_const_limb_shared_by_all_instances;
SIZ (x) = 0;
}
I suppose we should do this!
(consequently we will have to change all functions that write a single
limb, pre-pending an MPZ_REALLOC(var,1) )
I suppose this is just in a few places, but it might not to easy to find
them.
--
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes: > At any point in mpq code (we check in the _init functions, and we ASSERT > elsewhere) we assume denominator is strictly positive and mpz's are > normalised. And hence, in this case, PTR(den)[0] is not only readable, but it always contains a meaningful value. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao,
Il Mer, 26 Agosto 2015 6:26 pm, Torbjörn Granlund ha scritto:
> ni...@lysator.liu.se (Niels Möller) writes:
> > (SIZ(den) | PTR(den)[0]) == 1
>
> I think it is correct, assuming that at this point in the code it is
> known that SIZ(den) != 0 (and that den is normalized, so that SIZ(den)
At any point in mpq code (we check in the _init functions, and we ASSERT
elsewhere) we assume denominator is strictly positive and mpz's are
normalised.
> Indeed a clever condition, helping Marco's quest against branches, a
> condition which also depends on that we always allocate a limb at
> PTR(mpz).
It depends only on being able to _read_ PTR(mpz)[0].
If we change (I'd agree) mpz_init into
void
mpz_init (mpz_ptr x)
{
ALLOC (x) = 0; /* ZERO, any MPZ_REALLOC will allocate */
PTR (x) = & static_const_limb_shared_by_all_instances;
SIZ (x) = 0;
}
(consequently we will have to change all functions that write a single
limb, pre-pending an MPZ_REALLOC(var,1) )
That condition will keep on being valid. The same holds for
#define mpz_odd_p(z) (((z)->_mp_size!=0)&__GMP_CAST(int,(z)->_mp_d[0]))
that we wrote a dozen years ago in gmp-h.in .
Regards,
m
--
http://bodrato.it/
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
ni...@lysator.liu.se (Niels Möller) writes:
"Marco Bodrato" writes:
> My idea is to check if the den{ominator} is one by checking this condition:
>
> (SIZ(den) | PTR(den)[0]) == 1
I think it is correct, assuming that at this point in the code it is
known that SIZ(den) != 0 (and that den is normalized, so that SIZ(den)
== 1 implies that PTR(den)[0] != 0).
Indeed a clever condition, helping Marco's quest against branches, a
condition which also depends on that we always allocate a limb at
PTR(mpz).
--
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes:
> My idea is to check if the den{ominator} is one by checking this condition:
>
> (SIZ(den) | PTR(den)[0]) == 1
I think it is correct, assuming that at this point in the code it is
known that SIZ(den) != 0 (and that den is normalized, so that SIZ(den)
== 1 implies that PTR(den)[0] != 0).
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
NUM(op1)), num1_size,
PTR(den_op2), den2_size);
else
tmp1_size -= 0 == mpn_mul (tmp1_ptr,
PTR(den_op2), den2_size,
PTR(NUM(op1)), num1_size);
}
if (num2_size >= den1_size)
tmp2_size -= 0 == mpn_mul (tmp2_ptr,
PTR(num_op2), num2_size,
PTR(DEN(op1)), den1_size);
else
tmp2_size -= 0 == mpn_mul (tmp2_ptr,
PTR(DEN(op1)), den1_size,
PTR(num_op2), num2_size);
cc = tmp1_size - tmp2_size != 0
? tmp1_size - tmp2_size : mpn_cmp (tmp1_ptr, tmp2_ptr, tmp1_size);
TMP_FREE;
return num1_sign < 0 ? -cc : cc;
}
int
mpq_cmp (mpq_srcptr op1, mpq_srcptr op2)
{
return mpq_cmp_numden (op1, NUM(op2), DEN(op2));
}
int
mpq_cmp_z (mpq_srcptr op1, mpz_srcptr op2)
{
const static mp_limb_t one = 1;
const static mpz_t den = MPZ_ROINIT_N ((mp_limb_t *) &one, 1);
return mpq_cmp_numden (op1, op2, den);
}___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes: If you pass NULL, you'll not avoid any pesky branch :-D Indeed. If you pass a static "1", and do not branch, you will end up allocating space and loosing time to multiply NUM(op1) by one... My idea was to have a file-local mpz_struct, which could be checked for in the helper to suppress *some* of the more expensive operations. Or not. I am less eager to mess up mpq than e.g. mpn for the sake of performance. Suppressing all denomonator ops for op2=mpz seem like overkill, and then we might as well reimplement mpq_cmp_z. We should remember that mpq programs will spend almost all time in gcd computations anyway. :-) -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes: > If you pass NULL, you'll not avoid any pesky branch :-D > > If you pass a static "1", and do not branch, you will end up allocating > space and loosing time to multiply NUM(op1) by one... Depends on whether or not we want to recognize the integer case also for mpq_cmp. I think it would make some sense to do that. And if so, passing a static "1" for mpq_cmp_z seems right, because then no additional branch is needed for that case. As I understand tail call machinery, to really get a tail call, the calling functions (mpq_cmp and mpq_cmp_z) mustn't pass any stack-allocated pointers to mpq_cmp_helper. > If we want to share code and we don't want to penalise the _z flavour too > much, some branches are needed. Is there a lot shared logic? For the integer case, we compare A/B to C, by first checking signs and sizes, and for close sizes, compare B*C to A (or ideally, only one or two of the high limbs of the product). While for the non-integer case, A/B vs C/D, it seems to me that sign logic would be the same, but size comparisons are different (limb size of A known exactly, while limb size of A*D has one unit of uncertainty). Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao, On Mon, August 24, 2015 6:24 pm, Torbjörn Granlund wrote: > An alternative to messing with void * would be an interface like this: > static int > cmp_helper (mpq_srcptr op1, mpz_srcptr op2num, mpz_srcptr op2den) I tested this one: cmp_helper (mpq_srcptr o1, mpz_srcptr o2n, mpz_srcptr o2d, mp_size_t o2s) obtaining a "slow" alternative. I'll try your proposal. > Then have mpq_cmp simply split its op2 arg before dropping into the > helper function, and mpz_cmp_z pass its 2nd arg as op2num, and then ether > pass a global static op2den which is compile-time initialised to 1, or > perhaps pass NULL. > That'd allow tail calls for most machines, and should not need many > pesky branches. If you pass NULL, you'll not avoid any pesky branch :-D If you pass a static "1", and do not branch, you will end up allocating space and loosing time to multiply NUM(op1) by one... One of the four branches I originally wrote can be avoided by better coding... If we want to share code and we don't want to penalise the _z flavour too much, some branches are needed. Regards, m -- http://bodrato.it/papers/ ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes: On Fri, August 21, 2015 10:36 pm, Marco Bodrato wrote: > Maybe changing the prototype of mpq_cmp_maybe_z to > int mpq_cmp_maybe_z (mpq_srcptr op1, const void *op2, int op2_is_mpz) ... no, void * is a nonsense ... Maybe the attached version is better, it uses the cast (mpz_srcptr) op2 when the numerator is needed, and a plain DEN(op2) to access the denominator if it is available. (Being busy, therefore slow to read code.) An alternative to messing with void * would be an interface like this: static int cmp_helper (mpq_srcptr op1, mpz_srcptr op2num, mpz_srcptr op2den) ... Then have mpq_cmp simply split its op2 arg before dropping into the helper function, and mpz_cmp_z pass its 2nd arg as op2num, and then ether pass a global static op2den which is compile-time initialised to 1, or perhaps pass NULL. That'd allow tail calls for most machines, and should not need many pesky branches. -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
2_ptr, tmp1_size);
TMP_FREE;
return num1_sign < 0 ? -cc : cc;
}
int
mpq_cmp (mpq_srcptr op1, mpq_srcptr op2)
{
mp_size_t den2_size = SIZ(DEN(op2));
ASSERT (den2_size > 0);
if ((den2_size | PTR(DEN(op2))[0]) == 1)
den2_size = 0;
return mpq_cmp_maybe_z (op1, op2, den2_size);
}
int
mpq_cmp_z (mpq_srcptr op1, mpz_srcptr op2)
{
return mpq_cmp_maybe_z (op1, (mpq_srcptr) op2, 0);
}___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao, Sorry Vincent, you suggested a simple function and received back a technical discussion about casting in C... On Fri, August 21, 2015 8:56 am, Torbjörn Granlund wrote: > not, I've forgotten this level of detail of the C standard. I am not > too enthusiastic about passing the wrong type, but if we add casts both > when going to &mpq and when going back to &mpz, I cannot see how that > could break with a conforming compiler. Maybe changing the prototype of mpq_cmp_maybe_z to int mpq_cmp_maybe_z (mpq_srcptr op1, const void *op2, int op2_is_mpz) so that we can pass to it either an mpq_srcptr or an mpz_srcptr, then replace occurrences of NUM(op2) with ((mpz_srcptr) op2), and occurrences of DEN(op2) with DEN((mpq_srcptr) op2)... Regards, m -- http://bodrato.it/papers/ ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
On Fri, 21 Aug 2015, Torbjörn Granlund wrote: "Marco Bodrato" writes: Maybe we can "promise" the right type, by adding an explicit cast? SIZ((mpz_srcptr) NUM(op2)) Except that we should cast op2, not NUM(ops). I am not sure Marc's reasoning is accurate, nor am I suggesting it is not, I've forgotten this level of detail of the C standard. I am not too enthusiastic about passing the wrong type, but if we add casts both when going to &mpq and when going back to &mpz, I cannot see how that could break with a conforming compiler. Good point. I agree that (mpz_srcptr)op2 is a safer way to do the same thing as NUM(op2) in this case. (I am not suggesting changing the gmp-impl implementation of NUM to a cast) -- Marc Glisse ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes:
Maybe we can "promise" the right type, by adding an explicit cast?
SIZ((mpz_srcptr) NUM(op2))
Except that we should cast op2, not NUM(ops).
I am not sure Marc's reasoning is accurate, nor am I suggesting it is
not, I've forgotten this level of detail of the C standard. I am not
too enthusiastic about passing the wrong type, but if we add casts both
when going to &mpq and when going back to &mpz, I cannot see how that
could break with a conforming compiler.
> > (We might consider adding mpf_cmp_z too, at least in a simple-minded
> > manner, to keep the GMP interface as orthogonal as possible.)
> Adding new mpf_t functions might confuse the message that people should
> use mpfr...
We can silently add it to the manual without claiming it in the release
announce :-)
Or deny that we added it?
A tenth of lines of code should be enough, shouldn't it?
int
mpf_cmp_z (mpf_srcptr u, mpz_srcptr v) __GMP_NOTHROW
{
mpf_t vf;
mp_size_t size;
SIZ (vf) = size = SIZ (v);
EXP (vf) = size = ABS (size);
/* PREC (vf) = size; */
PTR (vf) = PTR (v);
return mpf_cmp (u, vf);
}
It looks about right. The code for mpf_set_z should provides a pattern,
except that its conditionally truncattion is not needed.
--
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
On Fri, 21 Aug 2015, Marco Bodrato wrote: On Thu, August 20, 2015 9:56 am, Marc Glisse wrote: Is casting an mpz to an mpq, then accessing only the NUM() part of it, portable? From what I understand of the aliasing model currently used by gcc, to be safe, in the function using it, we should have: mpz_srcptr op2n = NUM(op2); and then use SIZ(op2n) instead of directly SIZ(NUM(op2)). The reason is "x=op2->_mp_den._mp_size" promises that op2 points to a __mpq_struct while "x=op2n->_mp_size" only promises a __mpz_struct (and gcc folds *& Maybe we can "promise" the right type, by adding an explicit cast? SIZ((mpz_srcptr) NUM(op2)) I think that cast would be ignored, you really want them in separate expressions. Another thing I forgot: computing DEN(op2) could also be illegal unless the layout of __mpq_struct is the same as __mpz_struct[2], in which case we are computing the "past-the-end" pointer of the mpz_t, which is ok. Anyway, I was just trying to think of potential issues with the code, feel free to ignore it as long as nobody reports an issue with it. -- Marc Glisse ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao,
On Thu, August 20, 2015 9:56 am, Marc Glisse wrote:
> > Is casting an mpz to an mpq, then accessing only the NUM() part of it,
> > portable?
> From what I understand of the aliasing model currently used by gcc, to
> be safe, in the function using it, we should have:
> mpz_srcptr op2n = NUM(op2);
> and then use SIZ(op2n) instead of directly SIZ(NUM(op2)). The reason is
> "x=op2->_mp_den._mp_size" promises that op2 points to a __mpq_struct
> while "x=op2n->_mp_size" only promises a __mpz_struct (and gcc folds *&
Maybe we can "promise" the right type, by adding an explicit cast?
SIZ((mpz_srcptr) NUM(op2))
> > (We might consider adding mpf_cmp_z too, at least in a simple-minded
> > manner, to keep the GMP interface as orthogonal as possible.)
> Adding new mpf_t functions might confuse the message that people should
> use mpfr...
We can silently add it to the manual without claiming it in the release
announce :-)
A tenth of lines of code should be enough, shouldn't it?
int
mpf_cmp_z (mpf_srcptr u, mpz_srcptr v) __GMP_NOTHROW
{
mpf_t vf;
mp_size_t size;
SIZ (vf) = size = SIZ (v);
EXP (vf) = size = ABS (size);
/* PREC (vf) = size; */
PTR (vf) = PTR (v);
return mpf_cmp (u, vf);
}
Best regards,
m
--
http://bodrato.it/
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
On Thu, 20 Aug 2015, Marco Bodrato wrote: Is casting an mpz to an mpq, then accessing only the NUM() part of it, portable? From what I understand of the aliasing model currently used by gcc, to be safe, in the function using it, we should have: mpz_srcptr op2n = NUM(op2); and then use SIZ(op2n) instead of directly SIZ(NUM(op2)). The reason is that as long as you are only doing pointer arithmetic (NUM counts as pointer arithmetic), the exact type is kind of irrelevant (size matters as a multiplicative factor, and alignment because it can make the result invalid, but that's it), but as soon as you actually use it (load or store), you are making a promise that the type is right. So "x=op2->_mp_den._mp_size" promises that op2 points to a __mpq_struct while "x=op2n->_mp_size" only promises a __mpz_struct (and gcc folds *& to nothing very early, so it sees SIZ(NUM(op2)) as the first expression). Note that my understanding could be wrong, and other compilers could have a different model. In practice, I doubt your code would fail, but with the generalization of link-time optimizations, the library and user code are not hidden from each other anymore, and surprising things could happen. The cast itself seems fine: "A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning." On Thu, 20 Aug 2015, Torbjörn Granlund wrote: (We might consider adding mpf_cmp_z too, at least in a simple-minded manner, to keep the GMP interface as orthogonal as possible.) Adding new mpf_t functions might confuse the message that people should use mpfr... -- Marc Glisse ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes: Maybe I've found a good sharing strategy... I'll take a proper look later. One idea which could perhaps avoid some branch is if you accepted a den_size argument for the "maybe" function. (We might consider adding mpf_cmp_z too, at least in a simple-minded manner, to keep the GMP interface as orthogonal as possible.) -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao,
On Sun, August 16, 2015 11:50 pm, Torbjörn Granlund wrote:
> On Sat, August 15, 2015 12:37 pm, Vincent Delecroix wrote:
> > it would be convenient to have a GMP function
> >
> > int mpq_cmp_z(mpq_t, mpz_t)
> We might consider some code sharing between the mpq_cmp and this
> function, they look very similar.
Maybe I've found a good sharing strategy...
static int
mpq_cmp_maybe_z (mpq_srcptr op1, mpq_srcptr op2, int op2_is_mpz)
{
...
}
int
mpq_cmp (mpq_srcptr op1, mpq_srcptr op2)
{
ASSERT (SIZ(DEN(op2) != 0));
return mpq_cmp_maybe_z (op1, op2,
(SIZ(DEN(op2)) | PTR(DEN(op2))[0]) == CNST_LIMB(1));
}
int
mpq_cmp_z (mpq_srcptr op1, mpz_srcptr op2)
{
return mpq_cmp_maybe_z (op1, (mpq_srcptr) op2, 1);
}
This way gcc compiles the mpq_cmp_z function (on amd64) as:
movl$1, %edx
jmp mpq_cmp_maybe_z
Is casting an mpz to an mpq, then accessing only the NUM() part of it,
portable?
I attach the proposed code, it adds four branches to the typical mpq_cmp
flow. One of them (checking if op1 is an integer) is not needed for
correctness. Please review!
Regards,
m
--
http://bodrato.it/papers//* mpq_cmp(u,v) -- Compare U, V. Return positive, zero, or negative
based on if U > V, U == V, or U < V.
Copyright 1991, 1994, 1996, 2001, 2002, 2005, 2015 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
The GNU MP Library is free software; you can redistribute it and/or modify
it under the terms of either:
* the GNU Lesser General Public License as published by the Free
Software Foundation; either version 3 of the License, or (at your
option) any later version.
or
* the GNU General Public License as published by the Free Software
Foundation; either version 2 of the License, or (at your option) any
later version.
or both in parallel, as here.
The GNU MP Library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received copies of the GNU General Public License and the
GNU Lesser General Public License along with the GNU MP Library. If not,
see https://www.gnu.org/licenses/. */
#include "gmp.h"
#include "gmp-impl.h"
#include "longlong.h"
static int
mpq_cmp_maybe_z (mpq_srcptr op1, mpq_srcptr op2, int op2_is_mpz)
{
mp_size_t num1_size = SIZ(NUM(op1));
mp_size_t den1_size = SIZ(DEN(op1));
mp_size_t num2_size = SIZ(NUM(op2));
mp_size_t den2_size = op2_is_mpz ? 0 : SIZ(DEN(op2));
mp_size_t tmp1_size, tmp2_size;
mp_ptr tmp1_ptr, tmp2_ptr;
mp_size_t num1_sign;
mp_limb_t d1h;
int cc;
TMP_DECL;
/* need canonical signs to get right result */
ASSERT (den1_size > 0);
ASSERT (op2_is_mpz || den2_size > 0);
if (num1_size == 0)
return -num2_size;
if (num2_size == 0)
return num1_size;
if ((num1_size ^ num2_size) < 0) /* I.e. are the signs different? */
return num1_size;
d1h = PTR(DEN(op1))[den1_size - 1]; /* THINK: Does storing d1h make sense? */
num1_sign = num1_size;
#if 1
if (op2_is_mpz == (den1_size | d1h)) /* Both ops are integers */
/* FIXME: check sizes, then use mpn_cmp */
return mpz_cmp (NUM (op1), NUM (op2));
#else
if (CNST_LIMB (1) == (den1_size | d1h)) /* op1 is an integer */
{
if (op2_is_mpz) /* Both integers */
return mpz_cmp (NUM (op1), NUM (op2));
MPQ_SRCPTR_SWAP (op1, op2);
num1_size = num2_size;
den1_size = den2_size;
num2_size = num1_sign;
den2_size = 0;
num1_sign = - num1_sign;
op2_is_mpz = 1;
d1h = PTR(DEN(op1))[den1_size - 1];
}
#endif
num1_size = ABS (num1_size);
num2_size = ABS (num2_size);
tmp1_size = num1_size + den2_size;
tmp2_size = num2_size + den1_size;
/* 1. Check to see if we can tell which operand is larger by just looking at
the number of limbs. */
/* NUM1 x DEN2 is either TMP1_SIZE limbs or TMP1_SIZE-1 limbs.
Same for NUM1 x DEN1 with respect to TMP2_SIZE. */
if (tmp1_size + op2_is_mpz > tmp2_size + 1)
/* NUM1 x DEN2 is surely larger in magnitude than NUM2 x DEN1. */
return num1_sign;
if (tmp2_size > tmp1_size + 1)
/* NUM1 x DEN2 is surely smaller in magnitude than NUM2 x DEN1. */
return -num1_sign;
/* 2. Same, but compare the number of significant bits. */
{
int cnt1, cnt2;
mp_bitcnt_t bits1, bits2;
count_leading_zeros (cnt1, PTR(NUM(op1))[num1_size - 1]);
bits1 = tmp1_size * GMP_NUMB_BITS - cnt1; /* + GMP_NAIL_BITS */
if (op2_is_mpz == 0)
{
count_leading_zeros (cnt2, PTR(DEN(op2))[den2_size - 1]);
bits1 -= cnt2 - GMP_NAIL_BITS;
}
count_leading_zeros (cnt1, PTR(NUM(op2))[num2_size - 1]);
count_leading_zeros (cnt2, d1h);
bits2 = tmp2_size * GMP_NUMB_BITS - cnt1 - cnt2 + GMP_NAIL_BITS; /* + GMP_NAIL_BIT
Re: mpq_cmp_z
"Marco Bodrato" writes:
Should we specialise code in mpq_cmp so that it is faster when a
denominator is 1? Then write:
Absolutely worth considering.
mpq_cmp_z (mpq_srcptr q, mpz_srcptr z)
{
static const mp_limb_t dummy = 1;
mpq_t qz;
SIZ(NUM(qz)) = SIZ(z);
PTR(NUM(qz)) = PTR(z);
SIZ(DEN(qz)) = 1;
PTR(DEN(qz)) = &dummy;
return mpq_cmp (q, qz);
}
Do you mean something like that?
Exactly.
--
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao,
On Sun, August 16, 2015 11:50 pm, Torbjörn Granlund wrote:
> On Sat, August 15, 2015 12:37 pm, Vincent Delecroix wrote:
> > rationals. We often have to compare integers with rationals and I came
> > to the conclusion that it would be convenient to have a GMP function
> >
> > int mpq_cmp_z(mpq_t, mpz_t)
> We might consider some code sharing between the mpq_cmp and this
> function, they look very similar.
I looked at "code sharing" in mpz/aors.h (a single file compiled with
different definitions to obtain two similar functions) and in mpq/aors.c
(two wrapper functions just setting a parameter for a single general
implementation), but I doubt either of the two models can be easily
applied to the mpq_cmp{,_q} case.
> We might even just put the mpz in stack allocated mpq structure and fall
> into mpq_cmp with a tail call.
Should we specialise code in mpq_cmp so that it is faster when a
denominator is 1? Then write:
mpq_cmp_z (mpq_srcptr q, mpz_srcptr z)
{
static const mp_limb_t dummy = 1;
mpq_t qz;
SIZ(NUM(qz)) = SIZ(z);
PTR(NUM(qz)) = PTR(z);
SIZ(DEN(qz)) = 1;
PTR(DEN(qz)) = &dummy;
return mpq_cmp (q, qz);
}
Do you mean something like that?
--
http://bodrato.it/
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
"Marco Bodrato" writes: Ciao Vincent, On Sat, August 15, 2015 12:37 pm, Vincent Delecroix wrote: > rationals. We often have to compare integers with rationals and I came > to the conclusion that it would be convenient to have a GMP function > > int mpq_cmp_z(mpq_t, mpz_t) Makes sense. > If you think that it would be a good addition, you might have a look in > the attached patch that was tested on the development version of GMP. I already have a similar function, I obtained it by pruning the mpq_cmp function, and you likely did the same, with an older version... I was waiting to propose, and commit it, because I'd like to overhaul many comparison function, maybe uniformly defining functions to test equality... and so on. But if you particularly need this function I think we can start by adding it. Comparing your code with mine, I see you added a couple of lines: if (!mpz_cmp_ui(mpq_denref(op), 1)) /* denominator 1 */ return mpz_cmp(mpq_numref(op), v); I'll test and add something equivalent. We might consider some code sharing between the mpq_cmp and this function, they look very similar. We might even just put the mpz in stack allocated mpq structure and fall into mpq_cmp with a tail call. -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpq_cmp_z
Ciao Vincent, On Sat, August 15, 2015 12:37 pm, Vincent Delecroix wrote: > rationals. We often have to compare integers with rationals and I came > to the conclusion that it would be convenient to have a GMP function > > int mpq_cmp_z(mpq_t, mpz_t) Makes sense. > If you think that it would be a good addition, you might have a look in > the attached patch that was tested on the development version of GMP. I already have a similar function, I obtained it by pruning the mpq_cmp function, and you likely did the same, with an older version... I was waiting to propose, and commit it, because I'd like to overhaul many comparison function, maybe uniformly defining functions to test equality... and so on. But if you particularly need this function I think we can start by adding it. Comparing your code with mine, I see you added a couple of lines: if (!mpz_cmp_ui(mpq_denref(op), 1)) /* denominator 1 */ return mpz_cmp(mpq_numref(op), v); I'll test and add something equivalent. Regards, m -- http://bodrato.it/papers/ ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
mpq_cmp_z
Dear all,
I am new to this list. I am a regular developer of the SageMath project
[1] in which we use mpz_t and mpq_t as our based type for integers and
rationals. We often have to compare integers with rationals and I came
to the conclusion that it would be convenient to have a GMP function
int mpq_cmp_z(mpq_t, mpz_t)
See the down stream ticket [2]. As we ship mpir by default, I made a
concrete proposal to them [3] and they kindly asked me to make the
proposal directly to GMP since they do want to keep their interface
consistent with the GMP project.
If you think that it would be a good addition, you might have a look in
the attached patch that was tested on the development version of GMP.
Best,
Vincent
[1] http://www.sagemath.org
[2] http://trac.sagemath.org/ticket/18304
[3] https://github.com/wbhart/mpir/pull/157
diff -r e5a96e5eb06d Makefile.am
--- a/Makefile.am Fri Aug 14 17:38:58 2015 +0200
+++ b/Makefile.am Sat Aug 15 12:35:02 2015 +0200
@@ -214,7 +214,7 @@
MPQ_OBJECTS = mpq/abs$U.lo mpq/aors$U.lo\
mpq/canonicalize$U.lo mpq/clear$U.lo mpq/clears$U.lo \
- mpq/cmp$U.lo mpq/cmp_si$U.lo mpq/cmp_ui$U.lo mpq/div$U.lo \
+ mpq/cmp$U.lo mpq/cmp_si$U.lo mpq/cmp_ui$U.lo mpq/cmp_z$U.lo mpq/div$U.lo \
mpq/get_d$U.lo mpq/get_den$U.lo mpq/get_num$U.lo mpq/get_str$U.lo \
mpq/init$U.lo mpq/inits$U.lo mpq/inp_str$U.lo mpq/inv$U.lo \
mpq/md_2exp$U.lo mpq/mul$U.lo mpq/neg$U.lo mpq/out_str$U.lo \
diff -r e5a96e5eb06d mpq/cmp_z.c
--- /dev/null Thu Jan 01 00:00:00 1970 +
+++ b/mpq/cmp_z.c Sat Aug 15 12:35:02 2015 +0200
@@ -0,0 +1,97 @@
+/* mpq_cmp_z(u,v) -- Compare U, V. Return positive, zero, or negative
+ based on if U > V, U == V, or U < V.
+
+Copyright 2015 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 2.1 of the License, or (at your
+option) any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+License for more details.
+
+You should have received a copy of the GNU Lesser General Public License
+along with the GNU MP Library; see the file COPYING.LIB. If not, write to
+the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+MA 02110-1301, USA. */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+#include "longlong.h"
+
+int
+mpq_cmp_z(mpq_srcptr op, mpz_srcptr v)
+{
+mp_size_t num_size = SIZ(NUM(op));
+mp_size_t den_size = SIZ(DEN(op));
+mp_size_t v_size = SIZ(v);
+mp_size_t tmp_size;
+mp_size_t num_sign;
+mp_ptr tmp_ptr;
+int cc;
+TMP_DECL;
+
+ASSERT (den_size > 0);
+
+/* 0. Check signs */
+if (num_size == 0)
+return -v_size;
+if (v_size == 0)
+return num_size;
+if ((num_size ^ v_size) < 0) /* different signs */
+return num_size;
+if (!mpz_cmp_ui(mpq_denref(op), 1)) /* denominator 1 */
+return mpz_cmp(mpq_numref(op), v);
+
+/* 1. Check to see if we can tell which operand is larger by just looking at the number of limbs */
+num_sign = num_size;
+num_size = ABS(num_size);
+v_size = ABS(v_size);
+tmp_size = v_size + den_size;
+
+/* den*v is either size tmp_size or tmp_size-1 */
+if(num_size > tmp_size)
+return num_sign;
+if(tmp_size > num_size + 1)
+return -num_sign;
+
+/* 2 . Same, but compare the number of significant bits. */
+{
+ int cnt1, cnt2;
+ unsigned long int bits1, bits2;
+
+ count_leading_zeros(cnt1, PTR(NUM(op))[num_size-1]);
+ bits1 = num_size * GMP_NUMB_BITS - cnt1 + GMP_NAIL_BITS;
+
+ count_leading_zeros(cnt1, PTR(v)[v_size-1]);
+ count_leading_zeros(cnt2, PTR(DEN(op))[den_size-1]);
+ bits2 = tmp_size * GMP_NUMB_BITS - cnt1 - cnt2 + 2 * GMP_NAIL_BITS;
+
+ if (bits1 > bits2 + 1)
+return num_sign;
+ if (bits2 > bits1 + 1)
+return -num_sign;
+}
+
+/* 3. Finally, cross multiply and compare. */
+TMP_MARK;
+tmp_ptr = (mp_ptr) TMP_ALLOC(num_size * GMP_LIMB_BYTES);
+
+if( v_size >= den_size)
+ tmp_size -= 0 == mpn_mul(tmp_ptr,
+ v->_mp_d, v_size,
+ op->_mp_den._mp_d, den_size);
+else
+ tmp_size -= 0 == mpn_mul(tmp_ptr,
+ op->_mp_den._mp_d, den_size,
+ v->_mp_d, v_size);
+cc = num_size - tmp_size != 0
+ ? num_size - tmp_size : mpn_cmp(op->_mp_num._mp_d, tmp_ptr, tmp_size);
+TMP_FREE;
+return num_sign < 0 ? -cc: cc;
+}
diff -r e5a96e5eb06d tests/mpq/Makefile.am
--- a/tests/mpq/Makefile.am Fri Aug 14 17:38:58 2015 +0200
+++ b/tests/mpq/Makefile.am Sat
