Title: Memoization in Racket
Date: 2017-04-01T00:00:00
Tags: Racket, Dynamic Programming, Memoization
Authors: Henry Brooks

After working on totalOnes last week I thought I would explore how I could implement memoization in racket. Working off an example I found here I converted the standard definition of the Fibonacci equation into an iterated form and a memoization form.

(define (fib n)
  (cond [(= 0 n) 0]
        [(= 1 n) 1]
        [else (+ (fib (- n 1)) (fib (- n 2)))]))

(define (fib2 n)
  (fib2-iter 0 1 n))
(define (fib2-iter a b c)
  (cond [(= c 0) a]
        [else (fib2-iter b (+ a b) (sub1 c))]))

(define (fib3 n)
  (define cache (make-vector 1000 -1))
  (vector-set! cache 0 0)
  (vector-set! cache 1 1)
  (define (mfib i)
    (if (= (vector-ref cache i) -1)
        (vector-set! cache i (+ (mfib (- i 1)) (mfib (- i 2))))
        (vector-ref cache i))
    (vector-ref cache i))
  (mfib n))

;(time (fib 40))
(time (fib2 400))
(time (fib3 400))

While the standard Fibonacci formula performed as bad as it always does for large values, I was quite surprised by the speed up generated by the memoization method. Memoization uses almost the exact formula for calculating Fibonacci yet it has a speed up that is even with the iterative version into the 10's of thousands.

Unfortunately I was never able to find an iterative version of totalOnes code however, there is still a significant increase in speed associated with converting the equation to use memoization.

(define (a000788 n)
  (cond [(= n 0) 0]
        [else (let ([n2 (quotient n 2)])
                (+ (- n n2)
                   (a000788 n2)
                   (a000788 (- n n2 1))))]))

(time (a000788 1000000))
> cpu time: 78 real time: 63 gc time: 0
> 9884999

(define (a2 n)
  (define cache (make-vector (add1 n) -1))
  (vector-set! cache 0 0)
  (define (ma i)
    (if (= (vector-ref cache i) -1)
        (vector-set! cache i (let ([i2 (quotient i 2)])
                               (+ (- i i2)
                                  (ma i2)
                                  (ma (- i i2 1)))))
        (vector-ref cache i))
    (vector-ref cache i))
  (ma n))
  
(time (a2 1000000))
> cpu time: 16 real time: 19 gc time: 16
> 9884999