Ken-Soft

Software and the World

  • 日本語
  • 한국어
  • 中文
  • italian
  • Portugese
  • Espanol
  • German

Ackermann–Péter function (2 arguments) - C/C++ - Recursive Implentation

Posted under C/C++, Mathematics by Kenny on Friday 16 July 2010 at 12:06 pm

Bookmark and Share

This is an implementation of the 2 argument version of the Ackermann Function (i.e. Ackermann-Péter function). In essence, this is an example of a very simple recursive function is an example of a total computable function that is not primitive recursive. Instead of making the internet even more redundant with unnecessary text, just click the above link to view the entire Wikipedia article.
Function’s like these are very fun to play with. I often think about the human brain and how it functions when I see these kinds of functions. Taking input from the environment and processing it, sometimes recursively (like in a thought cycle), then converging to some or many outputs.
C Implentation:
noteThis function grows extremely fast, such that it quickly out grows any primitive type in C, including the largest “unsigned long long” type. Though the program will likely crash with a 0xC0000005 error from too much recursion :)
It should run fine from A(0,0) to A(4,0) and likely crash while computing A(4,1), which is 65533. A(4,0) is 13, so the number of recursive calls jumps up enormously! I will be working on a custom, larger data type as well as a way around the error caused by too much recursion.

1
2
3
4
5
6
7
8
9
10
11
12

/**
 * Ackermann function - recursive implementation
 */
unsigned long long A(unsigned long long m, unsigned long long n) {
    if(m == 0) {
        return n + 1;
    }else if(n == 0) {
        return A(m - 1, 1);
    } else {
        return A(m - 1, A(m, n - 1));
    }
}

The entire source implentation can be found here
I obtained a list of some of the expected values from this site -> http://www-users.cs.york.ac.uk/susan/cyc/a/ackermnn.htm
Here are some of the values for 0 < m < 5, 0 < n < 6

n=0 n=1 n=2 n=3 n=4 n=5
m=0 1 2 3 4 5 6
m=1 2 3 4 5 6 7
m=2 3 5 7 9 11 13
m=3 5 13 29 61 125 253
m=4 13 65533 265536-3 2265536-3 A(3,2265536-3) A(3,A(4,4))

Some of the patterns formed are very amazing. For example: A(2, n), 0 <= n < infinite, will list odd numbers starting from 3 to infinite.
To demonstrate this just insert the below loop into your code:

1
2
3

for(int n = 0; n < 100; n++) {
      std::cout << "A(2, " << n << ") = " << A(2, n) << std::endl;
}
Share on Facebook

Simulation Program (Motivated John Conway’s Game of Life) - C/C++

Posted under C/C++, Programming, Security, Simulation by Kenny on Tuesday 13 July 2010 at 8:33 pm

Bookmark and Share

In this little simulation demo I created four simple rules, of which can be activated by uncommenting them out in the source code. Though nothing too complex emerges, I still liked some the resulting behavior.
Particularly, rule1(), results in colors slowly grouping together in various forms. It may be hard to immediately noticed so watch carefully. This was motivated by John Conway’s Game of Life.
The program was written in C/C++, all graphics are done using SDL
The whole source can be found here main.cpp
Compileg++ main.cpp -lSDL
Run./a.out

Game of Life Patterns Game of Life Patterns
Game of Life Patterns Game of Life Patterns

Rule1()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

for(int x = 0; x < worldWidth; x++) {
    for(int y = 0; y < worldHeight; y++) {
        int r = world[x][y].r;
        int g = world[x][y].g;
        int b = world[x][y].b;
        /*
          o o o
          o x o
          o o o
        */
        // RULES
        if(x > 0 && y > 0) { // top left
            if(world[x - 1][y - 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x - 1][y - 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x - 1][y - 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(y > 0) { // top
            if(world[x][y - 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x][y - 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x][y - 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x < worldWidth - 1 && y > 0) { // top right
            if(world[x + 1][y - 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x + 1][y - 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x + 1][y - 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x > 0) { //  left
            if(world[x - 1][y].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x - 1][y].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x - 1][y].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x < worldWidth - 1) { // right
            if(world[x + 1][y].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x + 1][y].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x + 1][y].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x > 0 && y < worldHeight - 1) { // bottom left
            if(world[x - 1][y + 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x - 1][y + 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x - 1][y + 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(y < worldHeight - 1) { // bottom
            if(world[x][y + 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x][y + 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x][y + 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(x < worldWidth - 1 && y < worldHeight - 1) { // bottom right
            if(world[x + 1][y + 1].r > 200) {
                r+=2; g--; b--;
            }
            if(world[x + 1][y + 1].g > 200) {
                r--; g+=2; b--;
            }
            if(world[x + 1][y + 1].b > 200) {
                r--; g--; b+=2;
            }
        }
        if(r < 0) {
            r = 0;
        }
        if(g < 0) {
            g = 0;
        }
        if(b < 0) {
            b = 0;
        }
        if(r > 255) {
            r = 255;
        }
        if(g > 255) {
            g = 255;
        }
        if(b > 255) {
            b = 255;
        }
        world[x][y].r = r;
        world[x][y].g = g;
        world[x][y].b = b;
    }
}
Share on Facebook

Is Prime Number Algorithm

Posted under C/C++, Mathematics, Programming by Kenny on Monday 12 July 2010 at 11:03 am

Bookmark and Share

I was randomly surfing around the internet when I stumbled upon Google Labs Aptitude Test (GLAT)(Found here). I can’t really remember which links I followed from there but I stumbled into a question that asks to find the first 10 consecutive digits of E that are prime. While definitely not a hard task I wrote a small program in C to test whether or not a number is prime.

The core function isPrime() is below

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

long long isPrime(long double n) {
    // is n an integer ?
    if(n / (long long) n != 1.0) {
        return -1;
    }
    // is n even? (half of the numbers)
    if((long long)n % 2 == 0) {
        if(n == 2) {
               return 0;
        }
        return 2;
    }
    long long root = sqrtl(n);
    // is the number divisible by n, such that n > 2 and n <= sqrt(number)?
    // if so then the number is composite
    for(long long i = 3; i <= root; i++) {
        if((long long) n % i == 0) {
            return i;
        }
    }
    return 0; // it is prime!
}

note: I use long long just to allow the calculation of bigger numbers. Though if the number gets to large enough this algorithm can still slow down a bit, as it could potentially have to iterate from 3 to the square root of the number being tested. For most cases this algorithm executes plenty fast enough and it is definitely better than iterating over every number between 1 and N, as many sites do.
the entire implementation is here:main.cpp

Share on Facebook

Next Page »

Copyright © 2009 www.Ken-Soft.com