Results 1 to 12 of 12
  1. #1
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,727
    Blog Entries
    7
    Rep Power
    21

    Default

    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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,727
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by sunde887 View Post
    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.
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,727
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by sunde887 View Post
    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.
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,727
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by sunde887 View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,727
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by sunde887 View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

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

  12. #12
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,727
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by sunde887 View Post
    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)
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Calling function in Javascript- from other function
    By jdigger in forum New To Java
    Replies: 1
    Last Post: 02-27-2011, 10:00 PM
  2. Replies: 3
    Last Post: 12-04-2009, 04:08 PM
  3. function
    By nanna in forum New To Java
    Replies: 1
    Last Post: 11-17-2008, 10:20 PM
  4. Need help with get function
    By calicocal in forum New To Java
    Replies: 10
    Last Post: 11-09-2008, 08:59 PM
  5. function name
    By osval in forum Advanced Java
    Replies: 1
    Last Post: 08-06-2007, 09:56 PM

Posting Permissions

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