[Gmp-commit] /var/hg/gmp: 2 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Mon Aug 31 08:40:45 UTC 2015
details: /var/hg/gmp/rev/c95f8df2b57e
changeset: 16795:c95f8df2b57e
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Aug 31 10:39:44 2015 +0200
description:
New function mpq_cmp_z, with test and documentation
details: /var/hg/gmp/rev/4d02fcf88613
changeset: 16796:4d02fcf88613
user: Marco Bodrato <bodrato at mail.dm.unipi.it>
date: Mon Aug 31 10:40:37 2015 +0200
description:
ChangeLog
diffstat:
ChangeLog | 11 +++++-
doc/gmp.texi | 1 +
gmp-h.in | 3 +
mpq/cmp.c | 75 ++++++++++++++++++++++++++++++++--------
tests/mpq/Makefile.am | 4 +-
tests/mpq/t-cmp_z.c | 93 +++++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 168 insertions(+), 19 deletions(-)
diffs (truncated from 311 to 300 lines):
diff -r 7a008d0f75a7 -r 4d02fcf88613 ChangeLog
--- a/ChangeLog Sat Aug 29 11:56:38 2015 +0200
+++ b/ChangeLog Mon Aug 31 10:40:37 2015 +0200
@@ -1,3 +1,12 @@
+2015-08-31 Marco Bodrato <bodrato at mail.dm.unipi.it>
+
+ * mpq/cmp.c (mpq_cmp_z): New function to compare mpq with mpz,
+ asked by Vincent Delecroix for the SageMath project.
+ * gmp-h.in: Declare it.
+ * doc/gmp.texi: Document it.
+ * tests/mpq/t-cmp_z.c: New file to test mpq_cmp_z (from t-cmp.c).
+ * tests/mpq/Makefile.am (check_PROGRAMS): Add t-cmp_z.
+
2015-08-29 Torbjörn Granlund <torbjorng at google.com>
* mpn/x86_64/fat/fat.c (fake_cpuid_table): Add CPU aliases.
@@ -7,7 +16,7 @@
* configure.ac (AH_VERBATIM): Add HAVE_NATIVE_mpn_mullo_basecase.
* mpn/generic/sqrlo.c (mpn_sqrlo): Use mullo_basecase when faster.
* mpn/generic/sqrlo_basecase.c: More readable #defines.
-
+
* tune/tuneup.c (tune_sqrlo): New function to tune sqrlo thresholds.
(all): Call it, after multiplication and FFT.
* tune/Makefile.am (TUNE_MPN_SRCS_BASIC): Add sqrlo{,_basecase}.c .
diff -r 7a008d0f75a7 -r 4d02fcf88613 doc/gmp.texi
--- a/doc/gmp.texi Sat Aug 29 11:56:38 2015 +0200
+++ b/doc/gmp.texi Mon Aug 31 10:40:37 2015 +0200
@@ -4420,6 +4420,7 @@
@cindex Comparison functions
@deftypefun int mpq_cmp (const mpq_t @var{op1}, const mpq_t @var{op2})
+ at deftypefunx int mpq_cmp_z (const mpq_t @var{op1}, const mpz_t @var{op2})
Compare @var{op1} and @var{op2}. Return a positive value if @math{@var{op1} >
@var{op2}}, zero if @math{@var{op1} = @var{op2}}, and a negative value if
@math{@var{op1} < @var{op2}}.
diff -r 7a008d0f75a7 -r 4d02fcf88613 gmp-h.in
--- a/gmp-h.in Sat Aug 29 11:56:38 2015 +0200
+++ b/gmp-h.in Mon Aug 31 10:40:37 2015 +0200
@@ -1158,6 +1158,9 @@
#define _mpq_cmp_ui __gmpq_cmp_ui
__GMP_DECLSPEC int _mpq_cmp_ui (mpq_srcptr, unsigned long int, unsigned long int) __GMP_ATTRIBUTE_PURE;
+#define mpq_cmp_z __gmpq_cmp_z
+__GMP_DECLSPEC int mpq_cmp_z (mpq_srcptr, mpz_srcptr) __GMP_ATTRIBUTE_PURE;
+
#define mpq_div __gmpq_div
__GMP_DECLSPEC void mpq_div (mpq_ptr, mpq_srcptr, mpq_srcptr);
diff -r 7a008d0f75a7 -r 4d02fcf88613 mpq/cmp.c
--- a/mpq/cmp.c Sat Aug 29 11:56:38 2015 +0200
+++ b/mpq/cmp.c Mon Aug 31 10:40:37 2015 +0200
@@ -1,7 +1,7 @@
/* 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 Free Software Foundation, Inc.
+Copyright 1991, 1994, 1996, 2001, 2002, 2005, 2015 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -33,13 +33,15 @@
#include "gmp-impl.h"
#include "longlong.h"
-int
-mpq_cmp (mpq_srcptr op1, mpq_srcptr op2)
+static int
+mpq_cmp_numden (mpq_srcptr op1, mpz_srcptr num_op2, mpz_srcptr den_op2)
{
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 = SIZ(DEN(op2));
+ mp_size_t num2_size = SIZ(num_op2);
+ mp_size_t den2_size = SIZ(den_op2);
+ int op2_is_int;
+ mp_limb_t d1h, d2h;
mp_size_t tmp1_size, tmp2_size;
mp_ptr tmp1_ptr, tmp2_ptr;
mp_size_t num1_sign;
@@ -59,6 +61,23 @@
num1_sign = num1_size;
num1_size = ABS (num1_size);
+
+ /* THINK: Does storing d1h and d2h make sense? */
+ d1h = PTR(DEN(op1))[den1_size - 1];
+ d2h = PTR(den_op2)[den2_size - 1];
+ op2_is_int = (den2_size | d2h) == 1;
+ if (op2_is_int == (den1_size | d1h)) /* Both ops are integers */
+ /* return mpz_cmp (NUM (op1), num_op2); */
+ {
+ int cmp;
+
+ if (num1_sign != num2_size)
+ return num1_sign - num2_size;
+
+ cmp = mpn_cmp (PTR(NUM(op1)), PTR(num_op2), num1_size);
+ return (num1_sign > 0 ? cmp : -cmp);
+ }
+
num2_size = ABS (num2_size);
tmp1_size = num1_size + den2_size;
@@ -72,7 +91,7 @@
if (tmp1_size > tmp2_size + 1)
/* NUM1 x DEN2 is surely larger in magnitude than NUM2 x DEN1. */
return num1_sign;
- if (tmp2_size > tmp1_size + 1)
+ if (tmp2_size + op2_is_int > tmp1_size + 1)
/* NUM1 x DEN2 is surely smaller in magnitude than NUM2 x DEN1. */
return -num1_sign;
@@ -82,41 +101,50 @@
mp_bitcnt_t bits1, bits2;
count_leading_zeros (cnt1, PTR(NUM(op1))[num1_size - 1]);
- count_leading_zeros (cnt2, PTR(DEN(op2))[den2_size - 1]);
- bits1 = tmp1_size * GMP_NUMB_BITS - cnt1 - cnt2 + 2 * GMP_NAIL_BITS;
+ count_leading_zeros (cnt2, d2h);
+ bits1 = tmp1_size * GMP_NUMB_BITS - cnt1 - cnt2; /* + 2 * GMP_NAIL_BITS */
- count_leading_zeros (cnt1, PTR(NUM(op2))[num2_size - 1]);
- count_leading_zeros (cnt2, PTR(DEN(op1))[den1_size - 1]);
- bits2 = tmp2_size * GMP_NUMB_BITS - cnt1 - cnt2 + 2 * 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; /* + 2 * GMP_NAIL_BITS */
if (bits1 > bits2 + 1)
return num1_sign;
- if (bits2 > bits1 + 1)
+ if (bits2 + op2_is_int > bits1 + 1)
return -num1_sign;
}
/* 3. Finally, cross multiply and compare. */
TMP_MARK;
+ if (op2_is_int)
+ {
+ tmp2_ptr = TMP_ALLOC_LIMBS (tmp2_size);
+ tmp1_ptr = PTR(NUM(op1));
+ --tmp1_size;
+ }
+ else
+ {
TMP_ALLOC_LIMBS_2 (tmp1_ptr,tmp1_size, tmp2_ptr,tmp2_size);
if (num1_size >= den2_size)
tmp1_size -= 0 == mpn_mul (tmp1_ptr,
PTR(NUM(op1)), num1_size,
- PTR(DEN(op2)), den2_size);
+ PTR(den_op2), den2_size);
else
tmp1_size -= 0 == mpn_mul (tmp1_ptr,
- PTR(DEN(op2)), den2_size,
+ 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(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);
+ PTR(num_op2), num2_size);
cc = tmp1_size - tmp2_size != 0
@@ -124,3 +152,18 @@
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);
+}
diff -r 7a008d0f75a7 -r 4d02fcf88613 tests/mpq/Makefile.am
--- a/tests/mpq/Makefile.am Sat Aug 29 11:56:38 2015 +0200
+++ b/tests/mpq/Makefile.am Mon Aug 31 10:40:37 2015 +0200
@@ -1,6 +1,6 @@
## Process this file with automake to generate Makefile.in
-# Copyright 1996, 1999-2002, 2012 Free Software Foundation, Inc.
+# Copyright 1996, 1999-2002, 2012, 2015 Free Software Foundation, Inc.
#
# This file is part of the GNU MP Library test suite.
#
@@ -22,7 +22,7 @@
LDADD = $(top_builddir)/tests/libtests.la $(top_builddir)/libgmp.la
check_PROGRAMS = t-aors t-cmp t-cmp_ui t-cmp_si t-equal t-get_d t-get_str \
- t-inp_str t-inv t-md_2exp t-set_f t-set_str io reuse
+ t-inp_str t-inv t-md_2exp t-set_f t-set_str io reuse t-cmp_z
TESTS = $(check_PROGRAMS)
# Temporary files used by the tests. Removed automatically if the tests
diff -r 7a008d0f75a7 -r 4d02fcf88613 tests/mpq/t-cmp_z.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/mpq/t-cmp_z.c Mon Aug 31 10:40:37 2015 +0200
@@ -0,0 +1,93 @@
+/* Test mpq_cmp_z.
+
+Copyright 1996, 2001, 2015 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library test suite.
+
+The GNU MP Library test suite is free software; you can redistribute it
+and/or modify it under the terms of the GNU General Public License as
+published by the Free Software Foundation; either version 3 of the License,
+or (at your option) any later version.
+
+The GNU MP Library test suite 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 a copy of the GNU General Public License along with
+the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "gmp.h"
+#include "gmp-impl.h"
+#include "tests.h"
+
+#define SGN(x) ((x) < 0 ? -1 : (x) > 0 ? 1 : 0)
+
+int
+ref_mpq_cmp_z (mpq_t a, mpz_t b)
+{
+ mpz_t bi;
+ int cc;
+
+ mpz_init (bi);
+
+ mpz_mul (bi, b, DEN (a));
+ cc = mpz_cmp (NUM (a), bi);
+ mpz_clear (bi);
+ return cc;
+}
+
+#ifndef SIZE
+#define SIZE 8 /* increasing this lowers the probability of finding an error */
+#endif
+
+int
+main (int argc, char **argv)
+{
+ mpq_t a;
+ mpz_t b;
+ mp_size_t size;
+ int reps = 10000;
+ int i;
+ int cc, ccref;
+
+ tests_start ();
+
+ if (argc == 2)
+ reps = atoi (argv[1]);
+
+ mpq_init (a);
+ mpz_init (b);
+
+ for (i = 0; i < reps; i++)
+ {
+ size = urandom () % SIZE - SIZE/2;
+ mpz_random2 (NUM (a), size);
+ do
+ {
+ size = urandom () % (SIZE/2);
+ mpz_random2 (DEN (a), size);
+ }
+ while (mpz_cmp_ui (DEN (a), 0) == 0);
+
+ size = urandom () % SIZE - SIZE/2;
+ mpz_random2 (b, size);
+
+ mpq_canonicalize (a);
+
+ ccref = ref_mpq_cmp_z (a, b);
+ cc = mpq_cmp_z (a, b);
More information about the gmp-commit
mailing list