Created
May 9, 2011 16:58
-
-
Save swannodette/962877 to your computer and use it in GitHub Desktop.
sieve.clj
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (ns clj-play.seive) | |
| (set! *warn-on-reflection* true) | |
| (set! *unchecked-math* true) | |
| (defmacro iloop [[b t n] & body] | |
| `(loop [~@b] | |
| (when ~t | |
| ~@body | |
| (recur ~n)))) | |
| (defmacro lte [x y] | |
| `(. clojure.lang.Numbers (lte ~x ~y))) | |
| (defn count-primes [^long n] | |
| (let [c (inc n) | |
| ^"[Z" prime? (make-array Boolean/TYPE c)] | |
| (iloop [(i 2) (<= i n) (inc i)] | |
| (aset prime? i true)) | |
| (iloop [(i 2) (<= (* i i) n) (inc i)] | |
| (if (identical? (aget prime? i) true) | |
| (iloop [(j i) (<= (* i j) n) (inc j)] | |
| (aset prime? (* i j) false)))) | |
| (let [primes (loop [i 2 c 0] | |
| (if (lte i n) | |
| (let [ni (inc i) | |
| nc (if (identical? (aget prime? i) true) | |
| (inc c) | |
| c)] | |
| (recur ni nc)) | |
| c))] | |
| primes))) | |
| (comment | |
| ;; 2s | |
| (do | |
| (dotimes [_ 10] | |
| (time | |
| (count-primes 1e8)))) | |
| ) |
Author
Thanks for the great post. I can follow everything but the "[Z" bit... ^"[Z" assigns the metadata {:tag "[Z"} to prime?, correct? What does the compiler do with that metadata?
Nice post!
The use of Java BitSets can further improve performance (30 % on my system):
https://gist.github.com/964676/b26344d3d09dcf66ea66000ec207751aa61bd9e3
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
heh, yeah thanks.