Skip to content

Instantly share code, notes, and snippets.

@oscardelben

oscardelben/SICP Exercise 1.10

Created March 19, 2009 21:28
Show Gist options
  • Save oscardelben/82074 to your computer and use it in GitHub Desktop.
Save oscardelben/82074 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
SICP Exercise 1.10
Exercise 1.10
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
;(A 1 10)
;(A 0 (A 1 9))
;(* 2 (A 0 (A 1 8)))
;(* 2 (* 2 (A 0 (A 1 7))))
;(* 2 (* 2 (* 2 (A 0 (A 1 6)))))
;(* 2 (* 2 (* 2 (* 2 (A 0 (A 1 5))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 4)))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 3))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 2)))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 1))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 2)))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 4))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 8)))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 16))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 32)))))
;(* 2 (* 2 (* 2 (* 2 64))))
;(* 2 (* 2 (* 2 128)))
;(* 2 (* 2 256))
;(* 2 512)
;1024
;(A 2 4)
;(A 1 (A 2 3))
;(A 1 (A 1 (A 2 2)))
;(A 1 (A 1 (A 1 (A 2 1))))
;(A 1 (A 1 (A 1 2)))
;(A 1 (A 1 (A 0 (A 1 1))))
;(A 1 (A 1 (* 2 2)))
;(A 1 (A 1 4))
;(A 1 (A 0 (A 1 3)))
;(A 1 (* 2 (A 0 (A 1 2))))
;(A 1 (* 2 (* 2 (A 0 (A 1 1)))))
;(A 1 (* 2 (* 2 (* 2 2))))
;(A 1 (* 2 (* 2 4)))
;(A 1 (* 2 8))
;(A 1 16)
;(A 0 (A 1 15))
;(* 2 (A 0 (A 1 14)))
;(* 2 (* 2 (A 0 (A 1 13))))
;(* 2 (* 2 (* 2 (A 0 (A 1 12)))))
;(* 2 (* 2 (* 2 (* 2 (A 0 (A 1 11))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 10)))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 9))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 8)))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 7))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 6)))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 5))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 4)))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 3))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 2)))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 1))))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 2)))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 4))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 8)))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 16))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 32)))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 64))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 128)))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 256))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 512)))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 1024))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 2048)))))
;(* 2 (* 2 (* 2 (* 2 4096))))
;(* 2 (* 2 (* 2 8192)))
;(* 2 (* 2 16384))
;(* 2 32768)
;65536
;(A 3 3)
;(A 2 (A 3 2))
;(A 2 (A 2 (A 3 1)))
;(A 2 (A 2 2))
;(A 2 (A 1 (A 2 1)))
;(A 2 (A 1 2))
;(A 2 (A 0 (A 1 1)))
;(A 2 (* 2 2))
;(A 2 4)
;(A 1 (A 2 3))
;(A 1 (A 1 (A 2 2)))
;(A 1 (A 1 (A 1 (A 2 1))))
;(A 1 (A 1 (A 1 2)))
;(A 1 (A 1 (A 0 (A 1 1))))
;(A 1 (A 1 (* 2 2)))
;(A 1 (A 1 4))
;(A 1 (A 0 (A 1 3)))
;(A 1 (* 2 (A 0 (A 1 2))))
;(A 1 (* 2 (* 2 (A 0 (A 1 1)))))
;(A 1 (* 2 (* 2 (* 2 2))))
;(A 1 (* 2 (* 2 4)))
;(A 1 (* 2 8))
;(A 1 16)
;(A 0 (A 1 15))
;(* 2 (A 0 (A 1 14)))
;(* 2 (* 2 (A 0 (A 1 13))))
;(* 2 (* 2 (* 2 (A 0 (A 1 12)))))
;(* 2 (* 2 (* 2 (* 2 (A 0 (A 1 11))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 10)))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 9))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 8)))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 7))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 6)))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 5))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 4)))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 3))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 2)))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 0 (A 1 1))))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 2)))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 4))))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 8)))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 16))))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 32)))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 64))))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 128)))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 256))))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 512)))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 (* 2 1024))))))
;(* 2 (* 2 (* 2 (* 2 (* 2 2048)))))
;(* 2 (* 2 (* 2 (* 2 4096))))
;(* 2 (* 2 (* 2 8192)))
;(* 2 (* 2 16384))
;(* 2 32768)
;65536
(f n) computes 2n
(g n) computes 2^n
(h n) computes 2^2^2... I don't know how to express this, but you should count n-1 exponentials, so for example (h 4) is 2^2^2^2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment