5
\$\begingroup\$

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.

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

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
\$\endgroup\$
  • \$\begingroup\$ You could also find the cube root of n and make the loop go up to that, instead of to n itself. \$\endgroup\$ – Blckknght Dec 27 '15 at 1:54
  • \$\begingroup\$ @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. \$\endgroup\$ – πάντα ῥεῖ Dec 27 '15 at 2:04
  • \$\begingroup\$ @Blckknght Also note that the cubic root of n (2,098.328151) isn't a plain integer value. \$\endgroup\$ – πάντα ῥεῖ Dec 27 '15 at 2:14
6
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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++;
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.