(defun fib (n)
  "Calculate the nth Fibonacci number using tail recursion."
  (labels ((fib-tail (a b count)
             (if (zerop count)
                 b
                 (fib-tail b (+ a b) (1- count)))))
    (if (<= n 2)
        1
        (fib-tail 1 1 (- n 2)))))

(defun matrix-multiply (a b)
  (destructuring-bind ((a11 a12) (a21 a22)) a
    (destructuring-bind ((b11 b12) (b21 b22)) b
      (list (list (+ (* a11 b11) (* a12 b21))
                  (+ (* a11 b12) (* a12 b22)))
            (list (+ (* a21 b11) (* a22 b21))
                  (+ (* a21 b12) (* a22 b22)))))))

(defun matrix-power (m n)
  (declare (type fixnum n))
  (cond ((= n 1) m)
        (t (let* ((half (matrix-power m (floor n 2)))
                  (squared (matrix-multiply half half)))
             (if (oddp n)
                 (matrix-multiply squared m)
                 squared)))))

(defun fib-nth (n)
  (declare (type fixnum n))
  (if (<= n 2)
      1
      (destructuring-bind ((result b) (c d))
          (matrix-power '((1 1) (1 0)) (- n 1))
        (declare (ignore b c d))
        result)))

(defun digits-in-number (n)
  "Count the number of digits in a number."
  (length (write-to-string n)))

(defun find-fib-index-0 (digit-count fib-f)
  "Find the index of the first Fibonacci number with the specified number of digits."
  (labels ((helper (index)
             (if (>= (digits-in-number
                      (funcall fib-f index))
                     digit-count)
                 index
                 (helper (1+ index)))))
    (helper 1)))

(defmacro find-fib-index (digit-count)
  `(find-fib-index-0 ,digit-count #'fib))
  
(defmacro find-fib-nth-index (digit-count)
  `(find-fib-index-0 ,digit-count #'fib-nth))

; SLIME 2.28
CL-USER> (time (find-fib-index 1000))
Evaluation took:
  0.456 seconds of real time
  
4782
CL-USER> (time (find-fib-nth-index 1000))
Evaluation took:
  0.080 seconds of real time
  
4782
CL-USER> (time (binary-search-fib-index 1000))
Evaluation took:
  0.001 seconds of real time
  
4782
CL-USER> 

— Me@2024-12-10 07:23:47 PM

.

.

2024.12.11 Wednesday (c) All rights reserved by ACHK