Re: mini-gmp mpz_gcdext Bézout coefficients do not match documentation
marco.bodr...@tutanota.com writes: > The only reason why I prefer my solution is: when cmp<0, there is no need to > compute > mpz_sub (t1, t0, t1); That's certainly a micro optimization, but let's keep things simple. I've pushed this fix now, I think there were only comment and ChangeLog changes since the previous version of the patch. Thanks for the review, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: major formatted output function bug with %c and the value 0
Ciao Vincent,
15 dic 2023, 13:26 da vinc...@vinc17.net:
> Note that there are similar issues in printf/repl-vsnprintf.c, and I
>
I finally had the time to examine the code and test it. I attach a proposed
patch.
I changed the 3 files: printf/doprntf.c, printf/repl-vsnprintf.c,
printf/sprintffuns.c, to use the returned value of the called functions,
instead of calling strlen on the string.
I also slightly changed the tests, to check at least one case with "%c", 0.
For this to work I also had to change a
- (*__gmp_free_func) (got, strlen(got)+1);
+ (*__gmp_free_func) (got, got_len+1);
When the string comes from a generic print, it is safer to relay on the return
value than on the length computed by strlen()...
> think that this is the cause of the MPFR failure with MS Visual C++
> (vsnprintf is used by gmp_vasprintf).
>
If you can also test on that side, let me know. Thanks!
Gis,
m
diff -r 1c566525476a printf/doprntf.c
--- a/printf/doprntf.c Wed Dec 27 19:35:36 2023 +0100
+++ b/printf/doprntf.c Sun Feb 18 12:17:18 2024 +0100
@@ -267,8 +267,7 @@
mean truncation */
ASSERT (explen >= 0 && explen < sizeof(exponent)-1);
#else
- sprintf (exponent, p->expfmt, expsign, expval);
- explen = strlen (exponent);
+ explen = sprintf (exponent, p->expfmt, expsign, expval);
ASSERT (explen < sizeof(exponent));
#endif
TRACE (printf (" expfmt %s gives %s\n", p->expfmt, exponent));
diff -r 1c566525476a printf/repl-vsnprintf.c
--- a/printf/repl-vsnprintf.c Wed Dec 27 19:35:36 2023 +0100
+++ b/printf/repl-vsnprintf.c Sun Feb 18 12:17:18 2024 +0100
@@ -364,16 +364,14 @@
if (total_width <= buf_size)
{
- vsprintf (buf, orig_fmt, orig_ap);
- len = strlen (buf);
+ len = vsprintf (buf, orig_fmt, orig_ap);
}
else
{
char *s;
s = __GMP_ALLOCATE_FUNC_TYPE (total_width, char);
- vsprintf (s, orig_fmt, orig_ap);
- len = strlen (s);
+ len = vsprintf (s, orig_fmt, orig_ap);
if (buf_size != 0)
{
size_t copylen = MIN (len, buf_size-1);
diff -r 1c566525476a printf/sprintffuns.c
--- a/printf/sprintffuns.c Wed Dec 27 19:35:36 2023 +0100
+++ b/printf/sprintffuns.c Sun Feb 18 12:17:18 2024 +0100
@@ -53,9 +53,9 @@
{
char *buf = *bufp;
int ret;
- vsprintf (buf, fmt, ap);
- ret = strlen (buf);
- *bufp = buf + ret;
+ ret = vsprintf (buf, fmt, ap);
+ if (ret > 0)
+*bufp = buf + ret;
return ret;
}
diff -r 1c566525476a tests/misc/t-printf.c
--- a/tests/misc/t-printf.c Wed Dec 27 19:35:36 2023 +0100
+++ b/tests/misc/t-printf.c Sun Feb 18 12:17:18 2024 +0100
@@ -128,12 +128,11 @@
}
void
-check_vsprintf (const char *want, const char *fmt, va_list ap)
+check_vsprintf (const char *want, int want_len, const char *fmt, va_list ap)
{
char got[MAX_OUTPUT];
- int got_len, want_len;
+ int got_len;
- want_len = strlen (want);
got_len = gmp_vsprintf (got, fmt, ap);
if (got_len != want_len || strcmp (got, want) != 0)
@@ -149,14 +148,12 @@
}
void
-check_vfprintf (const char *want, const char *fmt, va_list ap)
+check_vfprintf (const char *want, int want_len, const char *fmt, va_list ap)
{
char got[MAX_OUTPUT];
- int got_len, want_len, fread_len;
+ int got_len, fread_len;
long ftell_len;
- want_len = strlen (want);
-
rewind (check_vfprintf_fp);
got_len = gmp_vfprintf (check_vfprintf_fp, fmt, ap);
ASSERT_ALWAYS (got_len != -1);
@@ -187,14 +184,12 @@
}
void
-check_vsnprintf (const char *want, const char *fmt, va_list ap)
+check_vsnprintf (const char *want, int want_len, const char *fmt, va_list ap)
{
chargot[MAX_OUTPUT+1];
- int ret, got_len, want_len;
+ int ret, got_len;
size_t bufsize;
- want_len = strlen (want);
-
bufsize = -1;
for (;;)
{
@@ -243,12 +238,11 @@
}
void
-check_vasprintf (const char *want, const char *fmt, va_list ap)
+check_vasprintf (const char *want, int want_len, const char *fmt, va_list ap)
{
char *got;
- int got_len, want_len;
+ int got_len;
- want_len = strlen (want);
got_len = gmp_vasprintf (, fmt, ap);
if (got_len != want_len || strcmp (got, want) != 0)
@@ -261,19 +255,17 @@
printf (" want_len %d\n", want_len);
abort ();
}
- (*__gmp_free_func) (got, strlen(got)+1);
+ (*__gmp_free_func) (got, got_len+1);
}
void
-check_obstack_vprintf (const char *want, const char *fmt, va_list ap)
+check_obstack_vprintf (const char *want, int want_len, const char *fmt, va_list ap)
{
#if HAVE_OBSTACK_VPRINTF
struct obstack ob;
- int got_len, want_len, ob_len;
+ int got_len, ob_len;
char *got;
- want_len = strlen (want);
-
obstack_init ();
got_len = gmp_obstack_vprintf (, fmt, ap);
got = (char *) obstack_base ();
@@ -300,15 +292,30 @@
void
check_one (const char *want, const char *fmt, ...)
{
+ int want_len = strlen (want);
va_list ap;
va_start (ap, fmt);
/* simplest first */
- check_vsprintf (want, fmt, ap);
-
Re: mini-gmp mpz_gcdext Bézout coefficients do not match documentation
Ciao Niels,
18 feb 2024, 10:10 da ni...@lysator.liu.se:
> marco.bodr...@tutanota.com writes:
>
>> What about;
>>
>>
>> /* Arrange so that |s| < |u| / 2g */
>> mpz_add (s1, s0, s1);
>> {
>> int cmp = mpz_cmpabs (s0, s1);
>> if (cmp >= 0)
>> {
>> mpz_swap (s0, s1);
>> mpz_sub (t1, t0, t1);
>> if (cmp != 0 || mpz_cmpabs (t0, t1) > 0)
>> mpz_swap (t0, t1);
>> }
>> }
>>
>
> I think swapping of s and t must go together? I've tried out this
> similar variant
>
You are right, it's better with the two swaps together.
> mpz_add (s1, s0, s1);
> mpz_sub (t1, t0, t1);
> cmp = mpz_cmpabs (s0, s1);
> if (cmp > 0 || (cmp == 0 && mpz_cmpabs (t0, t1) > 0))
> {
> mpz_swap (s0, s1);
> mpz_swap (t0, t1);
> }
>
The only reason why I prefer my solution is: when cmp<0, there is no need to
compute
mpz_sub (t1, t0, t1);
> Seems to work fine, and it's a rather clear way to express the "lexical"
> preference that we want the cofactor pair with the smallest of |s|, |s'|, but
> in case of a tie, we choose the pair with smallest |t|, |t'|.
>
I agree.
Ĝis,
m
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: mini-gmp mpz_gcdext Bézout coefficients do not match documentation
marco.bodr...@tutanota.com writes:
> s==0 is not a special case, it's one of the cases with smaller |s|.
Right, s == 0 is not a special case in itself, what's special is the
case g = a = b, then we have too candidate cofactor pairs, s=1, t=0,
s'=0, t'= 1. And we have the asymmetric preference for the first.
> What about;
>
> /* Arrange so that |s| < |u| / 2g */
> mpz_add (s1, s0, s1);
> {
> int cmp = mpz_cmpabs (s0, s1);
> if (cmp >= 0)
> {
> mpz_swap (s0, s1);
> mpz_sub (t1, t0, t1);
> if (cmp != 0 || mpz_cmpabs (t0, t1) > 0)
> mpz_swap (t0, t1);
> }
> }
I think swapping of s and t must go together? I've tried out this
similar variant
mpz_add (s1, s0, s1);
mpz_sub (t1, t0, t1);
cmp = mpz_cmpabs (s0, s1);
if (cmp > 0 || (cmp == 0 && mpz_cmpabs (t0, t1) > 0))
{
mpz_swap (s0, s1);
mpz_swap (t0, t1);
}
Seems to work fine, and it's a rather clear way to express the "lexical"
preference that we want the cofactor pair with the smallest of |s|, |s'|, but
in case of a tie, we choose the pair with smallest |t|, |t'|.
Updated version of the patch appended below.
Regrads,
/Niels
diff -r 1c566525476a mini-gmp/mini-gmp.c
--- a/mini-gmp/mini-gmp.c Wed Dec 27 19:35:36 2023 +0100
+++ b/mini-gmp/mini-gmp.c Sun Feb 18 10:02:56 2024 +0100
@@ -2809,6 +2809,7 @@
mpz_t tu, tv, s0, s1, t0, t1;
mp_bitcnt_t uz, vz, gz;
mp_bitcnt_t power;
+ int cmp;
if (u->_mp_size == 0)
{
@@ -2960,12 +2961,21 @@
mpz_tdiv_q_2exp (t0, t0, 1);
}
- /* Arrange so that |s| < |u| / 2g */
+ /* Choose small cofactors (they should satify
+
+ |s| < |u| / 2g and |t| < |v| / 2g,
+
+ except for documented exceptions). Always choose the smallest s,
+ if there are two choices for s with same absolute value, choose
+ the one with smallest corresponding t (this asymmetryic condition
+ is needed to prefer s = 0, |t| = 1 when g = |a| = |b|). */
mpz_add (s1, s0, s1);
- if (mpz_cmpabs (s0, s1) > 0)
+ mpz_sub (t1, t0, t1);
+ cmp = mpz_cmpabs (s0, s1);
+ if (cmp > 0 || (cmp == 0 && mpz_cmpabs (t0, t1) > 0))
{
mpz_swap (s0, s1);
- mpz_sub (t0, t0, t1);
+ mpz_swap (t0, t1);
}
if (u->_mp_size < 0)
mpz_neg (s0, s0);
diff -r 1c566525476a mini-gmp/tests/t-gcd.c
--- a/mini-gmp/tests/t-gcd.cWed Dec 27 19:35:36 2023 +0100
+++ b/mini-gmp/tests/t-gcd.cSun Feb 18 10:02:56 2024 +0100
@@ -55,6 +55,10 @@
if (mpz_sgn (g) <= 0)
return 0;
+ /* Require that s==0 iff g==abs(b) */
+ if (!mpz_sgn (s) != !mpz_cmpabs (g, b))
+goto fail;
+
mpz_init (ta);
mpz_init (tb);
mpz_init (r);
@@ -79,20 +83,20 @@
if (mpz_sgn (r) != 0)
goto fail;
- /* Require that 2 |s| < |b/g|, or |s| == 1. */
- if (mpz_cmpabs_ui (s, 1) > 0)
+ /* Require that 2 |s| < |b/g|, or s == sgn(a) */
+ if (mpz_cmp_si (s, mpz_sgn (a)) != 0)
{
mpz_mul_2exp (r, s, 1);
- if (mpz_cmpabs (r, tb) > 0)
+ if (mpz_cmpabs (r, tb) >= 0)
goto fail;
}
- /* Require that 2 |t| < |a/g| or |t| == 1*/
- if (mpz_cmpabs_ui (t, 1) > 0)
+ /* Require that 2 |t| < |a/g| or t == sgn(b) */
+ if (mpz_cmp_si (t, mpz_sgn (b)) != 0)
{
mpz_mul_2exp (r, t, 1);
- if (mpz_cmpabs (r, ta) > 0)
- return 0;
+ if (mpz_cmpabs (r, ta) >= 0)
+ goto fail;
}
mpz_clear (ta);
@@ -102,17 +106,53 @@
return 1;
}
+static void test_one(const mpz_t a, const mpz_t b)
+{
+ mpz_t g, s, t;
+
+ mpz_init (g);
+ mpz_init (s);
+ mpz_init (t);
+
+ mpz_gcdext (g, s, t, a, b);
+ if (!gcdext_valid_p (a, b, g, s, t))
+{
+ fprintf (stderr, "mpz_gcdext failed:\n");
+ dump ("a", a);
+ dump ("b", b);
+ dump ("g", g);
+ dump ("s", s);
+ dump ("t", t);
+ abort ();
+}
+
+ mpz_gcd (s, a, b);
+ if (mpz_cmp (g, s))
+{
+ fprintf (stderr, "mpz_gcd failed:\n");
+ dump ("a", a);
+ dump ("b", b);
+ dump ("r", g);
+ dump ("ref", s);
+ abort ();
+}
+
+ mpz_clear (g);
+ mpz_clear (s);
+ mpz_clear (t);
+}
+
void
testmain (int argc, char **argv)
{
unsigned i;
- mpz_t a, b, g, s, t;
+ mpz_t a, b, g, s;
+ int ai, bi;
mpz_init (a);
mpz_init (b);
mpz_init (g);
mpz_init (s);
- mpz_init (t);
for (i = 0; i < COUNT; i++)
{
@@ -129,6 +169,15 @@
}
}
+ /* Exhaustive test of small inputs */
+ for (ai = -30; ai <= 30; ai++)
+for (bi = -30; bi <= 30; bi++)
+ {
+ mpz_set_si (a, ai);
+ mpz_set_si (b, bi);
+ test_one (a, b);
+ }
+
for (i = 0; i < COUNT; i++)
{
unsigned flags;
@@ -147,32 +196,11 @@
if (flags & 2)
mpz_neg (b, b);
- mpz_gcdext (g, s, t, a, b);
- if (!gcdext_valid_p (a, b, g, s, t))
- {
- fprintf (stderr, "mpz_gcdext failed:\n");
- dump ("a", a);
- dump ("b", b);
- dump ("g", g);
- dump ("s", s);
- dump ("t",
