Steel Bank Common Lisp

(bignum) GCD can return negative values

Reported by Paul Khuong on 2009-08-14
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Medium
Paul Khuong

Bug Description

On a 32 bit build:

(gcd 20286123923750474264166990598656 680564733841876926926749214863536422912)
=> -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
(+ 20286123923750474264166990598145/680564733841876926926749214863536422912)
=> -39621335788575145047201153513/-1329227995784915872903807060280344576

Paul Khuong (pvk) wrote :

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.

Changed in sbcl:
status: Confirmed → In Progress
assignee: nobody → Paul Khuong (pvk)
Paul Khuong (pvk) on 2010-04-26
Changed in sbcl:
status: In Progress → Fix Committed
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers