I changed "integer-length" to use numberOfLeadingZeros or bitLength methods.
It reduces execution time a bit. So that of "exact-integer-sqrt" too.
;; test with name integer-length-new
(defmulti ;; #^{:private true}
integer-length-new class)
(defmethod integer-length-new java.lang.Integer [n]
(- 32 (Integer/numberOfLeadingZeros n)))
(defmethod integer-length-new java.lang.Long [n]
(- 64 (Long/numberOfLeadingZeros n)))
(defmethod integer-length-new java.math.BigInteger [n]
(.bitLength n))
(defn time-f [f start length]
(time (dorun (map f (range start (+ start length))))))
;; Integer case
(time-f integer-length (expt 2 10) (expt 10 6))
"Elapsed time: 435.079883 msecs"
(time-f integer-length-new (expt 2 10) (expt 10 6))
"Elapsed time: 415.858854 msecs"
;; Long case
(time-f integer-length (expt 2 40) (expt 10 6))
"Elapsed time: 746.825107 msecs"
(time-f integer-length-new (expt 2 40) (expt 10 6))
"Elapsed time: 612.915711 msecs"
;; BigInteger case
(time-f integer-length (expt 2 70) (expt 10 5))
"Elapsed time: 1263.520978 msecs"
(time-f integer-length-new (expt 2 70) (expt 10 5))
"Elapsed time: 1006.090455 msecs"
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
--- math.clj.~master~ 2009-03-30 10:37:00.000000000 +0900
+++ math.clj 2009-03-30 11:04:02.000000000 +0900
@@ -134,11 +134,11 @@
; Length of integer in binary, used as helper function for sqrt.
(defmulti #^{:private true} integer-length class)
(defmethod integer-length java.lang.Integer [n]
- (count (Integer/toBinaryString n)))
+ (- 32 (Integer/numberOfLeadingZeros n)))
(defmethod integer-length java.lang.Long [n]
- (count (Long/toBinaryString n)))
+ (- 64 (Long/numberOfLeadingZeros n)))
(defmethod integer-length java.math.BigInteger [n]
- (count (. n toString 2)))
+ (.bitLength n))
;; Produces the largest integer less than or equal to the square root of n
;; Input n must be a non-negative integer
