Solution to Exercise 1.10:
> (A 1 10)
1024
> (A 2 4)
65536
> (A 3 3)
65536(f n) computes 2n.
(g n) computes 2n for n>0. For n=0, it is 0.
(h n) computes h(n) such that if n=0, h(0)=0; otherwise h(n)=2h(n-1).
Posted by Ken Dyck in Programming
March 20th, 2005
Solution to SICP Exercise 1.10
8 Responses to “Solution to SICP Exercise 1.10”
-
Joe Slag says:
Actually, looks like h computes the tetration of of 2 by n. If that’s how you say it - never heard of tetration until I peeked at the wikipedia entry for the Ackermann function.
http://en.wikipedia.org/wiki/Tetration
September 8th, 2007 at 10:54 pm -
Luis C Guerrero says:
First of all let me thank you for posting your answers for discussion. As the last person just stated the answer for the (h n) function would be the tetration of 2, with the number of iterations being n. Is your mathematical definition stating this? Im a little confused if you could please explain your definition it would help me alot.
-
JasonMR says:
Actually the answer for (h n) with n >= 0 and h(0) = 0 is h(n) = 2^2^h(n-1)
-
Tim Eichner says:
It seems as though (h n) must compute a three-part function: h(0) = 0, h(1) = 2, and h(x) = 2^h(n - 1) for n > 1.
-
Tim Eichner says:
That “x” should be an “n”
-
mat-tina says:
Clarification/question for whom it might concern: The Wikipedia article on the Ackermann function seems to describe another function (which is the one that i knew of; along the lines of (A 0 n) => addition, (A 1 n) => multiplication, (A 2 n) => exponentiation, (A 4 n) => tetration). You can see the difference by observing that the SICP function only can evaluate to multiples of 2.
For those who disagree with Ken’s answer:
(define (h n) (A 2 n))
(h n)
(A 2 n)
(A 1 (A 2 (- n 1)))
(A 1 (A 1 (A 2 (- n 1))))
(A 1 (A 1 (A 1 … (A 1 (A 2 1)))))
Which equals:
(g (g (g (g … 2))))
Which we have already shown to be:
2 ^ 2 ^ 2 ^ 2 ^ … ^ 2 (n times)
2^^n (tetration), like Joe said before me. -
Tim says:
Hey, looks like a good discussion going here.
I’m not sure if this is a subject of debate or controversy in mathematics, but according to the wikipedia entry on integers, zero does not qualify as a positive integer. That would remove n = 0 from the problem domain.
-
a says:
I agree with this so far: h(0) = 0, h(1) = 2, and h(x) = 2^h(n - 1) for n > 1.
What do you make of this answer
(h n): 2^{2^{n}}from http://community.schemewiki.org/?sicp-ex-1.10
?
For n=3, I got 2^4…not 2^8, so I would say the answer is h(0) = 0, h(1) = 2, and h(x) = 2^h(n - 1) for n > 1.