(this is what I do instead of actually getting stuff done at work)
I think it'll be cool if we can get a team effort happening, & try to get the largest value we possibly can.
I was wondering if you could point out places where I can make stuff go faster. I think I'm running out of stack space, actually, because the depth of the recursion is gigantonormous. I reason that making each stack frame a bit smaller could result in..... well, not segfaulting quite as early.
My code is very fast at the moment. The only problem is that it segfaults rather quickly as well. (valgrind says can't grow stack, not out of bounds exception or anything)
Anyway, I'm making use of a cache, that for some reason is initialised (it loses this property if I add more global variables
). It's always a good sign when you don't know why your code WORKS, rather than why it doesn't work..... 
Anyway, the cache cuts down on duplicate calls by a factor of god-knows-what. It's a very nice optimisation.
Another optimisation is that the function is made partially iterative. In truth, I stole this idea from somewhere.
Also, if you think this code is a total trainwreck then tell me - I don't mind criticism, as long as it actually helps me. I'm here to learn, & you can't learn if you have an ego :p
- Code: Select all
#include <iostream>
using namespace std;
#define y_range 3000000
#define x_range 5
long unsigned int calls = 0;
int cacheHits = 0;
long unsigned int result = 0;
long unsigned int cache[x_range][y_range];
long unsigned int it_ack(long unsigned m, long unsigned n) {
calls++;
if (m >= x_range || n >= y_range) {
cout << "Out of cache range! (" << m << ',' << n << ")\n";
exit(1);
}
if (cache[m][n]) { // this is the bit I don't understand. Why is it initialised?
cacheHits++;
return(cache[m][n]);
}
long unsigned m_tmp=m;
long unsigned n_tmp = n;
while (m != 0) {
if (n == 0) {
n = 1;
} else {
n = it_ack(m, n-1);
}
m--;
}
result = n + 1;
cache[m_tmp][n_tmp] = result;
return result;
}
long unsigned int ack(long unsigned m, long unsigned n) {
calls++;
if (m >= x_range || n >= y_range) {
cout << "Out of cache range! (" << m << ',' << n << ")\n";
exit(1);
}
if (cache[m][n]) {
cacheHits++;
return(cache[m][n]);
}
if (m == 0) {
cache[m][n] = n+1;
return n+1;
}
else if (n == 0) {
result = ack(m-1, 1);
cache[m][n] = result;
return result;
}
else {
result = ack(m,n-1);
result = ack(m-1, result);
cache[m][n] = result;
return result;
}
}
int main() {
int a,b;
cout << "Enter a and b\n";
cin >> a >> b;
cout << a << " " << b << endl;
while (42) {
cout << "Ack is: " << it_ack(a, b) << endl;
cout << calls << " calls, " << cacheHits << " cache hits.\n";
calls = 0; cacheHits = 0;
cin >> a >> b;
}
}
