Re: overflow in mpz type with a simple mpz_add_ui

[Vincent Lefevre]

On 2020-09-21 21:17:36 +0200, Torbjorn Granlund wrote:
> Vincent Lefevre  writes:
> 
>   This is not properly documented, then. The manual says:
> 
>'mpz_add_ui', 'mpz_sub_ui', 'mpf_add_ui' and 'mpf_sub_ui' benefit
>from an in-place operation like 'mpz_add_ui(x,x,y)', since usually
>^^
>only one or two limbs of 'x' will need to be changed.  The same
>applies to the full precision 'mpz_add' etc if 'y' is small.  If
>'y' is big then cache locality may be helped, but that's all.
> 
>   Since this should be an in-place operation (as there is no carry),
>   an overflow is unexpected here.
> 
> Overflow here is a result of the mathmatical result.  Whether things are
> done "in place" or not is not part of it.

No, here this is not the result of the mathematical result. In my
example, this is just a consequence of GMP's implementation.

> But overflow might be flagged one limb too early for addition; instead
> of at 2^27-1 limbs for 32-bit hosts it might happen already at 2^27-2
> limbs.  I cannot say that's particularly bad.

Instead of flagging overflow before the addition, GMP should flag it
after, if it really occurs.

-- 
Vincent Lefèvre  - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: overflow in mpz type with a simple mpz_add_ui

[Torbjörn Granlund]

Vincent Lefevre  writes:

  This is not properly documented, then. The manual says:

   'mpz_add_ui', 'mpz_sub_ui', 'mpf_add_ui' and 'mpf_sub_ui' benefit
   from an in-place operation like 'mpz_add_ui(x,x,y)', since usually
   ^^
   only one or two limbs of 'x' will need to be changed.  The same
   applies to the full precision 'mpz_add' etc if 'y' is small.  If
   'y' is big then cache locality may be helped, but that's all.

  Since this should be an in-place operation (as there is no carry),
  an overflow is unexpected here.

Overflow here is a result of the mathmatical result.  Whether things are
done "in place" or not is not part of it.

But overflow might be flagged one limb too early for addition; instead
of at 2^27-1 limbs for 32-bit hosts it might happen already at 2^27-2
limbs.  I cannot say that's particularly bad.

As it happens, overflow detetion for other cases is much more coarse,
such as powering.

-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: overflow in mpz type with a simple mpz_add_ui

[Vincent Lefevre]

On 2020-09-21 18:16:15 +0200, Torbjorn Granlund wrote:
> Vincent Lefevre  writes:
> 
>   So the overflow occurs in "mpz_add_ui (z, z, 1);", though this
>   operation doesn't need a larger mpz_t and could even be done
>   in place: no carry occurs here, and note that a carry for a
>   huge number is very unlikely to occur.
> 
> No bug.  You're (presumably deliberately) dancing on the edge of mpz
> overflow.  The overflow detection flags some false positives, which is
> by design.

This is not properly documented, then. The manual says:

 'mpz_add_ui', 'mpz_sub_ui', 'mpf_add_ui' and 'mpf_sub_ui' benefit
 from an in-place operation like 'mpz_add_ui(x,x,y)', since usually
 ^^
 only one or two limbs of 'x' will need to be changed.  The same
 applies to the full precision 'mpz_add' etc if 'y' is small.  If
 'y' is big then cache locality may be helped, but that's all.

Since this should be an in-place operation (as there is no carry),
an overflow is unexpected here.

-- 
Vincent Lefèvre  - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: overflow in mpz type with a simple mpz_add_ui

[Marco Bodrato]

Ciao,

Il 2020-09-21 18:16 t...@gmplib.org ha scritto:

overflow.  The overflow detection flags some false positives, which is
by design.


But maybe we could avoid the false positive at least for the following 
example:


#include 
#include "gmp.h"

int main (void)
{
  mpz_t z;

  mpz_init (z);
  mpz_setbit (z, 0xffdf);
  printf ("OK\n");
  mpz_sub_ui (z, z, 123);
  printf ("OK\n");

  return 0;
}

We can avoid it simply moving the REALLOC after the branch.
This may save some allocations in many cases.

The proposed patch follows:

diff -r b851f9336a86 mpz/aors_ui.h
--- a/mpz/aors_ui.h Thu Sep 17 12:00:00 2020 +0200
+++ b/mpz/aors_ui.h Mon Sep 21 18:36:33 2020 +0200
@@ -86,21 +86,26 @@

   abs_usize = ABS (usize);

-  /* If not space for W (and possible carry), increase space.  */
-  wp = MPZ_REALLOC (w, abs_usize + 1);
-
-  /* These must be after realloc (U may be the same as W).  */
-  up = PTR (u);
-
   if (usize VARIATION_CMP 0)
 {
   mp_limb_t cy;
+
+  /* If not space for W (and possible carry), increase space.  */
+  wp = MPZ_REALLOC (w, abs_usize + 1);
+  /* These must be after realloc (U may be the same as W).  */
+  up = PTR (u);
+
   cy = mpn_add_1 (wp, up, abs_usize, (mp_limb_t) vval);
   wp[abs_usize] = cy;
   wsize = VARIATION_NEG (abs_usize + cy);
 }
   else
 {
+  /* If not space for W, increase space.  */
+  wp = MPZ_REALLOC (w, abs_usize);
+  /* These must be after realloc (U may be the same as W).  */
+  up = PTR (u);
+
   /* The signs are different.  Need exact comparison to determine
 which operand to subtract from which.  */
   if (abs_usize == 1 && up[0] < vval)




Ĝis,
m

--
http://bodrato.it/papers/
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: overflow in mpz type with a simple mpz_add_ui

[Torbjörn Granlund]

Vincent Lefevre  writes:

  So the overflow occurs in "mpz_add_ui (z, z, 1);", though this
  operation doesn't need a larger mpz_t and could even be done
  in place: no carry occurs here, and note that a carry for a
  huge number is very unlikely to occur.

No bug.  You're (presumably deliberately) dancing on the edge of mpz
overflow.  The overflow detection flags some false positives, which is
by design.

-- 
Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs