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