How finish the c file computing faster

Question

When I run the program with x = 999 then it finishes under 22s. But I need to go more than 9999999. When put x = 9999 then it takes a long time. I opened my laptop for 7 hours. So, can make it faster?

I tried with python and also javascript. those took longer than c.

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

int main() {
    signed long int x = 999;
    signed long int target = 43;

    signed long int a = ((-1) * x);
    signed long int b = ((-1) * x);
    signed long int c = ((-1) * x);
    signed long int cheack = ((a * a * a) + (b * b * b) + (c * c * c));

    signed long int sum_Max = pow(((x * 2) + 1), 3);
    printf("Max SUM: %ld\n", sum_Max);

    while (cheack != target) {
        signed long int cheack = ((a * a * a) + (b * b * b) + (c * c * c));
        if (cheack == target) {
            printf("Available: \n");
            printf("    a = %ld \n", a);
            printf("    b = %ld \n", b);
            printf("    c = %ld \n", c);
            printf("    target = %ld ", target);
            break;
        } else if (a == x) {
            if (b == x) {
                if (c == x) {
                    printf("Not available... Try in bigger numbers");
                    break;
                } else {
                    a = ((-1) * x);
                    b = ((-1) * x);
                    c++;
                }
            } else {
                a = ((-1) * x);
                b++;
            }
        } else {
            a++;
        }
    }
    return 0;
}

I need to complete this project please try to fix the problem.

This is not a language problem, what you have ran into is an runtime efficiency problem. Without knowing what this program is meant to do though there is not much help that can be given. — Sean Powell, Jul 12 '21 at 09:09
You can see that the programme will provide me three number which will be support cheack = ((a*a*a)+(b*b*b)+(c*c*c)); the equation. Like if i give a number target = 43 it will provide me a three number a = 3 , b = 2, c = 2, which support the equation. so i need a number for 33 but it's not available under 999. But it's take a long time to calculate. I need to make it faster to i can find any number values instant — Arman Hossen, Jul 12 '21 at 09:10
@ArmanHossen don't put question details in a comment but instead [edit] your question and put all clarifications _there_ — Jabberwocky, Jul 12 '21 at 09:11
How large is `signed long int` on your machine? Can it hold `x*x*x` for large numbers? 32 bits will not be sufficient. — Gerhardh, Jul 12 '21 at 09:49
The outer loop `while (cheack != target)` does not make any sense. The variables are never modified inside the loop. — Gerhardh, Jul 12 '21 at 09:55
Looks like a solution for 33 with a bound of 99,999 does not exist. — Eric Postpischil, Jul 12 '21 at 11:16
A solution is mentioned [in this question](https://stackoverflow.com/questions/55463078/verify-sum-of-three-cubes-equal-to-33-fails-in-r-works-in-python): 8866128975287528, -8778405442862239, and -2736111468807040. — Eric Postpischil, Jul 12 '21 at 11:26
There is some analysis in [this answer](https://stackoverflow.com/a/35443765/298225) for a question on solving for sums of two cubes that might be useful. However, this requires more advanced techniques than are evident in the code in this question. — Eric Postpischil, Jul 12 '21 at 11:33

Gerhardh · Answer 1 · 2021-07-12T12:20:25.870

This is not a full solution but should enable you to speed up significantly.

Your code is basically a variation of the following code with some obfuscation added. ;)

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

int main() {
    signed long int x = 999;
    signed long int target = 43;

    signed long int a = ((-1)*x);
    signed long int b = ((-1)*x);
    signed long int c = ((-1)*x);
    signed long int cheack = ((a*a*a)+(b*b*b)+(c*c*c));

    signed long int sum_Max = pow(((x*2)+1),3);
    printf("Max SUM: %ld\n", sum_Max);

    for (c = -x; b <= x; c++)
    {
        for (b = -x; b < x; b++)
        {
            for (a = -x; a < x; a++)
            {
                cheack = ((a*a*a)+(b*b*b)+(c*c*c));
                if (cheack == target) {
                    printf("Available: \n");
                    printf("    a = %ld \n",a);
                    printf("    b = %ld \n",b);
                    printf("    c = %ld \n",c);
                    printf("    target = %ld ",target);
                    break;
                } 
            }
        }
    }
    if (cheack != target)
    {
        printf("Not available... Try in bigger numbers");
    }
    return 0;
}

This has a runtime complexity of O(n^3), i.e. increasing x by a factor of 10 will cause runtime to increase by factor of 1000. Hence 22s => 22,000s == ~6:05h

Assuming that the whole purpose of the program is to find a solution where target is the sum of 3 numbers taken to 3rd power you can rewrite your formula:

target == (a*a*a)+(b*b*b)+(c*c*c)

to

a*a*a == target - (b*b*b) - (c*c*c)

where a is the cubic root of target - (b*b*b) - (c*c*c)

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

int main()
{
    signed long int x = 999;
    signed long int target = 43;

    signed long int a = ((-1)*x);
    signed long int b = ((-1)*x);
    signed long int c = ((-1)*x);

    signed long int sum_Max = pow(((x*2)+1),3);
    printf("Max SUM: %ld\n", sum_Max);
    int found = 0;

    for (c = -x; c <= x; c++)
    {
        for (b = -x; b <= x; b++)
        {
            signed long int remaining = target - ((b*b*b)+(c*c*c));

            signed long int a_root = round(cbrt(remaining));
            if (a_root*a_root*a_root == remaining)
            {
                a = a_root;
                found = 1;
            }

            if (found)
            {
                printf("Available: \n");
                printf("    a = %ld \n",a);
                printf("    b = %ld \n",b);
                printf("    c = %ld \n",c);
                printf("    target = %ld ",target);
                break;
            } 
        }
    }
    if (!found)
    {
        printf("Not available... Try in bigger numbers");
    }
    return 0;
}

This solution reduces the complexity to O(n^2). The whole inner loop is basically replaced by a single call to round(cbrt()).

This is not tested. You might need to handle some rounding issues in the math functions.

There is no need to separate the sign and use `pow(…, 1./3)`. Just use the standard `cbrt` function. Also apply `round` to the result to allow for inaccuracies in the library functions, rather than `floor`. (E.g., a poor library routine might return 2.9999…5 instead of 3 for an input of 27.) — Eric Postpischil, Jul 12 '21 at 11:05
To match the original, the new program should exit the program or all the loops when a solution is found. — Eric Postpischil, Jul 12 '21 at 11:06
I presume `for (c = -x; b <= x; c++)` is a typo, not some attempt to exploit symmetry to reduce the loops. — Eric Postpischil, Jul 12 '21 at 11:28
@EricPostpischil Thanks for the changes. Initially I wanted to test with `floor()` and `floor+1`, hence the floor. I barely ever use math functions. Didn't even know there is a `cbrt` function. ;) — Gerhardh, Jul 12 '21 at 11:39

chqrlie · Answer 2 · 2021-07-12T13:35:20.383

As documented by Gerhardh, you can reduce the complexity of your algorithm from O(x³) to O(x²).

After much simplifying, the modified version below finds all 30 matches for x = 9999 in about 5 seconds on my slow Macbook:

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

int main() {
    long x = 9999;
    long target = 43;
    long a, b, c;
    long found = 0;
    // this is actually the total number of triplets
    long sum_Max = ((x * 2) + 1) * ((x * 2) + 1) * ((x * 2) + 1);
    printf("Max SUM: %ld\n", sum_Max);

    for (c = -x; c <= x; c++) {
        long c3 = c * c * c;
        for (b = -x; b <= x; b++) {
            long b3 = b * b * b;
            a = (long)+round(cbrt(target - c3 - b3));
            if ((a * a * a) + b3 + c3 == target) {
                printf("Available:\n"
                       "    a = %ld\n    b = %ld\n    c = %ld\n"
                       "    target = %ld\n",
                       a, b, c, target);
                found++;
                // if you just want the first solution, uncomment this
                //return 0;
            }
        }
    }
    if (found) {
        printf("Found %ld solutions\n", found);
    } else {
        printf("Not available... Try in bigger numbers\n");
    }
    return 0;
}

Note that this improved code is still a brute force approach. A simple improvement would run the second loop only from for (b = -c; b <= c; b++) and handle permutations when printing the matches.

The complexity tells us that x = 99999 should take about 9 minutes and x = 999999 more than half a day, but since 999999³ is greater than LONG_MAX / 2 on most architectures, the above code would invoke undefined behavior for large values of c and b and may produce incorrect results for crbt() if the magnitude of the argument is greater than 2⁵³. Another approach seems required for values of x greater than 100000.

As long as `target` is greater than zero, `c` can start at one, since one of the numbers must be positive, and symmetry implies we will find a solution with a positive `c`. And `b` can be limited to `b <= c`. — Eric Postpischil, Jul 12 '21 at 14:12

How finish the c file computing faster

2 Answers2