On Mon, Sep 12, 2011 at 12:54 AM, Alan Malloy <a...@malloys.org> wrote:
> Integer overflow.
>
> user> (mod 9876543210 (bigint (Math/pow 2 32)))
> 1286608618
Oops.
But nth can probably be fixed while keeping good performance:
(defn- small-drop [s n]
(loop [n (int n) s (seq s)]
(if (zero? n) s (recur (dec n) (next s)))))
(def pow231 (bigint (Math/pow 2 31)))
(defn my-nth [s n]
(let [s (small-drop s (rem n pow231))]
(loop [n (quot n pow231) s s]
(if s
(if (zero? n)
(first s)
(recur (dec n) (small-drop s pow231)))))))
Given a bigint n, this does only two arithmetic operations on bigints
at the start and one possibly-bigint dec every 2^31 items, instead of
doing a bigint dec every single item. So it should be nearly as fast
for large n as for small n, per item.
I'm guessing there are similar bugs in drop, take, and so forth with
large n and large (or infinite) seqs. They should all be fixed.
Note: the above code is untested, and (nth n too-short-a-seq) returns
nil. For further speed you'd want small-drop to use an unchecked dec.
You'd also want my-nth to punt to the special implementations for
vectors and other random-access seqables, and maybe change the
behavior on long seqs.
--
Protege: What is this seething mass of parentheses?!
Master: Your father's Lisp REPL. This is the language of a true
hacker. Not as clumsy or random as C++; a language for a more
civilized age.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
