Faster finding of all cubic numbers

Question

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.

Answer 1

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

Answer 2

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)

Answer 3

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++;
  }
}