#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))