Skip to content

Optimizing the Ackermann Function using Haskell – part 1

July 4, 2010

This article aims to be the first one of a series of articles concerning the optimization of the Ackermann function using Haskell. The overall goal is to solve a project Euler problem, where the goal is to find  ∑≤n ≤ 6 A(nn) and give the answer mod 148.

The problem with this function is that it grows really fast even with very low numbers. It is not a primitive recursive function, however it is a total recursive function. Here is the simplest Haskell definition of it:

module Ackermann (ackermann) where

ackermann m n | m == 0 = n+1
              | m > 0 && n == 0 = ackermann (m-1) 1
              | m > 0 && n > 0 = ackermann (m-1) (ackermann m (n-1))

This definition resembles very much its mathematical definition. If one tries to execute it with low inputs (less than m=4) it runs well, however if one tries to run this function with m=4 and n=1… well, I never waited long enough to see its output 🙂

The biggest problem is the recursion. For example, if both n and m are greater than zero, the function has a double recursion, which is very consuming both in terms of time and resources.

There are of course many possibilities for optimizing this function: using fix point, memoization (by using a state monad) or non-recursively by means of the Knuth’s up-arrow notation. In further articles I will try each one of those optimizations and see if I can compute the Ackermann function with m=6 and n=6 🙂

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: