Results 1 to 12 of 12
Thread: Ackerman function
 04262011, 11:29 AM #1
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,068
 Blog Entries
 3
 Rep Power
 13
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))))))))
Java Code:(A 1 4)
Java Code:(A 2(A 8(A 7(A 6(A 5(A 4(A 3(A 2(A 1 3))))))))
Java Code:(A 8(A 7(A 6(A 5(A 4(A 3(A 2(A 1(A 1 3)))))))))
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)))))
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
Last edited by sunde887; 04262011 at 01:42 PM.
 05012011, 10:39 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
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(x1); s.push(1); } else { s.push(x1); s.push(x); s.push(y1); } } System.out.println(s.peek()); } }
JosBuild a wall around Donald Trump; I'll pay for it.
 05012011, 11:08 AM #3
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,068
 Blog Entries
 3
 Rep Power
 13
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)))))
Btw, I got and ran your game of life rpl code, the code was interesting, not sure what all of it meant however.
 05012011, 11:48 AM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
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.Build a wall around Donald Trump; I'll pay for it.
 05012011, 11:58 AM #5
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,068
 Blog Entries
 3
 Rep Power
 13
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.
 05012011, 12:15 PM #6
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
Build a wall around Donald Trump; I'll pay for it.
 05012011, 09:09 PM #7
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,068
 Blog Entries
 3
 Rep Power
 13
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))))))
 05022011, 07:46 AM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
Nope, your interpretation is correct; my Ackermann function is the 'classical' one; the version above is just as bad (bigOh 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(x1, a(x, y1)); }
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
 05022011, 07:53 AM #9
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,068
 Blog Entries
 3
 Rep Power
 13
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
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(fiter a b c count) (if(= count 0) c ((+ a b c)a b( count 1)))) (fiter(2 1 0 n)))
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.
 05022011, 08:29 AM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
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, n1)) which is 2*A(1, n1); So the recurrent relation is A(1, n) == 2*A(1, n1); the sentinel value A(x, 1) == 1, so A(1, n) == 2^n. The value A(2, n) can be dissected similarly.
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
 05022011, 08:39 AM #11
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,068
 Blog Entries
 3
 Rep Power
 13
At least this book will get me ready for discrete math when I go back to university.
 05022011, 02:15 PM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
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)Build a wall around Donald Trump; I'll pay for it.
Similar Threads

Calling function in Javascript from other function
By jdigger in forum New To JavaReplies: 1Last Post: 02272011, 10:00 PM 
Possible? Callback function passed as arguments to another function
By TreyAU21 in forum Advanced JavaReplies: 3Last Post: 12042009, 04:08 PM 
function
By nanna in forum New To JavaReplies: 1Last Post: 11172008, 10:20 PM 
Need help with get function
By calicocal in forum New To JavaReplies: 10Last Post: 11092008, 08:59 PM 
function name
By osval in forum Advanced JavaReplies: 1Last Post: 08062007, 09:56 PM
Bookmarks