Ackerman function

[sunde887]

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

(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

(A -1 4)

but would the A(x -1 be put on the back, like this

(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

(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

(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,

(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).

[JosAH]

Maybe this dumping program helps a bit:

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

[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.

(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.

[JosAH]

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.

(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.

[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.

[JosAH]

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.

[sunde887]

The ackerman function shown in the book looks to be a bit different then yours:

(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?

[JosAH]

The ackerman function shown in the book looks to be a bit different then yours:

(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:

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

[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

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

(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.

[JosAH]

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

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

(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

[sunde887]

At least this book will get me ready for discrete math when I go back to university.

[JosAH]

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)