From: William H. N. <wil...@ai...> - 2003-06-29 15:03:00
|
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 modulo-the-cycle 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 most-positive-fixnum 20) *cycle*) to be unreasonably slow (like .13 seconds:-) while (nth (1+ most-positive-fixnum) *cycle*) would be much faster.) -- William Harold Newman <wil...@ai...> 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 |