PHP Ackermann's Implementation

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
whaatt
Posts: 30
Joined: Sun Apr 11, 2010 2:03 pm UTC

PHP Ackermann's Implementation

Postby whaatt » Sat Apr 24, 2010 1:18 am UTC

Edit: Just so you know, I am self-taught up to this point, so please forgive any silly errors :D ..This is also my first post on here.

Arggh. :? I've been trying to create an implementation of Ackermann's function in PHP (for Project Euler, if you must know), and it works for small(ish) numbers, but if I enter anything relatively high like (m,n) -> (6,6), the program doesn't work. Any ideas (code below)? Thanks!

Code: Select all

<?php
function ackermann($x,$y)
   {
   if ($x != 0)
      {
      if ($x > 0 && $y == 0)
         {
         return ackermann($x-1,1);
         }
      if ($x > 0 && $y > 0)
         {
         return ackermann($x-1,ackermann($x, $y-1));
         }
      }
      
   else
      {
      return $y + 1;
      }
   }

echo ackermann(m,n);
//m,n is replaced by the values you want to find the Ackermann value for.
?>
echo "Dang. Forgot Semicolon."

fazzone
Posts: 186
Joined: Wed Dec 10, 2008 9:38 pm UTC
Location: A boat

Re: PHP Ackermann's Implementation

Postby fazzone » Sat Apr 24, 2010 2:44 am UTC

Well, I'm pretty sure PHP's integers aren't bignums by default. Though I am also pretty sure that PHP provides a arbitrary precision library of some kind.

Basically, the integer types that you are using aren't big enough to compute something as mindbogglingly large as the result of an Ackermann function. The integer is a fixed size in bits, and when you add one to a number like 11111111111111111, you just wrap around to 000000000000000000 again. And this is likely causing problems.

What you want is a bignum / arbitrary precision library. This is a bunch of code that manipulates numbers in main memory, instead of in registers (where size is limited) The advantage of this is that you will never overflow (unless you are trying to store something larger than 2^2^16 or something). The disadvantage of using such a library is that it is a gazillion times slower than regular integers.

See this page for PHP specific stuff.

http://php.net/manual/en/language.types.integer.php

or just google "arbitrary precision PHP" or something to that effect.

Ninja-edit: If you are going to be trying to compute the Ackermann function of even bigger values, performance will start to matter. I suggest looking at a more dynamic programming-type algorithm -- i.e. store previously computed values in a table of some sort so you don't compute the same thing over and over again.
*/

User avatar
Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA

Re: PHP Ackermann's Implementation

Postby Pesto » Sat Apr 24, 2010 9:16 am UTC

What exactly do you mean by "doesn't work"? Do you get an error? Does the program just sit there and never complete? Do you get the wrong answer?

User avatar
whaatt
Posts: 30
Joined: Sun Apr 11, 2010 2:03 pm UTC

Re: PHP Ackermann's Implementation

Postby whaatt » Sat Apr 24, 2010 12:23 pm UTC

Another Edit: I need to find the sum of all the Ackermann values (m,n) where 0 <= m <= 6 and 0 <= n <= 6 and give my answer mod 14^8. If anyone sees any faster ways could you could hint to it :D.

Edit: The built-in BCmath module is probably what I need. I'll try it out and see if it works.

Thanks for the replies, by "It doesn't work", I mean that it just randomly cancels execution of the program and depending on the browser, displays "This page cannot be displayed."

I did some research on Wikipedia, and found that the size of the final result increases greatly with small changes to the input; for example A(4,2) has a result of 19729 digits long.

@Reply 1: I will try looking into your suggestions.
echo "Dang. Forgot Semicolon."

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: PHP Ackermann's Implementation

Postby Xanthir » Sat Apr 24, 2010 4:20 pm UTC

Ah, if you're going to mod the answer anyway, then you can just use modular arithmetic. Check out the ackermann function's wikipedia page, where it shows you the equivalent exponential-based expression for each value. Doing modular arithmetic and fast exponentiation together should make this *very* fast. For verification purposes, the answer to A(4,2) mod 14^8 = 804023037. That took less than a millisecond to compute using my MOD-EXPT function, which uses a combination of fast exponentiation and modular arithmetic simplification. Together, these ensure that I don't actually have to do very many multiplications, and that the numbers involved are always relatively small.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Pesto
Posts: 737
Joined: Wed Sep 05, 2007 5:33 pm UTC
Location: Berkeley, CA

Re: PHP Ackermann's Implementation

Postby Pesto » Sat Apr 24, 2010 5:24 pm UTC

whaatt wrote:Thanks for the replies, by "It doesn't work", I mean that it just randomly cancels execution of the program and depending on the browser, displays "This page cannot be displayed."

Since you're trying to display the answer in a browser, I'm guessing the browser is simply timing out. Like Xanthir said, you probably need to change your algorithm, otherwise your program will likely run for hours? Days? Years?

User avatar
whaatt
Posts: 30
Joined: Sun Apr 11, 2010 2:03 pm UTC

Re: PHP Ackermann's Implementation

Postby whaatt » Sat Apr 24, 2010 6:11 pm UTC

Pesto wrote:
whaatt wrote:Thanks for the replies, by "It doesn't work", I mean that it just randomly cancels execution of the program and depending on the browser, displays "This page cannot be displayed."

Since you're trying to display the answer in a browser, I'm guessing the browser is simply timing out. Like Xanthir said, you probably need to change your algorithm, otherwise your program will likely run for hours? Days? Years?


Yep, that sounds right. Just racking my brain now over how to make the algorithm efficient; the only thing I can think of would be to try using the bcmath extension, but that doesn't seem to rectify the problem.

Code: Select all

<?php
function ackermann($x,$y)
   {
   if (bccomp($x, 0) == 0)
      {
      return $y + 1;
      }
      
   else
      {
      if (bccomp($x,0) == 1 && bccomp($y,0) == 0)
         {
         return ackermann(bcsub($x,1),1);
         }
      if (bccomp($x,0) == 1 && bccomp($y,0) == 1)
         {
         return ackermann(bcsub($x,1),ackermann(bcadd($x,0), bcsub($y,1)));
         }
      }
   }   

echo ackermann(m,n);
//insert values for m and n.
?>


Thanks anyways.
echo "Dang. Forgot Semicolon."

Ended
Posts: 1459
Joined: Fri Apr 20, 2007 3:27 pm UTC
Location: The Tower of Flints. (Also known as: England.)

Re: PHP Ackermann's Implementation

Postby Ended » Sat Apr 24, 2010 6:36 pm UTC

As Xanthir said, you need to take advantage of modular arithmetic. Calculating A(6,6) explicitly will not work - it's simply much too big. However by using techniques like modular exponentiation, it is possible to compute A(6,6) mod some small number (in this case 14^8).

You might need to play around with expressing A(6,6) in a non-recursive form, in the same way that A(4,4) is given as a power-tower on the Wikipedia page (just thinking aloud here).
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
-dubsola

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: PHP Ackermann's Implementation

Postby Xanthir » Sat Apr 24, 2010 10:28 pm UTC

Ended wrote:As Xanthir said, you need to take advantage of modular arithmetic. Calculating A(6,6) explicitly will not work - it's simply much too big. However by using techniques like modular exponentiation, it is possible to compute A(6,6) mod some small number (in this case 14^8).

And pair the modular exponentiation with fast exponentiation. You can compute 2^100, for example, with only 10 multiplications if I'm figuring correctly, rather than 99. When you're doing ridiculously large exponents, you'll need it.

You might need to play around with expressing A(6,6) in a non-recursive form, in the same way that A(4,4) is given as a power-tower on the Wikipedia page (just thinking aloud here).

At the very least, computing any of the A(4,n) values directly as an exponential will help. Pair that with memoization so you only compute a given value once, and then later just retrieve it from an array or hash table, and you should be golden.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Turtlewing
Posts: 236
Joined: Tue Nov 03, 2009 5:22 pm UTC

Re: PHP Ackermann's Implementation

Postby Turtlewing » Mon Apr 26, 2010 1:38 pm UTC

I don't know much about the values you're trying to calculate but, I see you're recursively calling functions there. Is it possible your running into stack overflow issues?

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: PHP Ackermann's Implementation

Postby Cosmologicon » Mon Apr 26, 2010 7:34 pm UTC

Modular exponentiation is a good start, but it's not enough. For instance, Wikipedia's non-recursive formula for A(4,4) has it in terms of 2^2^2^65536. Using modular exponentiation this takes 2^65536 operations. You'll need to be more clever than that to get it done. You should be able to get A(4,4) just using Euler's Theorem, but I don't know about ones beyond that.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests