Mercurial > lasercutter
comparison src/clojure/contrib/math.clj @ 10:ef7dbbd6452c
added clojure source goodness
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Sat, 21 Aug 2010 06:25:44 -0400 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
9:35cf337adfcf | 10:ef7dbbd6452c |
---|---|
1 ;;; math.clj: math functions that deal intelligently with the various | |
2 ;;; types in Clojure's numeric tower, as well as math functions | |
3 ;;; commonly found in Scheme implementations. | |
4 | |
5 ;; by Mark Engelberg (mark.engelberg@gmail.com) | |
6 ;; January 17, 2009 | |
7 | |
8 ;; expt - (expt x y) is x to the yth power, returns an exact number | |
9 ;; if the base is an exact number, and the power is an integer, | |
10 ;; otherwise returns a double. | |
11 ;; abs - (abs n) is the absolute value of n | |
12 ;; gcd - (gcd m n) returns the greatest common divisor of m and n | |
13 ;; lcm - (lcm m n) returns the least common multiple of m and n | |
14 | |
15 ;; The behavior of the next three functions on doubles is consistent | |
16 ;; with the behavior of the corresponding functions | |
17 ;; in Java's Math library, but on exact numbers, returns an integer. | |
18 | |
19 ;; floor - (floor n) returns the greatest integer less than or equal to n. | |
20 ;; If n is an exact number, floor returns an integer, | |
21 ;; otherwise a double. | |
22 ;; ceil - (ceil n) returns the least integer greater than or equal to n. | |
23 ;; If n is an exact number, ceil returns an integer, | |
24 ;; otherwise a double. | |
25 ;; round - (round n) rounds to the nearest integer. | |
26 ;; round always returns an integer. round rounds up for values | |
27 ;; exactly in between two integers. | |
28 | |
29 | |
30 ;; sqrt - Implements the sqrt behavior I'm accustomed to from PLT Scheme, | |
31 ;; specifically, if the input is an exact number, and is a square | |
32 ;; of an exact number, the output will be exact. The downside | |
33 ;; is that for the common case (inexact square root), some extra | |
34 ;; computation is done to look for an exact square root first. | |
35 ;; So if you need blazingly fast square root performance, and you | |
36 ;; know you're just going to need a double result, you're better | |
37 ;; off calling java's Math/sqrt, or alternatively, you could just | |
38 ;; convert your input to a double before calling this sqrt function. | |
39 ;; If Clojure ever gets complex numbers, then this function will | |
40 ;; need to be updated (so negative inputs yield complex outputs). | |
41 ;; exact-integer-sqrt - Implements a math function from the R6RS Scheme | |
42 ;; standard. (exact-integer-sqrt k) where k is a non-negative integer, | |
43 ;; returns [s r] where k = s^2+r and k < (s+1)^2. In other words, it | |
44 ;; returns the floor of the square root and the "remainder". | |
45 | |
46 (ns | |
47 ^{:author "Mark Engelberg", | |
48 :doc "Math functions that deal intelligently with the various | |
49 types in Clojure's numeric tower, as well as math functions | |
50 commonly found in Scheme implementations. | |
51 | |
52 expt - (expt x y) is x to the yth power, returns an exact number | |
53 if the base is an exact number, and the power is an integer, | |
54 otherwise returns a double. | |
55 abs - (abs n) is the absolute value of n | |
56 gcd - (gcd m n) returns the greatest common divisor of m and n | |
57 lcm - (lcm m n) returns the least common multiple of m and n | |
58 | |
59 The behavior of the next three functions on doubles is consistent | |
60 with the behavior of the corresponding functions | |
61 in Java's Math library, but on exact numbers, returns an integer. | |
62 | |
63 floor - (floor n) returns the greatest integer less than or equal to n. | |
64 If n is an exact number, floor returns an integer, | |
65 otherwise a double. | |
66 ceil - (ceil n) returns the least integer greater than or equal to n. | |
67 If n is an exact number, ceil returns an integer, | |
68 otherwise a double. | |
69 round - (round n) rounds to the nearest integer. | |
70 round always returns an integer. round rounds up for values | |
71 exactly in between two integers. | |
72 | |
73 | |
74 sqrt - Implements the sqrt behavior I'm accustomed to from PLT Scheme, | |
75 specifically, if the input is an exact number, and is a square | |
76 of an exact number, the output will be exact. The downside | |
77 is that for the common case (inexact square root), some extra | |
78 computation is done to look for an exact square root first. | |
79 So if you need blazingly fast square root performance, and you | |
80 know you're just going to need a double result, you're better | |
81 off calling java's Math/sqrt, or alternatively, you could just | |
82 convert your input to a double before calling this sqrt function. | |
83 If Clojure ever gets complex numbers, then this function will | |
84 need to be updated (so negative inputs yield complex outputs). | |
85 exact-integer-sqrt - Implements a math function from the R6RS Scheme | |
86 standard. (exact-integer-sqrt k) where k is a non-negative integer, | |
87 returns [s r] where k = s^2+r and k < (s+1)^2. In other words, it | |
88 returns the floor of the square root and the "remainder". | |
89 "} | |
90 clojure.contrib.math) | |
91 | |
92 (derive ::integer ::exact) | |
93 (derive java.lang.Integer ::integer) | |
94 (derive java.math.BigInteger ::integer) | |
95 (derive java.lang.Long ::integer) | |
96 (derive java.math.BigDecimal ::exact) | |
97 (derive clojure.lang.Ratio ::exact) | |
98 (derive java.lang.Double ::inexact) | |
99 (derive java.lang.Float ::inexact) | |
100 | |
101 (defmulti ^{:arglists '([base pow]) | |
102 :doc "(expt base pow) is base to the pow power. | |
103 Returns an exact number if the base is an exact number and the power is an integer, otherwise returns a double."} | |
104 expt (fn [x y] [(class x) (class y)])) | |
105 | |
106 (defn- expt-int [base pow] | |
107 (loop [n pow, y (num 1), z base] | |
108 (let [t (bit-and n 1), n (bit-shift-right n 1)] | |
109 (cond | |
110 (zero? t) (recur n y (* z z)) | |
111 (zero? n) (* z y) | |
112 :else (recur n (* z y) (* z z)))))) | |
113 | |
114 (defmethod expt [::exact ::integer] [base pow] | |
115 (cond | |
116 (pos? pow) (expt-int base pow) | |
117 (zero? pow) 1 | |
118 :else (/ 1 (expt-int base (- pow))))) | |
119 | |
120 (defmethod expt :default [base pow] (Math/pow base pow)) | |
121 | |
122 (defn abs "(abs n) is the absolute value of n" [n] | |
123 (cond | |
124 (not (number? n)) (throw (IllegalArgumentException. | |
125 "abs requires a number")) | |
126 (neg? n) (- n) | |
127 :else n)) | |
128 | |
129 (defmulti ^{:arglists '([n]) | |
130 :doc "(floor n) returns the greatest integer less than or equal to n. | |
131 If n is an exact number, floor returns an integer, otherwise a double."} | |
132 floor class) | |
133 (defmethod floor ::integer [n] n) | |
134 (defmethod floor java.math.BigDecimal [n] (.. n (setScale 0 BigDecimal/ROUND_FLOOR) (toBigInteger))) | |
135 (defmethod floor clojure.lang.Ratio [n] | |
136 (if (pos? n) (quot (. n numerator) (. n denominator)) | |
137 (dec (quot (. n numerator) (. n denominator))))) | |
138 (defmethod floor :default [n] | |
139 (Math/floor n)) | |
140 | |
141 (defmulti ^{:arglists '([n]) | |
142 :doc "(ceil n) returns the least integer greater than or equal to n. | |
143 If n is an exact number, ceil returns an integer, otherwise a double."} | |
144 ceil class) | |
145 (defmethod ceil ::integer [n] n) | |
146 (defmethod ceil java.math.BigDecimal [n] (.. n (setScale 0 BigDecimal/ROUND_CEILING) (toBigInteger))) | |
147 (defmethod ceil clojure.lang.Ratio [n] | |
148 (if (pos? n) (inc (quot (. n numerator) (. n denominator))) | |
149 (quot (. n numerator) (. n denominator)))) | |
150 (defmethod ceil :default [n] | |
151 (Math/ceil n)) | |
152 | |
153 (defmulti ^{:arglists '([n]) | |
154 :doc "(round n) rounds to the nearest integer. | |
155 round always returns an integer. Rounds up for values exactly in between two integers."} | |
156 round class) | |
157 (defmethod round ::integer [n] n) | |
158 (defmethod round java.math.BigDecimal [n] (floor (+ n 0.5M))) | |
159 (defmethod round clojure.lang.Ratio [n] (floor (+ n 1/2))) | |
160 (defmethod round :default [n] (Math/round n)) | |
161 | |
162 (defn gcd "(gcd a b) returns the greatest common divisor of a and b" [a b] | |
163 (if (or (not (integer? a)) (not (integer? b))) | |
164 (throw (IllegalArgumentException. "gcd requires two integers")) | |
165 (loop [a (abs a) b (abs b)] | |
166 (if (zero? b) a, | |
167 (recur b (mod a b)))))) | |
168 | |
169 (defn lcm | |
170 "(lcm a b) returns the least common multiple of a and b" | |
171 [a b] | |
172 (when (or (not (integer? a)) (not (integer? b))) | |
173 (throw (IllegalArgumentException. "lcm requires two integers"))) | |
174 (cond (zero? a) 0 | |
175 (zero? b) 0 | |
176 :else (abs (* b (quot a (gcd a b)))))) | |
177 | |
178 ; Length of integer in binary, used as helper function for sqrt. | |
179 (defmulti ^{:private true} integer-length class) | |
180 (defmethod integer-length java.lang.Integer [n] | |
181 (count (Integer/toBinaryString n))) | |
182 (defmethod integer-length java.lang.Long [n] | |
183 (count (Long/toBinaryString n))) | |
184 (defmethod integer-length java.math.BigInteger [n] | |
185 (count (. n toString 2))) | |
186 | |
187 ;; Produces the largest integer less than or equal to the square root of n | |
188 ;; Input n must be a non-negative integer | |
189 (defn- integer-sqrt [n] | |
190 (cond | |
191 (> n 24) | |
192 (let [n-len (integer-length n)] | |
193 (loop [init-value (if (even? n-len) | |
194 (bit-shift-left 1 (bit-shift-right n-len 1)) | |
195 (bit-shift-left 2 (bit-shift-right n-len 1)))] | |
196 (let [iterated-value (bit-shift-right (+ init-value (quot n init-value)) 1)] | |
197 (if (>= iterated-value init-value) | |
198 init-value | |
199 (recur iterated-value))))) | |
200 (> n 15) 4 | |
201 (> n 8) 3 | |
202 (> n 3) 2 | |
203 (> n 0) 1 | |
204 (> n -1) 0)) | |
205 | |
206 (defn exact-integer-sqrt "(exact-integer-sqrt n) expects a non-negative integer n, and returns [s r] where n = s^2+r and n < (s+1)^2. In other words, it returns the floor of the square root and the 'remainder'. | |
207 For example, (exact-integer-sqrt 15) is [3 6] because 15 = 3^2+6." | |
208 [n] | |
209 (if (or (not (integer? n)) (neg? n)) | |
210 (throw (IllegalArgumentException. "exact-integer-sqrt requires a non-negative integer")) | |
211 (let [isqrt (integer-sqrt n), | |
212 error (- n (* isqrt isqrt))] | |
213 [isqrt error]))) | |
214 | |
215 (defmulti ^{:arglists '([n]) | |
216 :doc "Square root, but returns exact number if possible."} | |
217 sqrt class) | |
218 (defmethod sqrt ::integer [n] | |
219 (if (neg? n) Double/NaN | |
220 (let [isqrt (integer-sqrt n), | |
221 error (- n (* isqrt isqrt))] | |
222 (if (zero? error) isqrt | |
223 (Math/sqrt n))))) | |
224 | |
225 (defmethod sqrt clojure.lang.Ratio [n] | |
226 (if (neg? n) Double/NaN | |
227 (let [numerator (.numerator n), | |
228 denominator (.denominator n), | |
229 sqrtnum (sqrt numerator)] | |
230 (if (float? sqrtnum) | |
231 (Math/sqrt n) | |
232 (let [sqrtden (sqrt denominator)] | |
233 (if (float? sqrtnum) | |
234 (Math/sqrt n) | |
235 (/ sqrtnum sqrtden))))))) | |
236 | |
237 (defmethod sqrt java.math.BigDecimal [n] | |
238 (if (neg? n) Double/NaN | |
239 (let [frac (rationalize n), | |
240 sqrtfrac (sqrt frac)] | |
241 (if (ratio? sqrtfrac) | |
242 (/ (BigDecimal. (.numerator sqrtfrac)) | |
243 (BigDecimal. (.denominator sqrtfrac))) | |
244 sqrtfrac)))) | |
245 | |
246 (defmethod sqrt :default [n] | |
247 (Math/sqrt n)) |