this post was submitted on 21 Oct 2023
1 points (100.0% liked)

Lisp

53 readers
3 users here now

founded 1 year ago
MODERATORS
 

sbcl-lisp : 0.7s

racket-scheme : 0.7s

ccl-lisp : 6s

kawa-scheme : 14s

abcl-lisp : 45s

you are viewing a single comment's thread
view the rest of the comments
[–] zyni-moe@alien.top 1 points 1 year ago

What is purpose of this? Optimize a function which uses a terrible algorithm? Why not use a good algorithm? In Racket for instance

(define (memoize/1 f)
  (define h (make-hasheqv))
  (λ (a)
    (hash-ref! h a (thunk (f a)))))

(define fib
  (memoize/1
   (λ (x)
     (if (< x 2) 
         1
         (+ (fib (- x 2)) 
            (fib (- x 1)))))))

And now

> (time (fib 39))
cpu time: 0 real time: 0 gc time: 0
102334155
> (time (fib 50000))
cpu time: 77 real time: 88 gc time: 29
174387413787277868303885543...

(10,000 digit number, results are from cold Racket so memo table was empty initially.)

Is entertaining then to try to compute say (log (fib 500000) 10). Bignums tend to get pretty slow then.