[gsharp-devel] redraw buglets

[Christophe Rhodes]

Robert Strandh <strandh at labri.fr> writes:

> Christophe Rhodes writes:
>  > I had a look at sbcl's own routines, and it turns out that there is
>  > currently (and probably in sbcl-0.8.13, due out soon, but probably not
>  > in sbcl-0.8.13.1) a large avoidable inefficiency in SBCL's (and I
>  > believe also CMUCL's) BIGNUM-GCD.  
>
> Please tell me more.  I had a look at the code, and at least it seems
> that you are using the fast algorithm that only needs shifts and
> subtractions.

Yes.  It wasn't an algorithmic issue, but a type issue: the definition
of the bignum-index type (a number that is a word-index into a bignum)
was wrong: its upper bound was 2^29-1 rather than 2^24-1.  This then
caused efficiency problems when computing a bit index: since we have
to multiply by 32, the compiler had to use generic arithmetic as the
upper bound becomes 2^34-32.  (This is clearly nonsense, because the
machine only has 2^32 bits of addressable memory, so has no way of
representing a bignum with 2^34 bits :-).  However, as I say, the
improvement is fairly negligible.

Cheers,

Christophe
-- 
http://www-jcsu.jesus.cam.ac.uk/~csr21/       +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%")    (pprint #36rJesusCollegeCambridge)