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

Nice, using redo to explicitly perform tail-end recursion optomization. I'm wondering if the optimizer can figure that out?

Hmm, but yours gives the wrong answer for A(3,3). (61 instead of 65536)

—John

Replies are listed 'Best First'.
Re (tilly) 3 (faster): Ackerman vs. Perl : KO in 3 rounds
by tilly (Archbishop) on Dec 18, 2001 at 04:29 UTC
    When Perl calls a recursive function it does a huge amount of work saving state, optimizing the next time you call it, etc. For a sobering comparison, compare the implementation above with the following one where I manage a stack explicitly instead of having a stack of function calls: 
    sub A {
  my ($x, $y) = @_;
  my @stack = ();
  while (1) {
    if (0 == $x) {
      if (@stack) {
        $y++;
        $x = pop(@stack);
      }
      else {
        return 1 + $y;
      }
    }
    else {
      if (0 == $y) {
        $x--;
        $y = 1;
      }
      else {
        push @stack, $x-1;
        $y--;
      }
    }
  }
}

    [download]
    Impressed?
[reply]
[d/l]
      Performace is the same: (3,3) => instantanious, while (4,3) => seemingly forever. (though it hasn't crashed yet, and memory usage is not growing)

      Seriously, thanks for posting that. It is a good idea for recursion in general in Perl, knowing what I just learned here.

[reply]
        If you understand the growth pattern properly, you will realize that A(4,3) is not running with the naive algorithm in your lifetime on a computer, and even if it did, Perl would be unable to represent the answer.

        Try A(3,6), A(3,7) and A(3,8) to get an idea of relative performance.

        Now if you really want a speed boost, what you want to do isn't make the recursion faster, but rather insert more and more special cases to avoid spending all of the time recursing at the tail. The following executes acceptably: 

        sub A {
  BARE_BLOCK: {
    if (0 == $_[0]) {
      return 1 + $_[1];
    }
    elsif (1 == $_[0]) {
      return 2 + $_[1];
    }
    elsif (2 == $_[0]) {
      return 3 + 2*$_[1];
    }

    @_=($_[0] - 1, $_[1] ? A($_[0], $_[1]-1) : 1);
    redo BARE_BLOCK;
  }
}

        [download]
        And here we find out why to use recursion even if Perl is bad at it. This intelligent optimization would be very hard to write if you first did the low-level optimization of avoiding any recursive calls. Intelligent algorithms beat faster execution of bad ones any time!
[reply]
[d/l]
Re (tilly) 3: Ackerman vs. Perl : KO in 3 rounds
by tilly (Archbishop) on Dec 18, 2001 at 03:42 UTC
    Sorry. Perl can't detect tail-end recursion for you. In fact Perl's handling of deep recursion is truly horrible.

    As for whether my answers are right or wrong, they agree with this page...

[reply]
      The version of the function I was using is expressed cleanly by VSarkiss in this node. It gives 65536.

      The Perl code reads exactly from the piece definition, adding a few $ symbols, a *, and semi's. It makes every condition explicit, and don't rely on narrowing constraints and order of definition. So I'm pretty sure that's a correct implementation.

      I suppose there are multiple versions of Ackerman's idea, all working in the same way, but different in detail.

      —John

[reply]
        VSarkiss was just trying to rewrite what you wrote more cleanly. But do a search for Ackermann's function and you consistently come up with the function as I wrote it.

        Incidentally as noted in this biography, what Ackermann actually came up with was a function of 3 variables. This was later simplified by Rosza Peter then Raphael Robinson into the current textbook form which I wrote.

[reply]

In Section Meditations