Download code

Jump to: navigation, search

Back to Ackermann_function_(Python)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

ackermann.py

 1 # The authors of this work have released all rights to it and placed it
 2 # in the public domain under the Creative Commons CC0 1.0 waiver
 3 # (http://creativecommons.org/publicdomain/zero/1.0/).
 4 # 
 5 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 # 
13 # Retrieved from: http://en.literateprograms.org/Ackermann_function_(Python)?oldid=16428
14 
15 import sys # for argv
16 
17 calls = 0
18 
19 def naive_ackermann(m, n):
20     global calls
21     calls += 1
22     if m == 0:
23         return n + 1
24     elif n == 0:
25         return naive_ackermann(m - 1, 1)
26     else:
27         return naive_ackermann(m - 1, naive_ackermann(m, n - 1))
28 
29 def iterative_ackermann(m, n):
30     global calls
31     calls += 1
32     while m != 0:
33         if n == 0:
34             n = 1
35         else:
36             n = iterative_ackermann(m, n - 1)
37         m -= 1
38     return n + 1
39 def formula_ackermann(m, n):
40     global calls
41     calls += 1
42     while m >= 4:
43         if n == 0:
44             n = 1
45         else:
46             n = formula_ackermann(m, n - 1)
47         m -= 1
48     if m == 3:
49         return (1 << n + 3) - 3
50     elif m == 2:
51         return (n << 1) + 3
52     elif m == 1:
53         return n + 2
54     else: # m == 0
55         return n + 1
56 
57 if __name__ == "__main__":
58     m = long(sys.argv[1])
59     n = long(sys.argv[2])
60 
61     calls = 0
62     result = naive_ackermann(m, n)
63     print "Naive:     %d (%d calls)" % (result, calls)
64 
65     calls = 0
66     result = iterative_ackermann(m, n)
67     print "Iterative: %d (%d calls)" % (result, calls)
68 
69     calls = 0
70     result = formula_ackermann(m, n)
71     print "Formula:   %d (%d calls)" % (result, calls)


hijacker
hijacker
hijacker
hijacker