Speeding up a script -- looking for ideas

[Jeff Epler]

On Sun, Oct 20, 2002 at 01:24:12AM -0700, Richard Bow wrote:
> I'm hoping to get some hints for significantly speeding up the below 
> script.

IMO this program is the kind of inner loop that should be written in C
(or another typed language with no overhead on arithmetic) for efficiency.

My earlier algorithm (the one that doesn't loop on 'b'):
My program on my system, no psyco:
    (13832, [(2, 24), (18, 20)])
    1
    real    0m1.645s

The same algorithm, implemented in C:
    13832 (2 24) (18 20)

    real    0m0.101s

psyco gets you closer (probably), but it still doesn't offer a factor of 16.

I'll admit that the "cubert" function makes me a bit uneasy (as its
corresponding part did in the python version) but it's a small matter of
making that function correct for all integer values...

#include <math.h>
#include <stdio.h>

#define N 2

unsigned cubert(unsigned int u) {
    return (unsigned)(pow(u, 1./3.)+.5);
}

unsigned f(unsigned low, unsigned high) {
    unsigned pairs[N][2];
    unsigned n, a, b, c, cu;

    for(c=low; c<high; c++) {
        n = 0;
        cu = cubert(c)+2;
        for(a=1; a<cu; a++) {
            b = cubert(c-a*a*a);
            if (b < a) break;
            if (a*a*a+b*b*b == c) {
                pairs[n][0] = a;
                pairs[n][1] = b;
                n++;
                if(n == N) {
                    printf("%u", c);
                    for(n=0; n<N; n++) {
                        printf(" (%u %u)", pairs[n][0], pairs[n][1]);
                    }
                    printf("\n");
                    break;
                }
            }
        }
    }
}

int main(int argc, char **argv) {
    f(10000, 20000);
    //f(1729, 1730);
}