Created
August 30, 2011 19:31
-
-
Save amalloy/1181797 to your computer and use it in GitHub Desktop.
Confusing results
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
;; As it turns out, A is much slower than B in some cases, but faster in others! Fun. | |
(time (sum-divisorsA 2000000)) => "Elapsed time: 3766.863 msecs" | |
(time (sum-divisorsB 2000000)) => "Elapsed time: 113.786 msecs" | |
(time (sum-divisorsA 200000)) => "Elapsed time: 3.233 msecs" | |
(time (sum-divisorsB 200000)) => "Elapsed time: 8.436 msecs" | |
(time (is-abundant?A 1000000)) => "Elapsed time: 14.259 msecs" | |
(time (is-abundant?B 1000000)) => "Elapsed time: 58.678 msecs" | |
;; Methods marked A use the inefficient method, yet produce results faster. | |
;; Methods marked B use the MUCH faster sum-divisors method with no other changes but gets much slower as the range you sum rises. | |
(defn is-abundant?A [num] | |
(> (sum-divisorsA num) num)) | |
(defn is-abundantB? [num] | |
(> (sum-divisorsB num) num)) | |
(defn abundantlistA [start end] | |
(filter is-abundant?A (range start end))) | |
(defn abundantlistB [start end] | |
(filter is-abundant?B (range start end))) |
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
;; Newer, faster method of summing divisors | |
(defn divisors [num] | |
"Returns a list of the Proper Divisors of given number" | |
(filter #(zero? (mod num %)) (range 1 (inc (/ num 2))))) | |
(defn sum-divisorsB [num] | |
(reduce + (divisors num))) | |
;; Original, far slower but more algorithmic method of getting sum of divisors. | |
(defn primes-to [n] | |
(take-while #(< % n) primes)) | |
(defn thorough-prime-factors [num] | |
"Returns the prime factors of a given number. 20 => (5 2 2)" | |
(loop [a (primes-to (inc (/ num 2))) | |
number num | |
factorlist '()] | |
(if (seq a) | |
(if (zero? (mod number (first a))) | |
(recur a (/ number (first a)) (conj factorlist (first a))) | |
(recur (rest a) number factorlist)) | |
factorlist))) | |
(defn sum-divisorsA [num] | |
"Returns sum of Proper Divisors (not including number itself)" | |
(let [prime-factors (partition-by identity (thorough-prime-factors num)) | |
sum (reduce * (for [[p :as ps] prime-factors] | |
(if (> (count ps) 1) | |
(-> (apply * p ps) | |
(dec) | |
(/ (dec p))) | |
(inc p))))] | |
(if (= sum 1) 1 (- sum num)))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment