#lang racket ;; The answer on the linux machines is 42 ;; The answer on my windows based machine is 34 ;; To make FIB more efficient, we can memoize it -- save the computed values. ;; It's possible to do this in many ways. ;; This version uses a global list of (input, output) pairs ;; to store the previously computed values. (define *the-memo* '()) ;; the cache (define m-fib (lambda (n) (let ((get-the-memo (member n *the-memo* ;; This specifies a custom test function for MEMBER to ;; use to determine whether input index matches some list ;; element B (lambda (index cached-pair) (equal? index (first cached-pair)))))) (if get-the-memo (second (first get-the-memo)) (let ((fib-n (if (< n 2) n (+ (m-fib (- n 1)) (m-fib (- n 2)))))) (set! *the-memo* (cons (list n fib-n) *the-memo*)) fib-n))))) (m-fib 8) ;; For A-FIB, there is no recursion involved, at least in the code below. ;; It is just necessary to recognize that the coefficients for x and y ;; from the fibonacci sequence themselves, the same as the colums with ;; the rabbits. And, if we call M-FIB, then we can let the function do ;; the heavy lifting. ;; Questions: does it matter if we run M-FIB before running A-FIB? ;; does it matter if we run A-FIB 2x with the same value N? ;; A-FIB ;; ------- ;; INPUT: X, Y, two numbers with which to create an arbitrary fibonacci value ;; INPUT: N, a natural number representing the n'th fibonacci value to calculate ;; OUTPUT: The n'th arbitrary fibonacci value. (define a-fib (lambda (x y n) (if (= n 1) x (if (= n 2) y (+ (* y (m-fib(- n 1))) (* x (m-fib(- n 2))) ))))) (a-fib 8 5 1) (a-fib 8 5 2) (a-fib 8 5 3) (a-fib 8 5 4) (a-fib 8 5 5) (a-fib 8 5 6) (a-fib 8 5 7) (a-fib 8 5 8) (a-fib 8 5 9) (a-fib 8 5 10) (a-fib 8 5 1000) (time (a-fib 8 5 7777)) (time (a-fib 8 5 7777)) ;;(time (m-fib 8888)) ;;(time (a-fib 8 5 8888))