[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