Skip to content

Instantly share code, notes, and snippets.

@vbe0201
Created October 12, 2018 16:08
Show Gist options
  • Save vbe0201/6130e5b5250ed67d21cb57e07628087f to your computer and use it in GitHub Desktop.
Save vbe0201/6130e5b5250ed67d21cb57e07628087f to your computer and use it in GitHub Desktop.
An implementation of the Ackermann function in Python.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys
import time
class Ackermann:
def __init__(self):
self.count = 0
self.cache = {}
self.cache_hit = 0
self.cache_miss = 0
def a0(self, x, y):
""" Ackermann's function with naive recursion. """
self.count += 1
if x == 0:
return y + 1
elif y == 0:
return self.a0(x - 1, 1)
else:
return self.a0(x - 1, self.a0(x, y - 1))
def a1(self, x, y):
""" Ackermann's function with Memoization """
self.count += 1
if x in self.cache and y in self.cache[x]:
self.cache_hit += 1
return self.cache[x][y]
else:
self.cache_miss += 1
if x == 0:
result = y + 1
elif y == 0:
result = self.a1(x - 1, y)
else:
result = self.a1(x - 1, self.a1(x, y - 1))
self.cache[x] = {y: result}
return result
def a2(self, x, y):
""" Ackermann's function with partial recursion """
self.count += 1
if x == 0:
return y + 1
elif x == 1:
return y + 2
elif y == 0:
return self.a2(x - 1, 1)
else:
return self.a2(x - 1, self.a2(x, y - 1))
def a3(self, x, y):
""" Ackermann's function with Memoization + partial recursion """
self.count += 1
if x in self.cache and y in self.cache[x]:
self.cache_hit += 1
return self.cache[x][y]
else:
self.cache_miss += 1
if x == 0:
result = y + 1
if x == 1:
result = y + 2
elif y == 0:
result = self.a3(x - 1, 1)
else:
result = self.a3(x - 1, self.a3(x, y - 1))
self.cache[x] = {y: result}
return result
def run(self, x, y):
return self.a3(x, y)
if __name__ == '__main__':
x = int(input('Please enter the first parameter: '))
y = int(input('Please enter the second parameter: '))
sys.setrecursionlimit(5000)
ackermann = Ackermann()
time1 = time.perf_counter()
print(f'Ackermann ({x}, {y}): {ackermann.run(x, y)}')
time2 = time.perf_counter()
time_diff = time2 - time1
print(f'Execution time: {time_diff}')
print(f'Number of calls: {ackermann.count}')
if ackermann.cache != {}:
print(f'Cache hit count: {ackermann.cache_hit}')
print(f'Cache miss count: {ackermann.cache_miss}')
print(f'Cache Hit ratio: {ackermann.cache_hit / ackermann.cache_miss * 100}.2f')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment