C++ - Ackermann function optmisation

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

Moderators: phlip, Prelates, Moderators General

C++ - Ackermann function optmisation

Postby Cynic » Fri Aug 24, 2007 5:06 pm UTC

I'm trying to optimise an implementation of the Ackermann function as much as possible, to see how much I can actually compute.

(this is what I do instead of actually getting stuff done at work)

I think it'll be cool if we can get a team effort happening, & try to get the largest value we possibly can. :)

I was wondering if you could point out places where I can make stuff go faster. I think I'm running out of stack space, actually, because the depth of the recursion is gigantonormous. I reason that making each stack frame a bit smaller could result in..... well, not segfaulting quite as early.

My code is very fast at the moment. The only problem is that it segfaults rather quickly as well. (valgrind says can't grow stack, not out of bounds exception or anything) :)


Anyway, I'm making use of a cache, that for some reason is initialised (it loses this property if I add more global variables ;)). It's always a good sign when you don't know why your code WORKS, rather than why it doesn't work..... :|
Anyway, the cache cuts down on duplicate calls by a factor of god-knows-what. It's a very nice optimisation.

Another optimisation is that the function is made partially iterative. In truth, I stole this idea from somewhere.

Also, if you think this code is a total trainwreck then tell me - I don't mind criticism, as long as it actually helps me. I'm here to learn, & you can't learn if you have an ego :p

Code: Select all
#include <iostream>


using namespace std;

#define y_range 3000000
#define x_range 5

long unsigned int calls = 0;
int cacheHits = 0;
long unsigned int result = 0;
long unsigned int cache[x_range][y_range];





long unsigned int it_ack(long unsigned m, long unsigned n) {
  calls++;

  if (m >= x_range || n >= y_range) {
    cout << "Out of cache range! (" << m << ',' << n << ")\n";
    exit(1);
  }
  if (cache[m][n]) { // this is the bit I don't understand. Why is it initialised?
    cacheHits++;
    return(cache[m][n]);
  }
  long unsigned m_tmp=m;
  long unsigned n_tmp = n;

  while (m != 0) {
    if (n == 0) {
        n = 1;
    } else {
        n = it_ack(m, n-1);
    }
    m--;
  }

  result = n + 1;
  cache[m_tmp][n_tmp] = result;
   
  return result;
}


long unsigned int ack(long unsigned m, long unsigned n) {
  calls++;

  if (m >= x_range || n >= y_range) {
    cout << "Out of cache range! (" << m << ',' << n << ")\n";
    exit(1);
  }

  if (cache[m][n]) {
    cacheHits++;
    return(cache[m][n]);
  }
  if (m == 0) {
    cache[m][n] = n+1;
    return n+1;
  }
  else if (n == 0) {
    result = ack(m-1, 1);
    cache[m][n] = result;
    return result;
  }
  else {
    result = ack(m,n-1);
    result = ack(m-1, result);
    cache[m][n] = result;
    return result;
  }
}


int main() {
  int a,b;
  cout << "Enter a and b\n";
  cin >> a >> b;
  cout << a << " " << b << endl;
  while (42) {
    cout << "Ack is: " << it_ack(a, b) << endl;
    cout << calls << " calls, " << cacheHits << " cache hits.\n";
    calls = 0; cacheHits = 0;
    cin >> a >> b;
  }
}

Cynic
 
Posts: 39
Joined: Sun Oct 08, 2006 5:08 pm UTC

Postby zenten » Fri Aug 24, 2007 5:19 pm UTC

Wouldn't it be easier to just figure out what the largest number a given computer can handle would be?
zenten
 
Posts: 3797
Joined: Fri Jun 22, 2007 7:42 am UTC
Location: Ottawa, Canada

Re: C++ - Ackermann function optmisation

Postby ToLazyToThink » Fri Aug 24, 2007 5:59 pm UTC

Cynic wrote:
Code: Select all
 if (cache[m][n]) { // this is the bit I don't understand. Why is it initialised?


Are you compiling in debug mode?
ToLazyToThink
 
Posts: 83
Joined: Thu Jun 14, 2007 1:08 am UTC

Postby demon » Fri Aug 24, 2007 6:54 pm UTC

Seriously though, using C++ default data types for something like this is a waste of time in my opinion. If you seriously want to print those huge numbers, perhaps try to write a stack-based implementation in Python? It has huge ints by default. It's quite slow though, but you're not getting too far regardless of int size - most of the Ackermann function values can't even be represented as decimal integers due to physical constraints of the universe, I've heard.

Also - if you're getting busted by stack space and not even overflowing integers, you're just not trying too hard to get a big value:)
demon
 
Posts: 170
Joined: Tue Feb 06, 2007 8:13 pm UTC

Postby Yakk » Fri Aug 24, 2007 8:08 pm UTC

*nod*, the values will end up being far larger than 2^32. You need to use big ints.

Note that
http://en.wikipedia.org/wiki/Ackermann_ ... in_C.2B.2B
contains a non-recusrive ackermann in C++ -- it also fails to use big ints, and I don't know if it works, but you can see the idea.

An advantage of having an explicit stack is that you can use out-of-memory storage (like disk space) to store the data in your stack quite easily. Another advantage is the ability to explicitly control what you store exactly.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10428
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby Cynic » Sat Aug 25, 2007 1:57 am UTC

To be honest, I didn't understand the stack-based implementation - and no, it doesn't even compile. I think perhaps it's valid code, but in some language other than C++ (C++ container types always require a declaration with the type they'll be storing, & this code doesn't provide it...). And I'm not even sure what stack.tos does.

At the moment I'm trying to break the ack(3,17) barrier. :) To do this, I don't need an implementation of arbitrary-size integers (results are not even greater than long int), but it's trivial to include such functionality - I probably just need to link against the GNU multi precision library and change everything to mpz_class :) although I recall something bad happening with arrays of mpz_class :| & it's probably because they need dynamic allocation of space, as I think they grow when you try to shove a bigger number into them. So perhaps change it to an array of pointers or something =P

Also, I'm not compiling with debugging.
Cynic
 
Posts: 39
Joined: Sun Oct 08, 2006 5:08 pm UTC

Postby Cynic » Sat Aug 25, 2007 2:03 am UTC

Oh holy shit - the stack-based thing just looks like a function stack. I see where that's going.
Cynic
 
Posts: 39
Joined: Sun Oct 08, 2006 5:08 pm UTC

Postby narg » Sat Aug 25, 2007 7:16 am UTC

Sorry to go oldschool on you, but this looks like a problem better solved by scheme (or clisp). It has compiled speed comparable to C/C++, tail recursion (stack space isn't an issue, recursion is treated like iteration), and arbitrarily large integers.
narg
 
Posts: 19
Joined: Fri Jul 27, 2007 9:20 am UTC

Postby necroforest » Sat Aug 25, 2007 11:00 pm UTC

I wrote an Ackerman function in Scheme, and it didn't go so well. Didn't try LISP though, maybe even something like Haskell would work pretty well.
ONE PART CLASS, ONE PART WHISKEY, TWO PARTS GUN! SERVE NEAT!
User avatar
necroforest
 
Posts: 195
Joined: Tue Apr 10, 2007 3:46 pm UTC

Postby demon » Sun Aug 26, 2007 12:22 am UTC

Cynic wrote:I think perhaps it's valid code, but in some language other than C++ (C++ container types always require a declaration with the type they'll be storing, & this code doesn't provide it...). And I'm not even sure what stack.tos does.


Dead wrong, you're just thinking about the STL. C++ container classes can be whatever you make them.

Adding this before the code from wiki:
Code: Select all
#include<stack>

class stack{
   public:
   int tos;
   int pop(void);
   void push(int);
   stack(){
      tos=-1;
   }
   private:
   std::stack<int> data;
};

int stack::pop(){
   int temp=data.top();
   data.pop();
   if(data.empty())tos=-1;
   return temp;
}

void stack::push(int what){
   data.push(what);
   tos=10;
}


makes it compile and run, albeit with somewhat dissapointing results.
Oh and I don't really think a class can overwrite neighbouring elements in an array... unless somebody didn't check for too large indices. In which case it's a shitty class and will break things. Check the docs - it might cast some errors to be dealt with by the programmer.
demon
 
Posts: 170
Joined: Tue Feb 06, 2007 8:13 pm UTC

Postby taggedunion » Sun Aug 26, 2007 5:26 am UTC

Cynic wrote:And I'm not even sure what stack.tos does.


Wouldn't that be "Top Of Stack"? Or were you concerned about something else?
Yo tengo un gato en mis pantelones.
User avatar
taggedunion
 
Posts: 146
Joined: Fri Jul 06, 2007 6:20 am UTC
Location: BEHIND YOU

Postby demon » Sun Aug 26, 2007 9:43 am UTC

While it indeed looks like the top of stack, it's the most butchered part of this code - this code doesn't seem to push any negative values on the stack, so unless you initialize the stack by pushing something <=-1 on it, it will segfault. I took the liberty of assuming it is a rudimentary check for the number of elements on the stack and rigged stack.tos to be positive if the stack is non-empty. Still it seems to hang up if the result should get even moderately large. Who the hell initiates int's to NULL is beyond me, though.
demon
 
Posts: 170
Joined: Tue Feb 06, 2007 8:13 pm UTC

Postby FACM » Mon Aug 27, 2007 2:50 pm UTC

On the lazy side of optimization, have you tried using the compiler's optimization flags? i think GCC uses -O, -O2, and -O3.
User avatar
FACM
 
Posts: 303
Joined: Thu Aug 09, 2007 6:40 pm UTC

Re: C++ - Ackermann function optmisation

Postby Cynic » Tue Dec 11, 2007 12:15 am UTC

I'm dicking around in C# (trying to learn the language) and have come up with a stack-based, iterative implementation, implementing a cache (much much faster, better than exponential difference). I'll post it if anyone wants..? It needs to be cleaned up tho.
Cynic
 
Posts: 39
Joined: Sun Oct 08, 2006 5:08 pm UTC

Re: C++ - Ackermann function optmisation

Postby thoughtfully » Tue Dec 11, 2007 2:43 am UTC

Cynic wrote:Also, if you think this code is a total trainwreck then tell me - I don't mind criticism, as long as it actually helps me. I'm here to learn, & you can't learn if you have an ego :p


Somehow, I manage.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery
User avatar
thoughtfully
 
Posts: 2096
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN

Re: C++ - Ackermann function optmisation

Postby Webzter » Tue Dec 11, 2007 4:24 am UTC

Cynic wrote:I'm dicking around in C# (trying to learn the language) and have come up with a stack-based, iterative implementation, implementing a cache (much much faster, better than exponential difference). I'll post it if anyone wants..? It needs to be cleaned up tho.


Please
Webzter
 
Posts: 179
Joined: Tue Dec 04, 2007 4:16 pm UTC
Location: Michigan, USA

Re: C++ - Ackermann function optmisation

Postby hotaru » Tue Dec 11, 2007 5:06 am UTC

this took me about 10 minutes to write in factor:
Code: Select all
USING: memoize ;
MEMO: ackermann ( m n -- r ) over zero? [ 1+ nip ] [ over 1 = [ 2 + nip ] [ over 2 = [ 1 shift 3 + nip ] [ over 3 = [ 3 + 1 swap shift 3 - nip ] [ dup zero? [ drop 1- 1 ackermann ] [ dupd 1- ackermann swap 1- swap ackermann ] if ] if ] if ] if ] if ;


and a quick test to see how fast it is:
Code: Select all
( scratchpad ) USING: memoize ;
Loading P" resource:extra/memoize/memoize.factor"
Compiling 980 words...
Compile finished.

:errors - print 0 compiler errors.
:warnings - print 866 compiler warnings.

Loading P" resource:extra/memoize/memoize-docs.factor"
( scratchpad ) MEMO: ackermann ( m n -- r ) over zero? [ 1+ nip ] [ over 1 = [ 2 + nip ] [ over 2 = [ 1 shift 3 + nip ] [ over 3 = [ 3 + 1 swap shift 3 - nip ] [ dup zero? [ drop 1- 1 ackermann ] [ dupd 1- ackermann swap 1- swap ackermann ] if ] if ] if ] if ] if ;
( scratchpad ) \ ackermann compile
Compiling ackermann
( scratchpad ) [ 3 1000 ackermann . ] time
85720688574901385675874003924800144844912384936442688595500031069628084089994889799455870305255668650207573833404251746014971622855385123487876620597588598431476542198593847883368596840498969135023633457224371799868655530139190140473324351568616503316569571821492337341283438653220995094697645344555005
2 ms run / 0 ms GC time
( scratchpad )


and 2 ms is how much time it takes just to print the number:
Code: Select all
( scratchpad ) 3 1000 ackermann
( scratchpad ) [ . ] time
85720688574901385675874003924800144844912384936442688595500031069628084089994889799455870305255668650207573833404251746014971622855385123487876620597588598431476542198593847883368596840498969135023633457224371799868655530139190140473324351568616503316569571821492337341283438653220995094697645344555005
2 ms run / 0 ms GC time
( scratchpad )
Code: Select all
uint8_t f(uint8_t n)
{ if (!(
n&1)) return 2;
  if (
n==169) return 13; if (n==121||n==143) return 11;
  if (
n==77||n==91) return 7; if (n==3||n==5) return 0;
  
n=(n>>4)+(n&0xF); n+=n>>4n&=0xF;
  return (
n==3||n==6||n==9||n==12||n==15)?3:(n==5||n==10)?5:0; } 
User avatar
hotaru
 
Posts: 949
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: C++ - Ackermann function optmisation

Postby Webzter » Tue Dec 11, 2007 5:43 pm UTC

Of course, the brain-dead implementation in c# is easy:

Code: Select all
public static int Ackermann(int M, int N)
{
   if (M == 0) return (N + 1);
   if (N == 0) return (Ackermann(M - 1, 1));
   return (Ackermann(M - 1, Ackermann(M, (N - 1))));
}


However, it stack overflows very quickly.... (Ackermann(5, 5) will do it) I haven't looked at it, but I assume it's the recursion overflowing the stack and not the int size.

I'm tempted to try this in F# real quick just because I ended up installing F# to get BigInt support...

Here's the C# implementation with BigInt support... note, you'll need F# installed. And, it still overflows the stack:

Code: Select all
public static BigInt Smackermann(BigInt M, BigInt N)
{
   if (BigIntModule.isZero(M)) return (BigIntModule.add(N, BigIntModule.one));
   if (BigIntModule.isZero(N)) return (Smackermann(BigIntModule.sub(M, BigIntModule.one), BigIntModule.one));
   return (Smackermann(BigIntModule.sub(M, BigIntModule.one), Smackermann(M, (BigIntModule.sub(N, BigIntModule.one)))));
}



edit: I think the problem is that the C# compiler is not taking advantage of tail recursion [1][2]. So, it's creating a new frame on the stack every call, which is quickly exhausting the stack and giving me that nice overflow exception. It should be possible to modify the IL to do it, though[3].

[1]http://blogs.msdn.com/jomo_fisher/archive/2007/09/19/adventures-in-f-tail-recursion-in-three-languages.aspx
[2]http://geekswithblogs.net/jwhitehorn/archive/2007/06/06/113060.aspx
[3]http://geekswithblogs.net/jwhitehorn/archive/2006/06/09/81257.aspx
Webzter
 
Posts: 179
Joined: Tue Dec 04, 2007 4:16 pm UTC
Location: Michigan, USA

Re: C++ - Ackermann function optmisation

Postby Yakk » Tue Dec 11, 2007 8:19 pm UTC

Webzter wrote:
Code: Select all
public static BigInt Smackermann(BigInt M, BigInt N)
{
   if (BigIntModule.isZero(M)) return (BigIntModule.add(N, BigIntModule.one));
   if (BigIntModule.isZero(N)) return (Smackermann(BigIntModule.sub(M, BigIntModule.one), BigIntModule.one));
   return (Smackermann(BigIntModule.sub(M, BigIntModule.one), Smackermann(M, (BigIntModule.sub(N, BigIntModule.one)))));
}


You cannot do tail-recursion when you are recursing more than once to produce your result.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10428
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: C++ - Ackermann function optmisation

Postby Dongorath » Tue Dec 11, 2007 8:55 pm UTC

When you look at how it expends, you got something like
A(m, n) = A(n1, A(n2, A(n3, A(..., A(np-1, np)...))))
so I implemented it iteratively with a stack reprensentig the sequence of arguments.
Plus, I used the formulas for the m=1, 2, 3.
I also tried to store already calculated values for (m, n) pairs with m>3. It eats up memory, but it is faster than redo all the recursion.
Dongorath
 
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: C++ - Ackermann function optmisation

Postby Cynic » Mon Dec 17, 2007 5:15 am UTC

hotaru wrote:this took me about 10 minutes to write in factor:
Code: Select all
USING: memoize ;
MEMO: ackermann ( m n -- r ) over zero? [ 1+ nip ] [ over 1 = [ 2 + nip ] [ over 2 = [ 1 shift 3 + nip ] [ over 3 = [ 3 + 1 swap shift 3 - nip ] [ dup zero? [ drop 1- 1 ackermann ] [ dupd 1- ackermann swap 1- swap ackermann ] if ] if ] if ] if ] if ;


and a quick test to see how fast it is:
Code: Select all
( scratchpad ) USING: memoize ;
Loading P" resource:extra/memoize/memoize.factor"
Compiling 980 words...
Compile finished.

:errors - print 0 compiler errors.
:warnings - print 866 compiler warnings.

Loading P" resource:extra/memoize/memoize-docs.factor"
( scratchpad ) MEMO: ackermann ( m n -- r ) over zero? [ 1+ nip ] [ over 1 = [ 2 + nip ] [ over 2 = [ 1 shift 3 + nip ] [ over 3 = [ 3 + 1 swap shift 3 - nip ] [ dup zero? [ drop 1- 1 ackermann ] [ dupd 1- ackermann swap 1- swap ackermann ] if ] if ] if ] if ] if ;
( scratchpad ) \ ackermann compile
Compiling ackermann
( scratchpad ) [ 3 1000 ackermann . ] time
85720688574901385675874003924800144844912384936442688595500031069628084089994889799455870305255668650207573833404251746014971622855385123487876620597588598431476542198593847883368596840498969135023633457224371799868655530139190140473324351568616503316569571821492337341283438653220995094697645344555005
2 ms run / 0 ms GC time
( scratchpad )


and 2 ms is how much time it takes just to print the number:
Code: Select all
( scratchpad ) 3 1000 ackermann
( scratchpad ) [ . ] time
85720688574901385675874003924800144844912384936442688595500031069628084089994889799455870305255668650207573833404251746014971622855385123487876620597588598431476542198593847883368596840498969135023633457224371799868655530139190140473324351568616503316569571821492337341283438653220995094697645344555005
2 ms run / 0 ms GC time
( scratchpad )



Why the shit is that so fast? That's a number of orders of magnitude faster than my solution. And mine is much, much faster than the simple recursive version.
Cynic
 
Posts: 39
Joined: Sun Oct 08, 2006 5:08 pm UTC

Re: C++ - Ackermann function optmisation

Postby Rysto » Mon Dec 17, 2007 5:18 am UTC

It's using memoization, which means that it implicitly caches the results of functions.
Rysto
 
Posts: 1443
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: C++ - Ackermann function optmisation

Postby Cynic » Mon Dec 17, 2007 5:49 am UTC

Okay. Cool - I was recently working on a functional language implementing exactly that. It was an interpreter though... and written in C++ as a group assignment... SLOW!! =P

My cache data structure in C# must be inefficient as all hell, in that case. I was using basically a Dictionary, which is a hash map. I cache every result and run out of memory at ack(3,22) or something.

That app written in Factor can do (3,100000). :/


edit: Hmm. It looks like it's using the cheaty method for ack, which has some stuff precalculated, but I'm not totally sure, as I dunno the Factor syntax too well.

if(m==2) return n+2;
if(m==3) return 2*n+3;

And of course it's much faster in this case.
Cynic
 
Posts: 39
Joined: Sun Oct 08, 2006 5:08 pm UTC

Re: C++ - Ackermann function optmisation

Postby Cynic » Mon Dec 17, 2007 11:44 pm UTC

Okay, fixed (broke?) that Factor code. And indented it, so everyone can actually read it.

It's still faster than the translucid interpreter I wrote, presumably because Factor was written by highly skilled coders, rather than me.

But C# version is king!


Code: Select all
Cheaty:
USING: memoize ;
MEMO: ackermann ( m n -- r )
   over zero?
      [ 1+ nip ] [ over 1 =
         [ 2 + nip ] [ over 2 =
            [ 1 shift 3 + nip ] [ over 3 =
               [ 3 + 1 swap shift 3 - nip ] [ dup zero?
                  [ drop 1- 1 ackermann ] [ dupd 1- ackermann swap 1- swap ackermann ]
               if ]
            if ]
         if ]
      if ]
   if ;


Legit:
USING: memoize ;
MEMO: ackermann ( m n -- r )
   over zero?
      [ 1+ nip ] [ dup zero?
            [ drop 1- 1 ackermann ] [ dupd 1- ackermann swap 1- swap ackermann ]
      if ]
   if ;



C#:
If I were going to cheat as horribly as the above Factor code, I'd just do this:
Code: Select all
long ack(long m, long n)
{
  return (long) Math.Pow(2.0,(double)n+3.0) - 3;
}


But otherwise..
(code is still messy, I don't care! PFFT! Doesn't have my name on it =P)
Code: Select all
        static Int64 numcalls = 0, cachehits = 0;
        static Dictionary<Int64, pair<Int64> > cachePos = new Dictionary<Int64, pair<Int64> >();
        static Int64 Ybounds = 22000000; // magic number
        static Int64[,] cache = new Int64[5, Ybounds];
       


        private Int64 ack(Int64 m, Int64 n)
        {

           
            Stack<Int64> stk = new Stack<Int64>();
            Int64 cacheCount;
            stk.Push(m); stk.Push(n);
            cachePos[0] = new pair<Int64>(m, n);
            while (stk.Count > 1)
            {
                cacheCount = (Int64)stk.Count;
                n = stk.Pop();
                m = stk.Pop();
               
                numcalls++;
               
                if (n < Ybounds && cache[m, n] != 0)
                {
                    stk.Push(cache[m, n]);
                    cachehits++;
                }
                else if (m == 0)
                {
                    Int64 res = n + 1;
                    stk.Push(res);
                    if (cachePos.ContainsKey(cacheCount))
                    {
                        pair<Int64> p = cachePos[cacheCount];
                        if (n < Ybounds)
                        {
                            cache[p.m, p.n] = res;
                            cache[m, n] = res;
                        }

                    }
                }
                else if (n == 0)
                {
                    stk.Push(m - 1);
                    stk.Push(1);
                    if (n < Ybounds)
                        cachePos[cacheCount] = new pair<Int64>(m, n);
                }
                else
                {
                    stk.Push(m - 1);
                    stk.Push(m);
                    stk.Push(n - 1);
                    if (n < Ybounds)
                        cachePos[cacheCount] = new pair<Int64>(m, n);
                }
            }
            cache[cachePos[0].m, cachePos[0].n] = stk.Peek();
            return stk.Peek();
        }


Code: Select all
    public class pair<T>
    {
        public T m, n;

        public pair(T a, T b)
        {
            m = a;
            n = b;
        }
    }



I noticed that Factor somehow uses multithreading. I have no idea how you'd do this with a stack-based implementation of anything, but this is probably by next step. Also, ditching C# in favour of C or Haskell or something, lol.


[edit: added generic pair class]
Cynic
 
Posts: 39
Joined: Sun Oct 08, 2006 5:08 pm UTC


Return to Coding

Who is online

Users browsing this forum: No registered users and 5 guests