Faster finding of all cubic numbers

I want to improve the performance of this program.

count = 0
store = []
n = 9238899039
for i in range(1,n):
if i*i*i <= n:
count += 1
store.append(i)
print count


At the moment it is very slow. I need to find all cubic numbers up to n.

• Uhmm wait, store.append(i) did you actually mean to store store.append(i*i*i) ? – πάντα ῥεῖ Dec 27 '15 at 3:25

The for loop keeps running for a whole lot of numbers (values of i), that will always have a bigger cubic result than n. This gives you a significant performance hit.

You can simply add a break statement as soon the condition if i*i*i <= n: is no longer fulfilled.

This will prevent to process any further values of i, which will also certainly not fulfill the condition.

for i in range(1,n):
if i*i*i <= n:
count += 1
store.append(i)
else:
break

• You could also find the cube root of n and make the loop go up to that, instead of to n itself. – Blckknght Dec 27 '15 at 1:54
• @Blckknght Sure, but that won't make much difference besides the extra effort (performance cost) of calculating the cubic root of n. Using the break the last i processed actually is the cubic root of n, thus my solution is even a few ticks faster performance wise. – πάντα ῥεῖ Dec 27 '15 at 2:04
• @Blckknght Also note that the cubic root of n (2,098.328151) isn't a plain integer value. – πάντα ῥεῖ Dec 27 '15 at 2:14

There's no reason to use brute force like that. I couldn't even get the program to complete without crashing.

To find the count, just take the cube root of n, and round down. Then, it's a simple matter to construct the list you need.

n = 9238899039
count = int(n ** (1.0/3))
store = range(1, count + 1)


A classic performance improvement in calculating a series of numbers is to take advantage of previous work.

If the cube of X is Y, then the cube of X+1 is Y + 3*X*(X+1) + 1.

With such a simple function of Y=X*X*X, I doubt it will be faster than List numbers 1 to cuberoot(n), but the idea is useful in a general sense.

Below is a C code that hopefully expresses the idea clear enough for a python user.

void cubes(unsigned long limit) {
unsigned i = 1;
unsigned long cube = 1;
while (cube <= limit) {
printf("%u %lu\n", i, cube);
cube += 3L*i*(i + 1) + 1;
i++;
}
}

int main(void) {
cubes(9238899039);
return 0;
}


Output

1 1
2 8
3 27
...
2096 9208180736
2097 9221366673
2098 9234565192


Another math solution takes advantage of differences of differences. No multiplication needed.

void cubes(unsigned long limit) {
unsigned i = 1;
unsigned d1 = 0;
unsigned long d2 = 1;
unsigned long cube = 1;
while (cube <= limit) {
printf("%u %lu\n", i, cube);
d1 += 6;
d2 += d1;
cube += d2;
i++;
}
}