(bignum) GCD can return negative values
Bug #413680 reported by
Paul Khuong
This bug affects 1 person
Affects | Status | Importance | Assigned to | Milestone | |
---|---|---|---|---|---|
SBCL |
Fix Released
|
Medium
|
Paul Khuong |
Bug Description
On a 32 bit build:
(gcd 202861239237504
=> -512 ;;; Correct value, but should be positive.
This exact test case correctly returns 512 on x86-64. The problem seems to be in BIGNUM-GCD: u is negative (-1) when the accelerated GCD loop exits.
Reported by Marius Posta as
(+ 202861239237504
=> -39621335788575
Changed in sbcl: | |
status: | In Progress → Fix Committed |
Changed in sbcl: | |
status: | Fix Committed → Fix Released |
To post a comment you must log in.
After reading the reference in the source of BIGNUM-GCD (Weber, K. 1995. The accelerated integer GCD algorithm. ACM Trans. Math. Softw. 21, 1 (Mar. 1995), 111-122. DOI=http:// doi.acm. org/10. 1145/200979. 201042), I see we're misusing the algorithm. The acceleration step computes a "small" value u such that gcd(x, y) = gcd(x, y, u), but that small value isn't guaranteed to be positive. I really don't feel like making sure the implementation is otherwise correct, so unless there's a taker for the verification I'll just patch in a call to ABS.