On Sun, Jun 29, 2003 at 08:20:52AM 0500, Paul F. Dietz wrote:
> Adam Warner has found this bug in cmucl/sbcl (as seen on c.l.l.)
>
> nth should be able to handle circular lists, as should nthcdr,
> so they need to be able to handle arbitrarily large bignums.
>
> To make this run in a sane amount of time, I suggest the implementation
> do the following when the argument is a bignum (assuming proper lists
> cannot be BIGNUM elements long):
>
> To compute (nth x N) where N is a bignum:
>
> (1) Determine if the list is circular. If it is not, return nil.
> (2) If it is, find the smallest i and j (i < j) s.t. (nthcdr x i)
> is eq to (nthcdr x j). Return (nth x (+ i (mod ( N i) ( j i)))).
>
> This will run in O(j) time if the right algorithm is used to find i and j.
>
> Paul Dietz
I agree that we should not fail outright on bignum values, but I'm not
convinced that we should go to the trouble of computing remainders
with respect to cycle lengths to make this efficient. It would have a
certain clever coolness factor, yes, but it would be quite a lot of
complexity to support an operation which, efficiencywise, deserves to
lose. I don't think an implementation needs to be responsible for
optimizing this any more than it's responsible for optimizing
(let ((counter 0))
(dotimes (i 12345678901234)
(incf counter))
counter)
(Furthermore, even if we were to optimize bignum NTH as cleverly as
you suggest, the operation could still tend to lose efficiencywise. I
might be able to say this with more confidence if I could think of a
situation where a sane app programmer would intentionally rely on this
behavior in the first place: but I suspect that in most such
situations the app programmer would have enough global knowledge of
the relevant cycle length that he could calculate the cycle length
once and for all, so that he could then compute his modulothecycle
indices more efficiently than we can, because he could avoid the
overhead of reexploring the cycle on every NTH call.)
(Furthermore, I don't see any appealing way to optimize NTH in the
range of big FIXNUMs, so we'd tend to end up with the surprising
behavior that for
(defvar *cycle* #1=(1 . #1#))
we'd find
(nth (floor mostpositivefixnum 20) *cycle*)
to be unreasonably slow (like .13 seconds:) while
(nth (1+ mostpositivefixnum) *cycle*)
would be much faster.)

William Harold Newman <william.newman@...>
hoping that I'm not missing the joke
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C B9 25 FB EE E0 C3 E5 7C
