45 lines
1.2 KiB
Clojure
45 lines
1.2 KiB
Clojure
(ns cyclelengths
|
|
(:gen-class))
|
|
|
|
(defn factorial [n]
|
|
" n! "
|
|
(apply *' (range 1 (inc n)))) ; Use *' (vs. *) to allow arbitrary length arithmetic
|
|
|
|
(defn pow [n i]
|
|
" n^i"
|
|
(apply *' (repeat i n)))
|
|
|
|
(defn analytical [n]
|
|
" Analytical Computation "
|
|
(->>(range 1 (inc n))
|
|
(map #(/ (factorial n) (pow n %) (factorial (- n %)))) ;calc n %))
|
|
(reduce + 0)))
|
|
|
|
;; Number of random times to test each n
|
|
(def TIMES 1000000)
|
|
|
|
(defn single-test-cycle-length [n]
|
|
" Single random test of cycle length "
|
|
(loop [count 0
|
|
bits 0
|
|
x 1]
|
|
(if (zero? (bit-and x bits))
|
|
(recur (inc count) (bit-or bits x) (bit-shift-left 1 (rand-int n)))
|
|
count)))
|
|
|
|
(defn avg-cycle-length [n times]
|
|
" Average results of single tests of cycle lengths "
|
|
(/
|
|
(reduce +
|
|
(for [i (range times)]
|
|
(single-test-cycle-length n)))
|
|
times))
|
|
|
|
;; Show Results
|
|
(println "\tAvg\t\tExp\t\tDiff")
|
|
(doseq [q (range 1 21)
|
|
:let [anal (double (analytical q))
|
|
avg (double (avg-cycle-length q TIMES))
|
|
diff (Math/abs (* 100 (- 1 (/ avg anal))))]]
|
|
(println (format "%3d\t%.4f\t%.4f\t%.2f%%" q avg anal diff)))
|