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 01: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
•