[Bug-openmcl] bignum gcd

[Gary Byers]

On Tue, 6 Jan 2004, bryan o'connor wrote:

> this returns #<BOGUS object ...>
>
> (gcd -4503599627370496
> 202402253307310618352495346718917307049556649764142118356901358027430339
> 567995346891960383701437124495187077864316811911389808737385793476867013
> 399940738509921517424276566361364466907742093216341239767678472745068562
> 007483424692698618103355649159556340810056512358769552333414615230502532
> 186327508646006263307707741093494784)
>
> which winds up calling #'%bignum-bignum-gcd to do the
> actual work.  i spent some time trying to figure it out,
> but it's running me in circles.
>
> do you build a special image that you can use with step?

You can either set CCL:*COMPILE-DEFINITIONS* to NIL before
defining something or (in most cases) set CCL:*SAVE-DEFINITIONS*
to T before defining something.

Whether the stepper works or not is another matter; the last time I
tried to use it, it said something smug about (funcall (lambda ()
...)), apparently unaware that LAMBDA is a macro and has been
for some time.  Somewhere on the to-do list (one of the things on
the to-do list is to put a to-do list on the website) is to implement
STEP by wrapping (maybe-step ...) around everything in compiled
code (perhaps when (OPTIMIZE (DEBUG 3)) was in effect) and getting
rid of "eval.lisp" entirely.


> i could use trace to narrow down where things started
> going wrong, but it doesn't seem to match up with the
> code in l0-bignum.lisp.  it actually seems to match up
> with the second commented out (#+fix-later) defun after it.

Until a few days ago (Saturday ?), the #+fix-later version was
current.  It tries to do the binary gcd algorithm (see
<http://www.nist.gov/dads/HTML/binaryGCD.html>) on two positive
bignums by making copies of them, making temporary buffers of
appropriate size, and doing destructive right-shift and subtraction
operations on them. I thought that it must have been neglecting to
zero memory somewhere but couldn't see where, so I decided to replace
the binary GCD implementation with a traditional Euclid's algorithm
version; it'd be slower and cons more, but nothing could go wrong ...

In the Euclid's algorithm version, if either argument is negative
it's copied to a stack-allocated buffer and the copy is used
instead.  Under some circumstances, (such as when one argument
is a multiple of the other), one of these stack allocated arguments
could be returned from the function; that's bad ...

It's not clear that the Euclid version would have failed in your
test case (since I believe that the GCD of those numbers is 1),
but I'm honestly not positive of that.  Both versions seem capable
of failing when they shouldn't, and it wasn't clear which version
you were running. (The #<BOGUS OBJECT> is a typical symptom of
returning something stack-consed.)

I think that I've found the bug in the binary version; the shifting
and subtracting terminates when at least one argument's reduced to
something that'd fit in a fixnum, but this wasn't detected correctly
and would fail about 1 time in 32, depending on the arguments.  It
passes a test case that motivated the change in the first place, but
this is complicated enough that I'd like to see it pass a few more
cases before checking anything in ...



>
> 					...bryan
>
> _______________________________________________
> Bug-openmcl mailing list
> Bug-openmcl at clozure.com
> http://clozure.com/mailman/listinfo/bug-openmcl
>
>