GNU bug report logs - #13031
large numbers

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 13031 in the body.
You can then email your comments to 13031 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Jozef Chraplewski <jozef <at> applicake.com>
To: bug-guile <at> gnu.org
Subject: large numbers
Date: Thu, 29 Nov 2012 09:42:09 +0100

Hi,

It looks that guile returns incorrect results when it works with really big numbers.

I've found it during resolving problem 48 from Project Euler:

http://projecteuler.net/problem=48

The solution is trivial:

(define (problem-48 limit)
 (define (F)
   (let loop ((n 1)
              (sum 0))
     (if (<= n limit)
         (loop (+ n 1) (+ sum (expt n n)))
         sum)))

 (let* ((str (number->string (F)))
          (len (string-length str)))
   (substring str (- len 10) len)))

(display (problem-48 1000))
(newline)


The proper answer is 9110846700 but guile returns 6457854188

I've tested solution under other scheme implementations (MIT scheme, petite and mzscheme) and it works as it should.

Does such a big numbers in guile require any special treatment or just they are not supported?

Best,
Jozef

Message #8 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: Noah Lavine <noah.b.lavine <at> gmail.com>
To: Jozef Chraplewski <jozef <at> applicake.com>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Thu, 29 Nov 2012 14:08:45 -0500

[Message part 1 (text/plain, inline)]

No, they are meant to be supported without any special treatment. I don't
know what is happening in your example.


On Thu, Nov 29, 2012 at 3:42 AM, Jozef Chraplewski <jozef <at> applicake.com>wrote:

> Hi,
>
> It looks that guile returns incorrect results when it works with really
> big numbers.
>
> I've found it during resolving problem 48 from Project Euler:
>
> http://projecteuler.net/problem=48
>
> The solution is trivial:
>
> (define (problem-48 limit)
>  (define (F)
>    (let loop ((n 1)
>               (sum 0))
>      (if (<= n limit)
>          (loop (+ n 1) (+ sum (expt n n)))
>          sum)))
>
>  (let* ((str (number->string (F)))
>           (len (string-length str)))
>    (substring str (- len 10) len)))
>
> (display (problem-48 1000))
> (newline)
>
>
> The proper answer is 9110846700 but guile returns 6457854188
>
> I've tested solution under other scheme implementations (MIT scheme,
> petite and mzscheme) and it works as it should.
>
> Does such a big numbers in guile require any special treatment or just
> they are not supported?
>
> Best,
> Jozef
>
>
>

[Message part 2 (text/html, inline)]

Message #11 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Israelsson Tampe <stefan.itampe <at> gmail.com>
To: Jozef Chraplewski <jozef <at> applicake.com>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Thu, 29 Nov 2012 20:15:26 +0100

[Message part 1 (text/plain, inline)]

Hi,

Which version of guile do you use, I get the correct value for guile
2.0.5.91-de6d8

/Stefan


On Thu, Nov 29, 2012 at 9:42 AM, Jozef Chraplewski <jozef <at> applicake.com>wrote:

> Hi,
>
> It looks that guile returns incorrect results when it works with really
> big numbers.
>
> I've found it during resolving problem 48 from Project Euler:
>
> http://projecteuler.net/problem=48
>
> The solution is trivial:
>
> (define (problem-48 limit)
>  (define (F)
>    (let loop ((n 1)
>               (sum 0))
>      (if (<= n limit)
>          (loop (+ n 1) (+ sum (expt n n)))
>          sum)))
>
>  (let* ((str (number->string (F)))
>           (len (string-length str)))
>    (substring str (- len 10) len)))
>
> (display (problem-48 1000))
> (newline)
>
>
> The proper answer is 9110846700 but guile returns 6457854188
>
> I've tested solution under other scheme implementations (MIT scheme,
> petite and mzscheme) and it works as it should.
>
> Does such a big numbers in guile require any special treatment or just
> they are not supported?
>
> Best,
> Jozef
>
>
>

[Message part 2 (text/html, inline)]

Message #14 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: Jozef Chraplewski <jozef <at> applicake.com>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Thu, 29 Nov 2012 23:11:29 +0100

Hi,

Jozef Chraplewski <jozef <at> applicake.com> skribis:

> The solution is trivial:
>
> (define (problem-48 limit)
>  (define (F)
>    (let loop ((n 1)
>               (sum 0))
>      (if (<= n limit)
>          (loop (+ n 1) (+ sum (expt n n)))
>          sum)))
>
>  (let* ((str (number->string (F)))
>           (len (string-length str)))
>    (substring str (- len 10) len)))
>
> (display (problem-48 1000))
> (newline)
>
>
> The proper answer is 9110846700 but guile returns 6457854188

I also get 9110846700 with 2.0.6+ and 1.8.8+.  What version do you use?

(Bigloo 3.2a returns 5842605292, though.)

Ludo’.

Message #17 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: Jozef Chraplewski <jozef <at> applicake.com>
To: Ludovic Courtès <ludo <at> gnu.org>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Fri, 30 Nov 2012 12:54:37 +0100

Hey guys,

I use guile 2.0.6, compiled on macbook pro 7.1 osx 10.8.2

I've compiled guild via home-brew package manager.

Here is the link to brew's formula with compilation options:
https://github.com/mxcl/homebrew/blob/master/Library/Formula/guile.rb

Best,
Jozef
On Nov 29, 2012, at 11:11 PM, Ludovic Courtès <ludo <at> gnu.org> wrote:

> Hi,
> 
> Jozef Chraplewski <jozef <at> applicake.com> skribis:
> 
>> The solution is trivial:
>> 
>> (define (problem-48 limit)
>> (define (F)
>>   (let loop ((n 1)
>>              (sum 0))
>>     (if (<= n limit)
>>         (loop (+ n 1) (+ sum (expt n n)))
>>         sum)))
>> 
>> (let* ((str (number->string (F)))
>>          (len (string-length str)))
>>   (substring str (- len 10) len)))
>> 
>> (display (problem-48 1000))
>> (newline)
>> 
>> 
>> The proper answer is 9110846700 but guile returns 6457854188
> 
> I also get 9110846700 with 2.0.6+ and 1.8.8+.  What version do you use?
> 
> (Bigloo 3.2a returns 5842605292, though.)
> 
> Ludo’.

Message #20 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: ludo <at> gnu.org (Ludovic Courtès)
To: Jozef Chraplewski <jozef <at> applicake.com>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Fri, 30 Nov 2012 17:27:09 +0100

Jozef Chraplewski <jozef <at> applicake.com> skribis:

> I use guile 2.0.6, compiled on macbook pro 7.1 osx 10.8.2

What compiler and what version of GMP is it?

Thanks,
Ludo’.

Message #23 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: Jozef Chraplewski <jozef <at> applicake.com>
Cc: Ludovic Courtès <ludo <at> gnu.org>, 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Fri, 30 Nov 2012 12:33:35 -0500

Jozef Chraplewski <jozef <at> applicake.com> writes:
> I use guile 2.0.6, compiled on macbook pro 7.1 osx 10.8.2
>
> I've compiled guild via home-brew package manager.

Could you please run "make check" in the build directory and show us the
output if any errors are reported?

    Thanks!
      Mark

Message #26 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: Jozef Chraplewski <jozef <at> applicake.com>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Sat, 01 Dec 2012 00:22:41 -0500

Hi Jozef,

Jozef Chraplewski <jozef <at> applicake.com> writes:
> It looks that guile returns incorrect results when it works with really big numbers.

Please disregard my earlier request.  Can you please run the following
code and send us the output?

  (let ((modulus (expt 10 10)))
    (define (last10 n) (modulo n modulus))
    (let loop ((n 1) (sum 0))
      (if (> n 1000)
          (last10 sum)
          (let* ((term (expt n n))
                 (sum (+ sum term)))
            (format #t "~4 <at> a ~10 <at> a ~10 <at> a~%" n (last10 term) (last10 sum))
            (loop (+ n 1) sum)))))

    Thanks,
      Mark

Message #29 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: Jozef Chraplewski <jozef <at> applicake.com>
To: Mark H Weaver <mhw <at> netris.org>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Mon, 3 Dec 2012 17:35:17 +0100

[Message part 1 (text/plain, inline)]

Hey guys,

Sorry for the late response, I was offline during the weekend.

@Mark, you can find output in attachment.

gcc -v

Using built-in specs.
Target: i686-apple-darwin11
Configured with: /private/var/tmp/llvmgcc42/llvmgcc42-2336.11~67/src/configure --disable-checking --enable-werror --prefix=/Applications/Xcode.app/Contents/Developer/usr/llvm-gcc-4.2 --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-prefix=llvm- --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin11 --enable-llvm=/private/var/tmp/llvmgcc42/llvmgcc42-2336.11~67/dst-llvmCore/Developer/usr/local --program-prefix=i686-apple-darwin11- --host=x86_64-apple-darwin11 --target=i686-apple-darwin11 --with-gxx-include-dir=/usr/include/c++/4.2.1
Thread model: posix
gcc version 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.11.00)

brew info gmp

gmp: stable 5.0.5
http://gmplib.org/
/usr/local/Cellar/gmp/5.0.5 (11 files, 2.3M) *
https://github.com/mxcl/homebrew/commits/master/Library/Formula/gmp.rb
==> Options
--32-bit
	Build 32-bit only


Best,
Jozef

[output.txt (text/plain, attachment)]

[Message part 3 (text/plain, inline)]

On Dec 1, 2012, at 6:22 AM, Mark H Weaver <mhw <at> netris.org> wrote:

>  (let ((modulus (expt 10 10)))
>    (define (last10 n) (modulo n modulus))
>    (let loop ((n 1) (sum 0))
>      (if (> n 1000)
>          (last10 sum)
>          (let* ((term (expt n n))
>                 (sum (+ sum term)))
>            (format #t "~4 <at> a ~10 <at> a ~10 <at> a~%" n (last10 term) (last10 sum))
>            (loop (+ n 1) sum)))))

Message #32 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: Jozef Chraplewski <jozef <at> applicake.com>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Mon, 03 Dec 2012 19:13:48 -0500

[Message part 1 (text/plain, inline)]

Hi Jozef,

I guess that on your system, (* 65536 65536) evaluates to 0.
Is that right?

If so, I believe the problem is caused by an aggressive optimization in
recent versions of Clang, which breaks Guile's logic for detecting
overflow when multiplying two fixnums.

Currently, Guile computes kk = xx * yy and checks for overflow by
verifying that kk / xx == yy.

I believe that Clang is optimizing out the check, because recent C
standards permit C implementations to assume that signed integer
arithmetic will never overflow.  For details, see:
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

One solution is to compile with the "-fwrapv" option, which should
disable the optimization.

Another solution is to apply the following patch.

Jozef, would you be willing to test this patch and tell me if it fixes
the problem?

   Many thanks,
      Mark

[FIXNUM_PRODUCT_OVERFLOW_FIX.patch (text/x-diff, inline)]

diff --git a/libguile/numbers.c b/libguile/numbers.c
index 52e227f..66c95db 100644
--- a/libguile/numbers.c
+++ b/libguile/numbers.c
@@ -7640,10 +7640,16 @@ scm_product (SCM x, SCM y)
       if (SCM_LIKELY (SCM_I_INUMP (y)))
 	{
 	  scm_t_inum yy = SCM_I_INUM (y);
-	  scm_t_inum kk = xx * yy;
-	  SCM k = SCM_I_MAKINUM (kk);
-	  if ((kk == SCM_I_INUM (k)) && (kk / xx == yy))
-	    return k;
+#if SCM_I_FIXNUM_BIT < 32 && SCM_HAVE_T_INT64
+          scm_t_int64 kk = xx * (scm_t_int64) yy;
+          if (SCM_FIXABLE (kk))
+            return SCM_I_MAKINUM (kk);
+#else
+          scm_t_inum axx = (xx > 0) ? xx : -xx;
+          scm_t_inum ayy = (yy > 0) ? yy : -yy;
+          if (SCM_MOST_POSITIVE_FIXNUM / axx >= ayy)
+            return SCM_I_MAKINUM (xx * yy);
+#endif
 	  else
 	    {
 	      SCM result = scm_i_inum2big (xx);

Message #35 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: Jozef Chraplewski <jozef <at> applicake.com>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Wed, 05 Dec 2012 11:20:41 -0500

I wrote:
> I guess that on your system, (* 65536 65536) evaluates to 0.
> Is that right?

I should have mentioned that if you're on a 64-bit system, then it may
instead be the case that (* (expt 2 32) (expt 2 32)) evaluates to 0.
Same bug either way, and the rest of my previous email still applies.

    Thanks,
      Mark


> If so, I believe the problem is caused by an aggressive optimization in
> recent versions of Clang, which breaks Guile's logic for detecting
> overflow when multiplying two fixnums.
>
> Currently, Guile computes kk = xx * yy and checks for overflow by
> verifying that kk / xx == yy.
>
> I believe that Clang is optimizing out the check, because recent C
> standards permit C implementations to assume that signed integer
> arithmetic will never overflow.  For details, see:
> http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
>
> One solution is to compile with the "-fwrapv" option, which should
> disable the optimization.
>
> Another solution is to apply the following patch.
>
> Jozef, would you be willing to test this patch and tell me if it fixes
> the problem?
>
>    Many thanks,
>       Mark
>
>
>
> diff --git a/libguile/numbers.c b/libguile/numbers.c
> index 52e227f..66c95db 100644
> --- a/libguile/numbers.c
> +++ b/libguile/numbers.c
> @@ -7640,10 +7640,16 @@ scm_product (SCM x, SCM y)
>        if (SCM_LIKELY (SCM_I_INUMP (y)))
>  	{
>  	  scm_t_inum yy = SCM_I_INUM (y);
> -	  scm_t_inum kk = xx * yy;
> -	  SCM k = SCM_I_MAKINUM (kk);
> -	  if ((kk == SCM_I_INUM (k)) && (kk / xx == yy))
> -	    return k;
> +#if SCM_I_FIXNUM_BIT < 32 && SCM_HAVE_T_INT64
> +          scm_t_int64 kk = xx * (scm_t_int64) yy;
> +          if (SCM_FIXABLE (kk))
> +            return SCM_I_MAKINUM (kk);
> +#else
> +          scm_t_inum axx = (xx > 0) ? xx : -xx;
> +          scm_t_inum ayy = (yy > 0) ? yy : -yy;
> +          if (SCM_MOST_POSITIVE_FIXNUM / axx >= ayy)
> +            return SCM_I_MAKINUM (xx * yy);
> +#endif
>  	  else
>  	    {
>  	      SCM result = scm_i_inum2big (xx);

Message #38 received at 13031 <at> debbugs.gnu.org (full text, mbox):

From: Jozef Chraplewski <jozef <at> applicake.com>
To: Mark H Weaver <mhw <at> netris.org>
Cc: 13031 <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Fri, 7 Dec 2012 11:40:16 +0100

Hey Mark,

Yes, I use 64-bit machine and (* (expt 2 32) (expt 2 32)) produces 0 (without the patch).

I've applied your fix and it works perfectly.
I suppose that you will add the patch to the next stable version (2.0.8 ??)

Thanks for help and great work!

Best,
Jozef

On Dec 5, 2012, at 5:20 PM, Mark H Weaver <mhw <at> netris.org> wrote:

> I wrote:
>> I guess that on your system, (* 65536 65536) evaluates to 0.
>> Is that right?
> 
> I should have mentioned that if you're on a 64-bit system, then it may
> instead be the case that (* (expt 2 32) (expt 2 32)) evaluates to 0.
> Same bug either way, and the rest of my previous email still applies.
> 
>    Thanks,
>      Mark
> 
> 
>> If so, I believe the problem is caused by an aggressive optimization in
>> recent versions of Clang, which breaks Guile's logic for detecting
>> overflow when multiplying two fixnums.
>> 
>> Currently, Guile computes kk = xx * yy and checks for overflow by
>> verifying that kk / xx == yy.
>> 
>> I believe that Clang is optimizing out the check, because recent C
>> standards permit C implementations to assume that signed integer
>> arithmetic will never overflow.  For details, see:
>> http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
>> 
>> One solution is to compile with the "-fwrapv" option, which should
>> disable the optimization.
>> 
>> Another solution is to apply the following patch.
>> 
>> Jozef, would you be willing to test this patch and tell me if it fixes
>> the problem?
>> 
>>   Many thanks,
>>      Mark
>> 
>> 
>> 
>> diff --git a/libguile/numbers.c b/libguile/numbers.c
>> index 52e227f..66c95db 100644
>> --- a/libguile/numbers.c
>> +++ b/libguile/numbers.c
>> @@ -7640,10 +7640,16 @@ scm_product (SCM x, SCM y)
>>       if (SCM_LIKELY (SCM_I_INUMP (y)))
>> 	{
>> 	  scm_t_inum yy = SCM_I_INUM (y);
>> -	  scm_t_inum kk = xx * yy;
>> -	  SCM k = SCM_I_MAKINUM (kk);
>> -	  if ((kk == SCM_I_INUM (k)) && (kk / xx == yy))
>> -	    return k;
>> +#if SCM_I_FIXNUM_BIT < 32 && SCM_HAVE_T_INT64
>> +          scm_t_int64 kk = xx * (scm_t_int64) yy;
>> +          if (SCM_FIXABLE (kk))
>> +            return SCM_I_MAKINUM (kk);
>> +#else
>> +          scm_t_inum axx = (xx > 0) ? xx : -xx;
>> +          scm_t_inum ayy = (yy > 0) ? yy : -yy;
>> +          if (SCM_MOST_POSITIVE_FIXNUM / axx >= ayy)
>> +            return SCM_I_MAKINUM (xx * yy);
>> +#endif
>> 	  else
>> 	    {
>> 	      SCM result = scm_i_inum2big (xx);

Message #43 received at 13031-done <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: Jozef Chraplewski <jozef <at> applicake.com>
Cc: 13031-done <at> debbugs.gnu.org
Subject: Re: bug#13031: large numbers
Date: Fri, 07 Dec 2012 12:06:41 -0500

Hi Jozef,

Jozef Chraplewski <jozef <at> applicake.com> writes:
> Yes, I use 64-bit machine and (* (expt 2 32) (expt 2 32)) produces 0 (without the patch).
>
> I've applied your fix and it works perfectly.

Excellent!  Thanks for bringing this problem to our attention,
and for helping us track it down :)

> I suppose that you will add the patch to the next stable version (2.0.8 ??)

Yes.

   Thanks again,
       Mark

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.