Re: [FWP] Ackerman

[csaba.raduly@sophos.com]

Abigail wrote:
> On Wed, Jun 27, 2001 at 10:47:37AM +0100, csaba.raduly@sophos.com wrote:
> > Do you think your computer has too much memory ? Give it a workout!
[snip my script using the following formula]
> > sub Acker
> > {
> >    my ( $m, $n ) = @_;
> >    if( $m==0 ){
> >       return $n+1;
> >    }
> >    if( $n==0 ){
> >       return Acker( $m-1, 0 );
                              ^
This should be 1, not 0 ------^

> >    }
> >    return Acker( $m-1, Acker($m,$n-1) );
> > }
> >
> > This script computes the Ackerman function, The Most Fiendishly
Recursive
> > Function Known To Man (tm).
>
> Eh, no, it doesn't. It starts off with:
>
>         A( 1, 0 ) = 2
>                         1,1
>         A( 1, 1 ) = 3
>                         1,2
>         A( 1, 2 ) = 4
>                         1,3
>         A( 1, 3 ) = 5
>                         1,4
>         A( 1, 4 ) = 6
>                         1,5
>         A( 1, 5 ) = 7
>                         1,6
>         A( 1, 6 ) = 8
>                         1,7
>         A( 1, 7 ) = 9
>                         1,8
>
> which are numbers that are way too low.  The rest of the numbers are
> way too low too.

At least the results above *are* correct. Purely by accident :-(

A(0,n) = n+1           =  n + 1
A(1,n) = 2 + (n+3) - 3 =  n + 2
A(2,n) = 2 * (n+3) - 3 = 2n + 3
A(3,n) = 2 **(n+3) - 3

See for example http://public.logica.com/~stepneys/cyc/a/ackermnn.htm

> Acker (3, 5) for instance is a number with almost
> 20k digits.

Nope, Acker(3,5) = 2**(5+3) - 3 = 253
Acker(3,5) = A( 2, A(3,4) ) = A( 2, 125 ) = A( 1, A(2,124) )

It's A( 4,2 ) which has 19729 digits.

>
> Your program puzzles me. You have a function 'Acker', but you never call
> it.

That's the legible implementation. Sub A is using the ?: operator,
and I needed the plain one to figure it out :-)

Unfortunately, there was a typo in the plain one :-(

> You also use Math::BigInt, but you never make objects from that class.
>

You mean "use Math::BigInt" doesn't work like "use integer" ?
Damn.

>
> Here's an implementation of the Ackermann function, as defined in [1].
> Call the program with two arguments, indicating the max arguments with
> call the Ackermann function with, and an optional first "-OPTIMIZE",
> which heavily optimizes the calculation of the values.
>
>
> [1] Edelsbrunner, Herbert: "Algorithms in Combinatorial Geometry", in
>     Brauer, W., Rozenberg, G., and Salomaa, A. (Eds.) "EATCS Monographs
>     on Theoretical Computer Science", Berlin: Springer-Verlag, 1987,
>     pp 377.
>
>
> #!/opt/perl/bin/perl -ws
>
> use strict;
> use Math::BigInt;
>
> my $two    = Math::BigInt -> new (2);
> my $three  = Math::BigInt -> new (3);
> my $four   = Math::BigInt -> new (4);
>
> use vars qw /$OPTIMIZE/;
>
> sub Ack {
>     my ($i, $j) = @_;
>
>     if ($OPTIMIZE) {
>         return $four                        if $j == 2;
>         return $two *  $j                   if $i == 1;
>         return $two ** $j                   if $i == 2;
>         return $two ** Ack ($three, $j - 1) if $i == 3 && $j >= 2;
>     }
>
>     return $two if $j == 1;
>     return Ack ($i, $j - 1) + $two if $i == 1;
>
>     Ack ($i - 1, Ack ($i, $j - 1))
> }

Are we speaking about different Ackermann functions ?
Is this what you're implementing ?

__recursion formula___           __function__
A(  0,  n) = n+1                 A(0, n) = n+1
A(m+1,  0) = A(m, 1)             A(m, 0) = A(m-1, 1)
A(m+1,n+1) = A(m, A(m+1,n))      A(m, n) = A(m-1, A(m,n-1))


Here's another try, using your "OPTIMIZE" idea,
hardwired to always:

sub Ack {
    my ($i, $j) = @_;

    return $j+1                    if $i == 0;
    return $j+2                    if $i == 1;
    return $two * $j + $three      if $i == 2;
    return $two ** ($j+3) - $three if $i == 3;

    # now $i > 3 and the fun begins
    return Ack( $i-1, 1 )          if $j == 0;
    return Ack( $i-1,
                Ack( $i, $j-1 ) );
}

>
> my $i_max = shift || 4;
> my $j_max = shift || 3;
>
> foreach my $I (1 .. $i_max) {
>     my $i = Math::BigInt -> new ($I);
>     foreach my $J (1 .. $j_max) {
>         my $j = Math::BigInt -> new ($J);
>         print "Ack ($i, $j) = ", Ack ($i, $j), "\n";
>     }
> }
>
> __END__
> $ ./ack -OPTIMIZE 5 5
> Ack (+1, +1) = +2
> Ack (+1, +2) = +4
> Ack (+1, +3) = +6
> Ack (+1, +4) = +8
> Ack (+1, +5) = +10
> Ack (+2, +1) = +2
> Ack (+2, +2) = +4
> Ack (+2, +3) = +8
> Ack (+2, +4) = +16
> Ack (+2, +5) = +32
> Ack (+3, +1) = +2
> Ack (+3, +2) = +4
> Ack (+3, +3) = +16
> Ack (+3, +4) = +65536
> Ack (+3, +5) = BIGNUM

All your results are wr^H^Hdifferent !
Replacing Ack with mine, and making the loops start at 0, this is what I
got:
(See attached file: rezult)


--
Csaba Ráduly, Software Engineer                     Sophos Anti-Virus
email: csaba.raduly@sophos.com                  http://www.sophos.com
US support: +1 888 SOPHOS 9               UK Support: +44 1235 559933

=?iso-8859-1?Q?rezult?=