1. ## Ackerman function

I'm working on reading through the first chapter of SICP, I know this is not java, but I'm hoping it's fine to post this here, I know at least Jos has been through the book.

I'm having a bit of trouble tracing how it works. I get that it's a linear recursive process but I am at a bit of a sticking point. I omitted the first few evaluations, however; this is what I have so far
Java Code:
```(A -4(A -3(A -2(A -1(A 0(A 1 5))))))
(A -5(A -4(A -3(A -2(A -1(A 0(A 1 4)))))))
(A -6(A -5(A -4(A -3(A -2(A -1(A 0(A 1 3))))))))
(A -7(A -6(A -5(A -4(A -3(A -2(A -1(A 0(A 1 2))))))))
(A -8(A -7(A -6(A -5(A -4(A -3(A -2(A -1(A 0(A 1 1)))))))))
(A -8(A -7(A -6(A -5(A -4(A -3(A -2(A -1(A 0 2)))))))))
(A -8(A -7(A -6(A -5(A -4(A -3(A -2(A -1 4))))))))```
I'd like to finish it and then see if it works as I am starting to think, however; I am not sure where to go from here. I get that the next call is
Java Code:
`(A -1 4)`
but would the A(x -1 be put on the back, like this
Java Code:
`(A -2(A -8(A -7(A -6(A -5(A -4(A -3(A -2(A -1 3))))))))`
or should it be added onto the newly being worked on portion and look like this
Java Code:
`(A -8(A -7(A -6(A -5(A -4(A -3(A -2(A -1(A -1 3)))))))))`
Also, please let me know if I am even doing it correctly.

BTW: The original call is (A 1 10)

I am starting to think I did it very incorrect and instead it should look something like this
Java Code:
```(A 1 10)
(A 0(A 1 9))
(A 0(A 0(A 1 8)))
(A 0(A 0(A 0(A 1 7))))
(A 0(A 0(A 0(A 0(A 1 6)))))```
and so on.

edit: I figured out how to trace (A 1 10), the last bit was the correct way to go, the next step is to evaluate(A 2 4), and (A 3 3). I get fairly small numbers when doing it by hand,
Java Code:
```(A 3 3) = 8
(A 2 4) = 16```
However, a quick write up of the code in java, and in scheme, returns 65535. I am unable to understand why, it also looks like it overflows the stack for stuff like (A 2 10).
Last edited by sunde887; 04-26-2011 at 12:42 PM. 2. ## Maybe this dumping program helps a bit:

Java Code:
```import java.util.Stack;

public class T {

private static void print(Stack<Integer> s) {

for (int i= 0; i < s.size()-1; i++)
System.out.print("A("+s.get(i)+",");

System.out.print(s.peek());

for (int i= 0; i < s.size()-1; i++)
System.out.print(")");

System.out.println("=");
}

public static void main(String[] args) {

Stack<Integer> s= new Stack<Integer>();

s.push(2);
s.push(10);

while (s.size() > 1) {

print(s);

int y= s.pop();
int x= s.pop();

if (x == 0)
s.push(y+1);
else if (y == 0) {
s.push(x-1);
s.push(1);
}
else {
s.push(x-1);
s.push(x);
s.push(y-1);
}
}
System.out.println(s.peek());
}
}```
kind regards,

Jos 3. ## Thanks for that jos, I'll have to run it when I get off work. Boring night on these forums today. Feel like helping me out with turning a recursive process into an iterative one? The process seems natural to do as a recursive process but I am just blocked when thinking of the iterative approach.

Java Code:
```(define(f n)
(if(< n 3)
n
(+(f(- n 1))
(f(- n 2))
(f(- n 3)))))```
is the recursive process I came up with. Thanks for the help, I amgetting the book soon, gonna have to read the first chapter quite a few times(and all the others as well)

Btw, I got and ran your game of life rpl code, the code was interesting, not sure what all of it meant however. 4. ##  Originally Posted by sunde887 Thanks for that jos, I'll have to run it when I get off work. Boring night on these forums today. Feel like helping me out with turning a recursive process into an iterative one? The process seems natural to do as a recursive process but I am just blocked when thinking of the iterative approach.

Java Code:
```(define(f n)
(if(< n 3)
n
(+(f(- n 1))
(f(- n 2))
(f(- n 3)))))```
is the recursive process I came up with. Thanks for the help, I amgetting the book soon, gonna have to read the first chapter quite a few times(and all the others as well)

Btw, I got and ran your game of life rpl code, the code was interesting, not sure what all of it meant however.
w.r.t. the example above: think about a Fibonacci series with three numbers; the first three numbers are 0, 1 and 2.

w.r.t. RPL, yep, I'm afraid I don't have to just finish the reference manual but I also have to write a tutorial ;-)

kind regards,

Jos

ps. I'll email you an RPL version of Ackermann's function including memoization. 5. ## Awesome thanks :)

I should be getting sicp within a few days, may have to bug you a bit when I get stuck on stuff.

Rpl seems pretty well done, seems like it can handle quite a lot, it's pretty impressive from my quick look without much experience. I can't wait to try and understand all the source code. 6. ##  Originally Posted by sunde887 Awesome thanks :)

I should be getting sicp within a few days, may have to bug you a bit when I get stuck on stuff.

Rpl seems pretty well done, seems like it can handle quite a lot, it's pretty impressive from my quick look without much experience. I can't wait to try and understand all the source code.
For fun, compare the speed of the RPL version (with memoization turned on as in the example I emailed you) with a properly written recursive Java version. RPL beats Java by miles here ;-)

kind regards,

Jos

ps. I understand the comparison isn't fair. 7. ## The ackerman function shown in the book looks to be a bit different then yours:

Java Code:
```(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))```
I modified the dumping program to handle everything exactly as the above. It showed me that my original hand evaluation for (A 1 10) was good, equals 1024, but I am still unsure not sure why (A 2 4) and (A 3 3) produce 65536. Anything much larger than 3 3 overflows java. Am I mis-interpreting the above function? 8. ##  Originally Posted by sunde887 The ackerman function shown in the book looks to be a bit different then yours:

Java Code:
```(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))```
I modified the dumping program to handle everything exactly as the above. It showed me that my original hand evaluation for (A 1 10) was good, equals 1024, but I am still unsure not sure why (A 2 4) and (A 3 3) produce 65536. Anything much larger than 3 3 overflows java. Am I mis-interpreting the above function?
Nope, your interpretation is correct; my Ackermann function is the 'classical' one; the version above is just as bad (big-Oh wise speaking). In Java, your version looks like this:

Java Code:
```public static long a(long x, long y) {
if (y == 0) return 0;
if (x == 0) return 2*y;
if (y == 1) return 2;
return a(x-1, a(x, y-1));
}```
(type int works just as well ...)

kind regards,

Jos 9. ## I tried playing around with it to use BigIntegers instead of ints, it still caused stack overflows as well; I think I understand this function a bit more, however; the book asks to describe what functions of
Java Code:
```A 0 n
A 1 n
A 2 n```
can be thought of as mathematical equations. For 1, it seems like it is binary; A 1 10 produces 1024.

I'd like to thank you for the suggestion to think of fibbonaci for the function i described above. I was able to solve it with
Java Code:
```(define(f n)
(define(f-iter a b c count)
(if(= count 0)
c
((+ a b c)a b(- count 1))))
(f-iter(2 1 0 n)))```
I really appreciate you helping me out with this stuff; and sending me your rpl IDE jos. I got the reference material you have sent me but I haven't gotten to read much of it yet.

I hope you won't mind if I ask for your help on some of the problems on SICP. Is a lot of the stuff in the book very heavily math based? My math skills aren't as good as I'd like, but I am willing to learn more as well. 10. ##  Originally Posted by sunde887 I tried playing around with it to use BigIntegers instead of ints, it still caused stack overflows as well; I think I understand this function a bit more, however; the book asks to describe what functions of
Java Code:
```A 0 n
A 1 n
A 2 n```
can be thought of as mathematical equations. For 1, it seems like it is binary; A 1 10 produces 1024.

I'd like to thank you for the suggestion to think of fibbonaci for the function i described above. I was able to solve it with
Java Code:
```(define(f n)
(define(f-iter a b c count)
(if(= count 0)
c
((+ a b c)a b(- count 1))))
(f-iter(2 1 0 n)))```
I really appreciate you helping me out with this stuff; and sending me your rpl IDE jos. I got the reference material you have sent me but I haven't gotten to read much of it yet.

I hope you won't mind if I ask for your help on some of the problems on SICP. Is a lot of the stuff in the book very heavily math based? My math skills aren't as good as I'd like, but I am willing to learn more as well.
You're welcome of course and I don't mind; I like that theoretical fiddling; the math is just simple discrete math (i.e. no nasty differential equations or such ;-)

About A(1, n); it equals A(0, A(1, n-1)) which is 2*A(1, n-1); So the recurrent relation is A(1, n) == 2*A(1, n-1); the sentinel value A(x, 1) == 1, so A(1, n) == 2^n. The value A(2, n) can be dissected similarly.

kind regards,

Jos 11. ## At least this book will get me ready for discrete math when I go back to university. 12. ##  Originally Posted by sunde887 At least this book will get me ready for discrete math when I go back to university.
If you want some discrete mathematics, try to find the three volume "The Art Of Computer Programming" by Donald Knuth; they are a must read: Donald Knuth proves everything in those books; very fundamental stuff.

kind regards,

Jos

ps. I think nowadays those three bibles can more easily be found in antique shops; "XXX for dummies in 21 days" seems to be more populair nowadays (which is a pity imho) #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•