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

[ichimunki]

I cannot duplicate this error. I get a print() on unopened filehandle error if I leave the space in between A and $ARGV. I get an Argument "Ackerman" isn't numeric in numeric eq (==) error if I take the space out.

update: I get the same error as dws if I assume that Ackerman is the script name and just pass '3 3' as my args. update 2: removed somewhat argumentative opening line.

[John M. Dlugosz]

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

[ichimunki]

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?

[John M. Dlugosz]

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;
 }

That gives the right answer for A(3,3), but blows up with reading from a bad memory location on A(4,3).