in reply to (ichimunki) Re: Ackerman vs. Perl : KO in 3 rounds
in thread Ackerman vs. Perl : KO in 3 rounds

It's a meditation because I don't need an answer to a specific problem to accomplish some task. Rather, I just thought it was interesting and enlightening.

The idea was that Perl is different than pure-compiled languages like C, and (1) should not have the same limit to stack size since the Perl stack != the asm stack, and (2) I can use the old & construct to not push arguments in the recursive calls. I had also planned to try it with memoize, to look at the speed/memory difference.

But it goes boom. I think it's a bug if the perl executable hits a stray pointer, instead of giving a proper "out of memory" message.

—John

  • Comment on Re: (ichimunki) Re: Ackerman vs. Perl : KO in 3 rounds

Replies are listed 'Best First'.
(ichimunki) Re x 4: Ackerman vs. Perl : KO in 3 rounds
by ichimunki (Priest) on Dec 18, 2001 at 03:18 UTC
    But this routine sets up an infinite loop as far as I can tell. When I added a quick print "$_[0],$_[1]" to the beginning of the sub, the output led me to believe the problem here is the algorithm itself, not the technique used to save stack space. Am I missing something?
[reply]
[d/l]
      Could be. I think the first recursive call messes up the left argument, since the stack trick basically makes them "static" variables. So that technique doesn't work for multiple recursive calls...owell. That's just one of the sinister things about this function. For the same reason, it won't "tail-end" optomize out the recursion. 
      sub A
 {
 return 0  if $_[1] == 0; 
 return 2*$_[1]  if $_[0] == 0;
 return 2  if $_[1] == 1;
 my $mm= $_[0]-1;
 --$_[1];
 $_[1]= &A;
 $_[0]= $mm;
 return &A;
 }

      [download]
      That gives the right answer for A(3,3), but blows up with reading from a bad memory location on A(4,3).
[reply]
[d/l]

In Section Meditations