From: Paul F. D. <di...@dl...> - 2003-06-29 13:12:31
Attachments:
Implementation limits when accessing circular lists
|
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 |