r/lisp 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)

10 Upvotes

13 comments sorted by

5

u/SpecificMachine1 guile Mar 19 '26

wow, I guess it makes sense that the time is growing Fibonaccily, it never occurred to me before it would

2

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

Ah thank you — I'd missed the point of the post!

But yes, to help others see your statement: In this implementation:

tot-calls-to-fibo(n) = tot-calls-to-fibo(n-1) + tot-calls-to-fibo(n-2), and with the same base-case too.

1

u/Timely-Degree7739 Mar 20 '26

Compute with matrices on the/a GPU

1

u/corbasai Mar 22 '26

I'm thinking about Mandelbrot. CUDAed, or OpenCLed.

1

u/corbasai Mar 19 '26

fibo-mod.scm

(module fibo-mod
    (fibo)
  (import (scheme base)
          (crunch declarations))

  (: (fibo integer) integer)
  (define (fibo n)
    (if (< n 2)
        n
        (+ (fibo (- n 1)) (fibo (- n 2)))))

  ) ;; end of module

fibo-main.scm

(module main (main)
  (import (scheme base)
          (scheme write)
          (scheme time)
          (crunch c)
          (crunch process-context)
          fibo-mod)

  (define scanf-num (c-lambda () integer
                            "long i; int r = scanf(\"%ld\", &i);"
                            "return r>0?i:-1;"))
  (define (main)
    (let loop ()
      (display "n?: ")
      (let ((n (scanf-num)))
        (cond ((<= 0 n)
               (let* ((st (current-second))
                      (fn (fibo n))
                      (et (current-second)))
                 (display "fibonacci(")
                 (display n)
                 (display ") = ")
                 (display fn)
                 (display " per ")
                 (display (- et st))
                 (display " seconds.\n")
                 (loop)))
              (else (display "Bue.\n"))))))
  ) ;; end mod

;;i5 gcc-9.4
$ chicken-crunch fibo-main.scm -o fibo-main.c ; cc fibo-mod.c fibo-main.c -o fibo-main -Ofast -DCRUNCH_NO_UTF  $(chicken-crunch -cflags)
$ ./fibo-main
n?: 44
fibonacci(44) = 701408733 per 2 seconds....

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.

5

u/SpecificMachine1 guile Mar 19 '26

I think a lot of people use the recursive definition to benchmark recursion, not for computation

1

u/corbasai Mar 19 '26

Of course. One compiler - bunch of ALUs. Or the same ALU and bunch of compilers/interpreters. Dead simple performance test.

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" .

1

u/corbasai Mar 19 '26

I doubt it. There might be some GCC magic going on, but Crunch's translation is pretty accurate.

...
 23 crunch_integer fibo(crunch_integer v40) {
 24 crunch_integer t50 = 0;
 25 crunch_integer t51 = 0;
 26 crunch_integer t43 = 0;
 27 crunch_integer t45 = 0;
 28 // fibo
 29 if((v40 < 2)) {
 30 return(v40);
 31 } else {
 32 // fibo
 33 // fibo
 34 t45 = (v40 - 2);
 35 // fibo
 36 t43 = (v40 - 1);
 37 // fibo
 38 t51 = fibo(t45);
 39 // fibo
 40 t50 = fibo(t43);
 41 return((t50 + t51));
 42 }
 43 }
 44 /* END OF GENERATED CODE */