GMP code committed -- watch for bugs.

GMP code committed -- watch for bugs.

[Rob Browning]

I've just committed the code that switches us over to full-time
bignums using GMP.  I've tagged before and after with rlb-pre-gmp and
rlb-post-gmp.

(Marius: we'll need to finish switching to LGPL now.  I put a note in
 LICENSE for now.  I suppose we'll need to exchange COPYING for
 COPYING.LIB.  However if automake throws a fit and/or keeps putting
 COPYING back, we might just leave it.  LICENSE is the critical file.)

(Mikael: if you get a second, could you look at random.c and make sure
 you don't see any obvious mistakes.  One thing in particular -- could
 you look at the FIXME there -- if there's a chance that a random
 bignum could end up with enough leading zeroes to place it in fixnum
 territory, then we need to return scm_i_normbig (result), but I
 wanted to check with you first.  Returning a bignum with a value in
 fixnum range would violate an assumption made by other guile
 numerical code.)

There may well be bugs -- in addition to numbers.c, the other main
things to check (if you're motiviated) are random.c, socket.c, and
num2integral.c.  If/when you do find a bug, could you also try to add
a suitable test (if possible) to test-suite/tests/numbers.test or
similar so we don't regress in the future?

Overall the performance in my really simple tests on ~256-bit bignums
suggests this is code faster than the old code, but less space
efficient for smaller values.

To some extent the conversion in numbers.c has been fairly
straightforward.  There may still be places (i.e. perhaps have
integer-expt use mpz_pow or mpf_pow_ui when the types are right) where
special casing with GMP operations could help, but it'll probably take
some good benchmarking to know for sure.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Marius Vollmer]

Rob Browning <rlb@defaultvalue.org> writes:

> (Marius: we'll need to finish switching to LGPL now. [...])

Yep, I hope to finish this over the weekend.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Mikael Djurfeldt]

Great work!

I noticed a couple of problems:

1. A bug in libguile/Makefile.am which I've fixed.

2. My first attempt to build Guile has failed.  check_sanity aborts at
   the long_long LLONG_MAX test.  Unfortunately, I can't look into
   that right now.

Best regards,
Mikael


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Rob Browning]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> 2. My first attempt to build Guile has failed.  check_sanity aborts at
>    the long_long LLONG_MAX test.  Unfortunately, I can't look into
>    that right now.

Not sure it'll matter, but what arch are you working on?

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Mikael Djurfeldt]

Rob Browning <rlb@defaultvalue.org> writes:

> Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:
>
>> 2. My first attempt to build Guile has failed.  check_sanity aborts at
>>    the long_long LLONG_MAX test.  Unfortunately, I can't look into
>>    that right now.
>
> Not sure it'll matter, but what arch are you working on?

Sorry---forgot that: I'm running Debian unstable on i386 (=> using gcc 3.2).

M


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Mikael Djurfeldt]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> 2. My first attempt to build Guile has failed.  check_sanity aborts at
>    the long_long LLONG_MAX test.  Unfortunately, I can't look into
>    that right now.

OK.  There seems to be two bugs preventing the long_long tests from
succeeding:

1. num2integral.i.c:INTEGRAL2BIG had a bug in computing the absolute
   value of n when preparing arguments to mpz_import.  I've committed
   a fix for this.

2. The determination of required storage size for a bignum is buggy:
   
ITYPE
NUM2INTEGRAL (SCM num, unsigned long int pos, const char *s_caller)
{

     [...]

              numbits = mpz_sizeinbase (SCM_I_BIG_MPZ (num), 2);
              if (UNSIGNED) numbits++;
              scm_remember_upto_here_1 (num);
              if (numbits > (sizeof (ITYPE) * 8))
                scm_out_of_range (s_caller, num);

Firstly, you probably intended to write "if (!UNSIGNED)" (to make room
for the sign bit).  Secondly, that doesn't work either.  For example,
the absolute value of LLONG_MIN requires 64 bits, even though it is a
signed number.  So, regardless if we have "if (UNSIGNED)" or "if
(!UNSIGNED)" there will always be a case where a valid long_long or
ulong_long will cause an out_of_range error.

Unfortunately, I don't have time to get enough overview of the
situation to fix this bug.  I'll leave that to you.

Best regards,
Mikael


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Mikael Djurfeldt]

Rob Browning <rlb@defaultvalue.org> writes:

> (Mikael: if you get a second, could you look at random.c and make sure
>  you don't see any obvious mistakes.  One thing in particular -- could
>  you look at the FIXME there -- if there's a chance that a random
>  bignum could end up with enough leading zeroes to place it in fixnum
>  territory, then we need to return scm_i_normbig (result), but I
>  wanted to check with you first.  Returning a bignum with a value in
>  fixnum range would violate an assumption made by other guile
>  numerical code.)

Yes, we certainly must normalize.  The old code looked like this:

      /* now fill up the rest of the bignum */
      while (i)
	bits[--i] = scm_the_rng.random_bits (state);
      /* use scm_i_normbig to cut away leading zeros and/or convert to inum */
      b = scm_i_normbig (b);
      if (SCM_INUMP (b))
	return b;

Best regards,
Mikael


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Rob Browning]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

>               numbits = mpz_sizeinbase (SCM_I_BIG_MPZ (num), 2);
>               if (UNSIGNED) numbits++;
>               scm_remember_upto_here_1 (num);
>               if (numbits > (sizeof (ITYPE) * 8))
>                 scm_out_of_range (s_caller, num);
>
> Firstly, you probably intended to write "if (!UNSIGNED)" (to make room
> for the sign bit).

Indeed.

> Secondly, that doesn't work either.  For example, the absolute value
> of LLONG_MIN requires 64 bits, even though it is a signed number.
> So, regardless if we have "if (UNSIGNED)" or "if (!UNSIGNED)" there
> will always be a case where a valid long_long or ulong_long will
> cause an out_of_range error.

Hmm.  Actually it looks like mpz_sizeinbase includes the needed sign
bit in its computation (for some reason I thought it didn't).  So I
don't think we need the numbits++ at all.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Mikael Djurfeldt]

Rob Browning <rlb@defaultvalue.org> writes:

> Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:
>
>>               numbits = mpz_sizeinbase (SCM_I_BIG_MPZ (num), 2);
>>               if (UNSIGNED) numbits++;
>>               scm_remember_upto_here_1 (num);
>>               if (numbits > (sizeof (ITYPE) * 8))
>>                 scm_out_of_range (s_caller, num);
>>
>> Firstly, you probably intended to write "if (!UNSIGNED)" (to make room
>> for the sign bit).
>
> Indeed.
>
>> Secondly, that doesn't work either.  For example, the absolute value
>> of LLONG_MIN requires 64 bits, even though it is a signed number.
>> So, regardless if we have "if (UNSIGNED)" or "if (!UNSIGNED)" there
>> will always be a case where a valid long_long or ulong_long will
>> cause an out_of_range error.
>
> Hmm.  Actually it looks like mpz_sizeinbase includes the needed sign
> bit in its computation (for some reason I thought it didn't).  So I
> don't think we need the numbits++ at all.

That might be true, but it is difficult to arrive at that result from
the gmp manual entry:

 - Function: size_t mpz_sizeinbase (mpz_t OP, int BASE)
     Return the size of OP measured in number of digits in base BASE.
     The base may vary from 2 to 36.  The sign of OP is ignored, just
     the absolute value is used.  The result will be exact or 1 too
     big.  If BASE is a power of 2, the result will always be exact.
     If OP is zero the return value is always 1.

     This function is useful in order to allocate the right amount of
     space before converting OP to a string.  The right amount of
     allocation is normally two more than the value returned by
     `mpz_sizeinbase' (one extra for a minus sign and one for the
     null-terminator).

I guess, as always, the source code is the best documentation. :)

M


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Rob Browning]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> I guess, as always, the source code is the best documentation. :)

Actually, I just ran a test program :>

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Rob Browning]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> Yes, we certainly must normalize.

OK.  That's kinda what I suspected.  Fixed.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Rob Browning]

Mikael Djurfeldt <djurfeldt@nada.kth.se> writes:

> 2. The determination of required storage size for a bignum is buggy:

I'm also adding some initial "make check" tests that'll catch this
next time.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Kevin Ryde]

[-- Attachment #1: Type: text/plain, Size: 542 bytes --]

Rob Browning <rlb@defaultvalue.org> writes:
>
> There may well be bugs

A small one in (gcd n 0), test and possible fix below.  The result
should of course be abs(n) but mpz_gcd_ui can't return that if it
doesn't fit a ulong.

> where
> special casing with GMP operations could help, but it'll probably take
> some good benchmarking to know for sure.

ash (mentioned in the comments) would definitely benefit from the mpz
2exp functions.

In gcd, it'd be nice for the inum/bignum case to share code with the
bignum/inum case, like lcm does.


[-- Attachment #2: numbers.test.gcd-n-0.diff --]
[-- Type: text/plain, Size: 425 bytes --]

--- numbers.test.~1.16.~	2003-03-26 09:11:21.000000000 +1000
+++ numbers.test	2003-04-06 15:09:42.000000000 +1000
@@ -788,6 +788,11 @@
     (pass-if "n = fixnum-min - 1"
       (eqv? (- (- fixnum-min 1)) (gcd 0 (- fixnum-min 1)))))
 
+  (with-test-prefix "(n 0)"
+
+    (pass-if "n = 2^128 * fixnum-max"
+      (eqv? (ash fixnum-max 128) (gcd (ash fixnum-max 128) 0))))
+
   (with-test-prefix "(1 n)"
 
     (pass-if "n = 0"

[-- Attachment #3: numbers.c.gcd-n-0.diff --]
[-- Type: text/plain, Size: 598 bytes --]

Index: numbers.c
===================================================================
RCS file: /cvsroot/guile/guile/guile-core/libguile/numbers.c,v
retrieving revision 1.177
diff -u -u -F^[[:alpha:]$_] -r1.177 numbers.c
--- numbers.c	5 Apr 2003 19:10:22 -0000	1.177
+++ numbers.c	6 Apr 2003 22:48:02 -0000
@@ -708,6 +708,8 @@
         {
           unsigned long result;
           long yy = SCM_INUM (y);
+          if (yy == 0)
+            return scm_abs (x);
           if (yy < 0) yy = -yy;
           result = mpz_gcd_ui (NULL, SCM_I_BIG_MPZ (x), yy);
           scm_remember_upto_here_1 (x);

[-- Attachment #4: Type: text/plain, Size: 142 bytes --]

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs.

[Kevin Ryde]

Rob Browning <rlb@defaultvalue.org> writes:
>
> There may well be bugs

In >, < and =, mpz_cmp_d cannot be called with a NaN, that'll need to
be tested explicitly.

The doco doesn't say much about nans, but you can imagine with a
positive/zero/negative return there's no scope to indicate
"unordered".


Also, unfortunately mpz_cmp_d currently doesn't recognise infinities,
so those will need to be checked before making a call too.

The current code ends up treating infinities as 2^1023 or some such
big value, so the problem will only be seen with bignums larger than
that.

I'd been meaning to add infinities to mpz_cmp_d and friends, I'll see
if that can be in gmp 4.2.  In which case perhaps a bit of a macro
like below (untested) to hide the difference between the versions,


/* mpz_cmp_d only recognises infinities in gmp 4.2 and up.
   For prior versions use an explicit check here.  */
#if __GNU_MP_VERSION < 4                                        \
  || (__GNU_MP_VERSION == 4 && __GNU_MP_VERSION_MINOR < 2)
#define guile_mpz_cmp_d(z, d)                           \
  (xisinf (d) ? (d < 0.0 ? 1 : -1) : mpz_cmp_d (z, d))
#else
#define guile_mpz_cmp_d(z, d)  mpz_cmp_d (z, d)
#endif


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP code committed -- watch for bugs ... gcd n 0

[Kevin Ryde]

I wrote:
>
> A small one in (gcd n 0)

I applied the changes I posted

        * numbers.c (scm_gcd): In bignum/inum, don't pass yy==0 to mpz_gcd_ui
        since we're only using the ulong return value, and x might not fit.

        * tests/numbers.test (gcd): Exercise bignum/inum with a bignum not
        fitting a ulong.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel