[gambit-list] Big number Bug?

Bradley Lucier lucier at math.purdue.edu
Thu Apr 26 09:41:24 EDT 2007


You're absolutely right, there is a bug in runtime library.  Thanks  
for reporting it.  (This code is from 1998 ;-)

Specifically, in ##exact-int.div, it assumes that the quotient of a  
fixnum by a bignum is zero, but that's not true when the fixnum is  
the least fixnum and the bignum is the negation of the least fixnum.

Debugging info follows.

Brad

Once I saw that you were using rational arithmetic, I decided to add  
code to the to top of the file to check the arguments and results of  
+, -, *, and / by

(define (proper-rational? r)
   (and (exact? r)
        (or (integer? r)
	   (let ((p (numerator r))
		 (q (denominator r)))
	     (and (exact? p) (integer? p)
		  (exact? q) (integer? q)
		  (< 0 q)
		  (= 1 (gcd  p q)))))))

(define (every? p l)
   (or (null? l)
       (and (p (car l))
	   (every? p (cdr l)))))

(define-macro (check-math-ops)
   (define (symbol-append . args)
     (string->symbol (apply string-append (map (lambda (x) (if  
(string? x) x (symbol->string x))) args))))

   `(let (,@(map (lambda (op)
		  `(,(symbol-append 'orig- op) ,op))
		'(+ - * /)))
      ,@(map (lambda (op)
	      (let ((orig-op (symbol-append 'orig- op)))
		`(set! ,op (lambda args
			     (if (not (every? proper-rational? args))
				 (error "args" ,orig-op args))
			     (let ((result (apply ,orig-op args)))
			       (if (proper-rational? result)
				   result
				   (error "result" ,orig-op args)))))))
	    '(+ - * /))))

(check-math-ops)

That showed

[brad:~/Desktop/dillo] lucier% gsi
Gambit Version 4.0 beta 22

 > (generate-proper-tail-calls #f)
 > (load "test.scm")
*** ERROR IN *, "test.scm"@34.1 -- result #<procedure #2>  
(1431655765/1073741824 -536870912)
1> ,b
0  *                         "test.scm"@34:1         (error "result"  
orig-* args)
1  #<procedure #3>           "test.scm"@61:13        (* t (car row))
2  map
3  map
4  map
5  map
6  map
7  map
8  map
9  map
...
23 (interaction)             "test.scm"@271:10       (rref M)
24 ##load
25 ##load
26 (interaction)             (console)@2:1           (load "test.scm")
1> ,e
result = 0/2
args = '(1431655765/1073741824 -536870912)
orig-+ = '#<procedure #4>
orig-- = '#<procedure #5>
orig-* = '#<procedure #2>
orig-/ = '#<procedure #6>
(current-exception-handler) = primordial-exception-handler
(current-input-port) = '#<input-output-port #7 (console)>
(current-output-port) = '#<input-output-port #7 (console)>
(current-directory) = "/Users/lucier/Desktop/dillo/"

So #<procedure #2> is orig-*, so the error is in *.  (We already knew  
it was in ##ratnum.* from the first error message.)  So I pulled out  
##ratnum.* and its associated macros from _num.scm, _num#.scm, and  
header.scm:

(##define-macro (macro-slot index struct . val)
   (if (null? val)
     `(##vector-ref ,struct ,index)
     `(##vector-set! ,struct ,index , at val)))

(##define-macro (macro-ratnum-make num den)
   `(##subtype-set!
     (##vector ,num ,den)
     (macro-subtype-ratnum)))

(##define-macro (macro-ratnum-numerator r)          `(macro-slot 0 ,r))
(##define-macro (macro-ratnum-numerator-set! r x)   `(macro-slot  
0 ,r ,x))
(##define-macro (macro-ratnum-denominator r)        `(macro-slot 1 ,r))
(##define-macro (macro-ratnum-denominator-set! r x) `(macro-slot  
1 ,r ,x))
(##define-macro (macro-subtype-ratnum)       2)

(define (ratnum.* x y)
   (let ((p (macro-ratnum-numerator x))
         (q (macro-ratnum-denominator x))
         (r (macro-ratnum-numerator y))
         (s (macro-ratnum-denominator y)))
     (step)
     (if (##eq? x y)
       (macro-ratnum-make (##* p p) (##* q q))     ; already in  
lowest form
       (let* ((gcd-ps (##gcd p s))
              (gcd-rq (##gcd r q))
              (num (##* (##quotient p gcd-ps) (##quotient r gcd-rq)))
              (den (##* (##quotient q gcd-rq) (##quotient s gcd-ps))))
         (if (##eq? den 1)
           num
           (macro-ratnum-make num den))))))

and stepped through

 > (trace ##+ ##* ##gcd ##quotient)
*** WARNING -- Rebinding global variable "##+" to an interpreted  
procedure
*** WARNING -- Rebinding global variable "##*" to an interpreted  
procedure
*** WARNING -- Rebinding global variable "##gcd" to an interpreted  
procedure
*** WARNING -- Rebinding global variable "##quotient" to an  
interpreted procedure
 > (ratnum.* 1431655765/1073741824 (##ratnum.<-exact-int -536870912))

There I found that (##gcd -536870912 1073741824) is 536870912 and  
eventually

1> ,s
| > (##quotient r gcd-rq)
| | > (##quotient -536870912 536870912)
| | 0
| 0

and if you trace why that happens, -536870912 is a fixnum (the least  
fixnum) and 536870912 is a bignum, and in ##exact-int.div we find the  
buggy code

          (if (##fixnum? x)
            (if (##fixnum? y)
              (##cons (##fixnum.quotient x y) ; note: y can't be -1
                      (##fixnum.remainder x y))
              (##cons 0 x))

so it assumes that the quotient of a fixnum with a bignum is zero,  
which, as we find out here is not true.

Brad



More information about the Gambit-list mailing list