+;;; FIXME: Maybe rename this so that it's clearer that it only works
+;;; on integers?
+(defun log2 (x)
+ (declare (type integer x))
+ ;; CMUCL comment:
+ ;;
+ ;; Write x = 2^n*f where 1/2 < f <= 1. Then log2(x) = n +
+ ;; log2(f). So we grab the top few bits of x and scale that
+ ;; appropriately, take the log of it and add it to n.
+ ;;
+ ;; Motivated by an attempt to get LOG to work better on bignums.
+ (let ((n (integer-length x)))
+ (if (< n sb!vm:double-float-digits)
+ (log (coerce x 'double-float) 2.0d0)
+ (let ((f (ldb (byte sb!vm:double-float-digits
+ (- n sb!vm:double-float-digits))
+ x)))
+ (+ n (log (scale-float (coerce f 'double-float)
+ (- sb!vm:double-float-digits))
+ 2.0d0))))))
+