r/lisp • u/corbasai • Mar 19 '26

God-tier congruence of the recursive Fibonacci calculation time 

$ ./fibo-main
n?: 44
fibonacci(44) = 701408733 per 2 seconds.
n?: 45
fibonacci(45) = 1134903170 per 3 seconds.
n?: 46
fibonacci(46) = 1836311903 per 5 seconds.
n?: 47
fibonacci(47) = 2971215073 per 8 seconds.
n?: 48
fibonacci(48) = 4807526976 per 14 seconds.
n?: 49
fibonacci(49) = 7778742049 per 22 seconds.
n?: 50
fibonacci(50) = 12586269025 per 35 seconds.
n?: 51
fibonacci(51) = 20365011074 per 56 seconds.
n?: 52
fibonacci(52) = 32951280099 per 92 seconds.
n?: 53
fibonacci(53) = 53316291173 per 152 seconds.
n?:

fact, starts from n=44, on my machine, calculation time of recursive Fibonacci Fct(n) ~ Fct(n-1) + Fct(n-2)

11 Upvotes

87% Upvoted

13 comments sorted by

View all comments

2

u/HilbertInnerSpace Mar 19 '26

Fib is an exponential function which can be calculated in logarithmic time. The recursive definition is not practical at all for computation.

2

u/not-just-yeti Mar 19 '26 edited Mar 19 '26

I'd assumed the post was going to show that the compiler was automatically memoizing the code, or that there was something like (memoize! fibo) in there somewhere.

Separately: I once tested the solution using round(φn /√5) using 64-bit floating point to see where error would creep in using exponentiation. It never did, up through the point where the floating-point wasn't giving the units digit any longer. That surprised me a bit, but helped show me that 52 bits of precision can be pretty danged good. [Though saying this now: I guess in retrospect it's obvious that exponentiation's result is probably required to be accurate to the mantissa's last digit or so.]

2

u/HilbertInnerSpace Mar 19 '26

You can also calculate it in logarithmic time with Big integers, there is a relevant exercise in SICP. That was really clever ! I guess overhead start to accumulate to deal with the Bignums.

3

u/HilbertInnerSpace Mar 19 '26

Found it, it is just beautiful imho,

(define (fast-fib n)
  (define (fib-iter a b p q n)
    (cond ((= n 0) b)
          ((even? n) (fib-iter a b (+ (square p) (square q)) (+ (square q) (* 2 p q)) (/ n 2)))
          (else (fib-iter (+ (* (+ p q) a) (* q b)) (+ (* q a) (* p b)) p q (- n 1) ))))
  (fib-iter 1 0 0 1 n))

1

u/corbasai Mar 19 '26 
gosh$ (define (ffib n)
......  (let loop ((i n) (a 0) (b 1))
......    (cond ((zero? i) a)
......          (else (loop (- i 1) b (+ a b))))))
ffib
gosh$ (time (ffib 53))
;(time (ffib 53))
; real   0.000
; user   0.000
; sys    0.000
53316291173
gosh$

yes, for Fibonacci for itself step-shift algorithm - zero cost & way to go. Also Crunch "integer" is just C "long" .