Demonstration of the Ackermann Function in C#

Ackermann.cs

using System;
using System.Numerics;
using System.IO;
using System.Diagnostics;
using System.Threading.Tasks.Dataflow;
using System.Threading.Tasks;
using System.Collections.Generic;
using System.Linq;
using System.Collections.Concurrent;

public struct Ackermann
{
	public readonly BigInteger m;
	public readonly BigInteger n;

	public readonly BigInteger Result;

	public readonly TimeSpan Elapsed;

	public static IEnumerable<Tuple<long, long>> Matrix()
	{
		for (long max = 0; ; max++)
		{
			for (long m = 0; m < max; m++)
			{
				yield return Tuple.Create(m, max);
			}

			for (long n = 0; n < max; n++)
			{
				yield return Tuple.Create(max, n);
			}

			yield return Tuple.Create(max, max);
		}
	}

	public Ackermann(
		BigInteger m, BigInteger n,
		Func<BigInteger, BigInteger, BigInteger> f = null)
	{
		this.m = m;
		this.n = n;
		var start = DateTime.Now;
		Result = (f ?? Optimized.Function)(m, n);
		Elapsed = DateTime.Now - start;
	}

	public Ackermann(long m, long n,
		Func<BigInteger, BigInteger, BigInteger> f = null) : this((BigInteger)m, (BigInteger)n, f) { }
	public Ackermann(Tuple<BigInteger, BigInteger> mn,
		Func<BigInteger, BigInteger, BigInteger> f = null) : this(mn.Item1, mn.Item2, f) { }
	public Ackermann(Tuple<long, long> mn,
		Func<BigInteger, BigInteger, BigInteger> f = null) : this(mn.Item1, mn.Item2, f) { }

	public static class Recursive
	{
		const string CACHE_KEY = "{0},{1}";
		public static readonly ConcurrentDictionary<string, Lazy<BigInteger>> _cache
			= new ConcurrentDictionary<string, Lazy<BigInteger>>();
			
		public static BigInteger Cached(BigInteger m, BigInteger n)
		{
			return _cache.GetOrAdd(
				String.Format(CACHE_KEY, m, n),
				key => new Lazy<BigInteger>(() =>
				{
					if (m > 0)
					{
						if (n > 0)
							return Cached(m - 1, Cached(m, n - 1));
						else if (n == 0)
							return Cached(m - 1, 1);
					}
					else if (m == 0)
					{
						if (n >= 0)
							return n + 1;
					}

					throw new System.ArgumentOutOfRangeException();
				})
			).Value;

		}
		
		public static BigInteger Function(BigInteger m, BigInteger n)
		{
			if (m > 0)
			{
				if (n > 0)
					return Function(m - 1, Function(m, n - 1));
				else if (n == 0)
					return Function(m - 1, 1);
			}
			else if (m == 0)
			{
				if (n >= 0)
					return n + 1;
			}

			throw new System.ArgumentOutOfRangeException();
		}
	}

	public static class Optimized
	{
		public class OverflowlessStack<T>
		{
			internal sealed class SinglyLinkedNode
			{
				private const int ArraySize = 2048;
				T[] _array;
				int _size;
				public SinglyLinkedNode Next;
				public SinglyLinkedNode()
				{
					_array = new T[ArraySize];
				}
				public bool IsEmpty { get { return _size == 0; } }
				public SinglyLinkedNode Push(T item)
				{
					if (_size == ArraySize - 1)
					{
						SinglyLinkedNode n = new SinglyLinkedNode();
						n.Next = this;
						n.Push(item);
						return n;
					}
					_array[_size++] = item;
					return this;
				}
				public T Pop()
				{
					return _array[--_size];
				}
			}
			private SinglyLinkedNode _head = new SinglyLinkedNode();

			public T Pop()
			{
				T ret = _head.Pop();
				if (_head.IsEmpty && _head.Next != null)
					_head = _head.Next;
				return ret;
			}

			public bool TryPop(ref T value)
			{
				if (!IsEmpty)
				{
					value = Pop();
					return true;
				}
				return false;
			}

			public void Push(T item)
			{
				_head = _head.Push(item);
			}
			public bool IsEmpty
			{
				get { return _head.Next == null && _head.IsEmpty; }
			}
		}

		static BigInteger FunctionInternal(BigInteger m, BigInteger n)
		{
			var stack = new OverflowlessStack<BigInteger>();

			do
			{
				if (!FunctionStackless(ref m, ref n))
				{
					stack.Push(m - 1);
					--n;
					continue;
				}

				if (!stack.TryPop(ref m))
					break;
			}
			while (true);

			return n;
		}

		/// returns true a no stack was used.
		static bool FunctionStackless(ref BigInteger m, ref BigInteger n)
		{
			do
			{
				if (m == 0)
					n = n + 1;
				else if (m == 1)
					n = n + 2;
				else if (m == 2)
					n = n * 2 + 3;
				else if (n == 0)
				{
					--m;
					n = 1;
					continue;
				}
				else
					return false;

				break;
			}
			while (true);

			return true;
		}

		public static BigInteger Function(BigInteger m, BigInteger n)
		{

			if (!FunctionStackless(ref m, ref n))
			{
				// Stack needed...
				return FunctionInternal(m, n);
			}

			return n;
		}
	}

	static long RequestValue(string name, string[] args, int index)
	{
		long result;
		if (args?.Length > index
			&& long.TryParse(args[index], out result))
			return result;

		Console.Write("{0} = ", name);
		while (!long.TryParse(Console.ReadLine(), out result))
			Console.WriteLine("Please enter a number.");
		return result;
	}


	static void Main(string[] args)
	{
		var processor = new TransformBlock<Tuple<long, long>, Ackermann>(
			p => new Ackermann(p),
			new ExecutionDataflowBlockOptions()
			{
				BoundedCapacity = 16,
				MaxDegreeOfParallelism = 8,
			});

		var output = new ActionBlock<Ackermann>(
			a =>
			{
				Console.WriteLine(
					"Ackermann({0}, {1}) = {2} ({3})",
					a.m, a.n, a.Result, a.Elapsed);
			});

		processor.LinkTo(output);
		processor.Completion
			.ContinueWith(t => output.Complete());

		if (args.Length != 0)
		{
			processor.Post(
				Tuple.Create(
					RequestValue("m", args, 0),
					RequestValue("n", args, 1)
				)
			);
			processor.Complete();
			output.Completion.Wait();
		}
		else
		{
			var worker = Task.Run(
			() =>
			{
				foreach (var p in Matrix())
					processor.Post(p);
			});

			Console.ReadLine();
		}

	}

}