Author: smokeink. Date 2018-03-01 12:41:32, views: 201, Raw

(defun log2 (x) "Use the fact that log2 x = n + log2 (x / 2^n) and choose n so that there are preserved as many significant digits as needed in x. In this case 100 digits, but it could be fewer according to the floating-point format used." ;; Let's take x=2^200+1 as an example ;; (integer-length #b1001) ==> 4 (integer-length 2) ==> 2 ;; (integer-length x) ==> 201 (let ((n (- (integer-length x) 100))) ; so n equals (- 201 100) ==> 101 ; (ash x (- n)) means x/2^n=â””(2^200+1)/x^101â”˜=2^100 ; which is then converted to a double float ; after that, get the binary logarithm of it ==> 100 ; finally add it to n (+ 101 100) ==> 201 (+ n (log (float (ash x (- n)) 1d0) 2)))) (defparameter x (+ (expt 3 5000) 1)) (dotimes (i 2) (setf x (+ (expt x 10) 1))) (let () (time (log x 2)) ; ==> 792481.25 (time (log2 x)) ; ==> 792481.2503605781d0 (time (1- (integer-length x)))) ; ==> 792482