Anonymous user
Ackermann function: Difference between revisions
→{{header|C}}
(Added Hare) |
|||
Line 1,906:
Whee. Well, with some extra work, we calculated <i>one more</i> n value, big deal, right?
But see, <code>A(4, 2) = A(3, A(4, 1)) = A(3, 65533) = A(2, A(3, 65532)) = ...</code> you can see how fast it blows up. In fact, no amount of caching will help you calculate large m values; on the machine I use A(4, 2) segfaults because the recursions run out of stack space--not a whole lot I can do about it. At least it runs out of stack space <i>quickly</i>, unlike the first solution...
A couple of alternative approaches...
<lang C>/***********************\
** Thejaka Maldeniya **
\***********************/
#include <conio.h>
unsigned long long HR(unsigned int n, unsigned int a, unsigned int b) {
// (Internal) Recursive Hyperfunction: Perform a Hyperoperation...
unsigned long long r = 1;
while(b--)
switch(n) {
case 3:
// Exponentiation
r *= a;
break;
default:
r = HR(n - 1, a, r);
}
return r;
}
unsigned long long H(unsigned int n, unsigned int a, unsigned int b) {
// Hyperfunction (Recursive-Iterative-O(1) Hybrid): Perform a Hyperoperation...
switch(n) {
case 0:
// Increment
return ++b;
case 1:
// Addition
return a + b;
case 2:
// Multiplication
return a * b;
}
return HR(n, a, b);
}
unsigned long long APH(unsigned int m, unsigned int n) {
// Ackermann-Peter Function (Recursive-Iterative-O(1) Hybrid)
return H(m, 2, n + 3) - 3;
}
unsigned long long * p = 0;
unsigned long long APRR(unsigned int m, unsigned int n) {
if (!m) return n + 1;
unsigned long long r = p ? p[m] : APRR(m - 1, 1);
while(n--)
r = APRR(m - 1, r);
return r;
}
unsigned long long APRA(unsigned int m, unsigned int n) {
if (!m) return n + 1;
if (!n) {
if(p) return p[m];
return APRA(m - 1, 1);
}
return APRR(m, n);
}
unsigned long long APR(unsigned int m, unsigned int n) {
unsigned long long r = 0;
// Allocate
p = (unsigned long long *) malloc(sizeof(unsigned long long) * (m + 1));
// Initialize
for(; r <= m; ++r)
p[r] = r ? APRA(r - 1, 1) : APRA(r, 0);
// Calculate
r = APRA(m, n);
// Free
free(p);
return r;
}
unsigned long long AP(unsigned int m, unsigned int n) {
return APH(m, n);
return APR(m, n);
}
int main(int n, char ** a) {
unsigned int M, N;
if (n != 3) {
printf("Usage: %s <m> <n>\n", *a);
return 1;
}
printf("AckermannPeter(%u, %u) = %llu\n", M = atoi(a[1]), N = atoi(a[2]), AP(M, N));
//printf("\nPress any key...");
//getch();
return 0;
}</lang>
A few further tweaks may be possible.
=={{header|C sharp|C#}}==
| |||