Some clarifications.
On Wed, Feb 16, 2011 at 8:50 PM, Ken Wesson <kwess...@gmail.com> wrote:
> Perfect squares are also worst-case (other than actual primes)
To be exact, perfect squares /of primes/. Squares of composite
integers halted on a smaller prime factor even in the original
version.
> could be a bit more efficient. (It's likely to depend on your data. If
> squares are common in the data this may help; if not the (== x y) test
> may not be worth it.)
Prime-squares would have to be common in the data. My guess would be
that the (== x y) test makes it slightly slower on typical data.
> This last of course gobbles memory remembering earlier primes. The
> "user/prime?" is required in 1.2 for the function to call the memoized
> version of itself that is created after. It might be desired to hoist
> the var lookup out of the loop
Actually, the prime? lookup should only be occurring once when
filter's arguments are evaluated anyway. The var lookups that could
actually slow things down are the zero? and rem in the closure, which
could be getting done repeatedly. So ...
(defn prime? [n]
(if-not (< n 2)
(let [x (inc (int (Math/sqrt n)))
zero? clojure.core/zero?
rem clojure.core/rem]
(not-any? #(zero? (rem n %))
(filter user/prime? (range 2 x))))))
(def prime? (memoize prime?))
seems best for frequent calls with smallish values of n; for larger
values or less frequent use the non-heap-consuming
(defn prime? [n]
(if-not (< n 2)
(let [x (inc (int (Math/sqrt n)))
zero? clojure.core/zero?
rem clojure.core/rem]
(not-any? #(zero? (rem n %))
(cons 2
(take-nth 2 (range 3 x)))))))
will be preferable and for even larger values
(defn prime? [n]
(if-not (< n 2)
(if (probable-prime? n)
(let [x (inc (int (Math/sqrt n)))
zero? clojure.core/zero?
rem clojure.core/rem]
(not-any? #(zero? (rem n %))
(filter probable-prime? (range 2 x)))))))
coupled with a suitable function definition for probable-prime? (it
should be quite fast but kill off a large swath of composite numbers).
Or you can parametrize it and make it the caller's choice, e.g.
(defn prime?
([n]
(or (== 2 n) (prime? odd? n)))
([probable-prime? n]
(if-not (< n 2)
(if (probable-prime? n)
(let [x (inc (int (Math/sqrt n)))
zero? clojure.core/zero?
rem clojure.core/rem]
(not-any? #(zero? (rem n %))
(filter probable-prime? (range 2 x))))))))
(The one-argument case works despite odd? not being a true
probable-prime test (it returns false for prime number 2) because a)
it explicitly checks for n = 2 and returns true in that case and b)
although divisibility by this prime is also not tested in the inner
loop, it is precisely divisibility by this prime that (if
(probable-prime? n) ...) ends up testing. Thus the one-argument case
ends up working basically the same as the first non-memoized
implementation in this post, checking against 2, 3, 5, 7, 9, 11, 13,
15 ...)
Another class of speedup is to generalize (cons 2 (take-nth 2 (range
...))) in the second implementation in a different way: consing the
primes below some number k onto the numbers prime to k. Example with k
= 24:
(def p-b-24 [2 3 5 7 11 13 17 19 23])
(def p-t-24 [1 5 7 11 13 17 19 23])
(defn primes-superset []
(concat
p-b-24
(mapcat #(map (partial + (* 24 %)) p-t-24) (iterate inc 1))))
user=> (take 50 (primes-superset))
(2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67
71 73 77 79 83 85 89 91 95 97 101 103 107 109 113 115 119 121 125 127
131 133 137 139 143 145)
The case k = 2 amounts to (cons 2 (take-nth 2 (range 3 ...)))
Of course, (primes-superset) returns an infinite seq. The algorithm
changes a bit more to still stop at the square root of n:
(defn prime? [n]
(if-not (< n 2)
(let [x (inc (int (Math/sqrt n)))
zero? clojure.core/zero?
rem clojure.core/rem]
(not-any? #(zero? (rem n %))
(take-while #(< % x)
(primes-superset))))))
Note that for primes-superset that returns just (iterate inc 2) the
take-while expression amounts to (range 2 x).
This can be combined with probable-prime tests or memoization, too:
use (take-while #(< % x) (primes-superset)) in place of (range 2 x) in
the first or third implementation in this post to reduce memory spent
on memoizing some of the composite numbers' compositeness or time
spent in probable-prime? in cases where probable-prime? is relatively
complex and slow. Then you might want to use
(def p-b-24 [2 3 5 7 11 13 17 19 23])
(def p-b-24s (set p-b-24))
(def p-t-24 [1 5 7 11 13 17 19 23])
(defn primes-superset []
(concat
p-b-24
(mapcat #(map (partial + (* 24 %)) p-t-24) (iterate inc 1))))
(defn prime? [n]
(or
(p-b-24s n)
(prime?* n)))
(defn prime?* [n]
(... one of earlier implementations with (range 2 x) goes here
with (range 2 x) replaced by
(take-while #(< % x) (primes-superset))))
(def prime?* (memoize prime?*)) ; if necessary.
Then numbers not either in the primes up to k or relatively prime to k
get wiped quickly, numbers higher than k that are relatively prime to
k get memoized or get a more expensive pseudo-primality test performed
on them, and numbers that survive the pseudo-primality test as well
get the full treatment. The primes up to k also don't get memoized.
--
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
