Search for solutions to quartic diophantine equation I wrote this code to find the variables that will satisfy the diophantine equation (i.e. a^4 + b^4 + c^4 = d^4), for all variables belong to: (0 , 430000), and it takes forever to find the answer (I left the code running for two hours and got nothing). I know that this is caused by the algorithm or the approach I took, but I really couldn't think of any better solution... 

here's the code:    

#include &lt;iostream&gt;
using namespace std;
void main()
{
    //Here I use double because max value for int variables is too small for what I need.
    double n = 0, LHS, RHS, valA, valB, valC, valD;     
    double *arrA, *arrB, *arrC, *arrD;
    arrA = new double[430000]; //array to store all the powers of 4 for var A   
    arrB = new double[430000]; //array to store all the powers of 4 for var B
    arrC = new double[430000]; //array to store all the powers of 4 for var C   
    arrD = new double[430000]; //array to store all the powers of 4 for var D
    for (int count = 0; count &lt; 430000; count++)
    {
        arrA[count] = n*n*n*n;      
        arrB[count] = n*n*n*n;      
        arrC[count] = n*n*n*n;
        arrD[count] = n*n*n*n;      
        n++;    
    }    
    //this loop is a counter, it increments "b" by 1 when "a" reaches max value, and so on for each variable...
    /*
    N.B: 
    The variables that satisfy the equation should be the following:
    a = 95800
    b = 217519
    c = 414560
    d = 422481
    Plug it in as initializers for the variables to check that the program is working fine.
    */
    int a = 0, b = 0, c = 0, d = 0;
    while (d &lt; 430000)
    {       
        if (a == 430000)
        {           
            a = 0; 
            b++;        
        }       
        if (b == 430000) 
        {           
            a = 0; 
            b = 0; 
            c++;        
        }       
        if (c == 430000) 
        {           
            a = 0; 
            b = 0; 
            c = 0; 
            d++;        
        }               
        if (d == 430000) 
        {           
            break;      
        }   
        LHS = arrA[a] + arrB[b] + arrC[c];      
        RHS = arrD[d];      
        if (LHS == RHS &amp;&amp; (arrA[a] != arrB[b] != arrC[c] != arrD[d]))       
        {           
            valA = a; valB = b; valC = c; valD = d;         
            break;      
        }       
        a++;
    }

    if (d == 430000){
        cout &lt;&lt; "Couldn't find an answer! \n" }
    else 
    {
        cout &lt;&lt; "value of A is:  " &lt;&lt; valA &lt;&lt; endl;
        cout &lt;&lt; "value of B is:  " &lt;&lt; valB &lt;&lt; endl; 
        cout &lt;&lt; "value of C is:  " &lt;&lt; valC &lt;&lt; endl; 
        cout &lt;&lt; "value of D is:  " &lt;&lt; valD &lt;&lt; endl;
    }
}


If anyone could tell me how to speed up the code or could think of a better algorithm. There's nothing wrong (IMO) in the code's syntax or logic, but it is very very slow...

N.B: here's a link to an article regarding the equation for further reading: 
https://www.jstor.org/stable/2008781?seq=1#page_scan_tab_contents

I'm using a 2013 macbook pro "running windows 10", (intel i5 2.4GHz, 8GB RAM), MS Visual Studio 2017...
This looks like a bug:

if (LHS == RHS &amp;&amp; (arrA[a] != arrB[b] != arrC[c] != arrD[d])) 


The operator != returns a boolean result. Its Associativity is also left to write. so the above is equivalent to:

if (LHS == RHS &amp;&amp; (((arrA[a] != arrB[b]) != arrC[c]) != arrD[d])) 


So:

arrA[a]         != arrB[b]     =&gt;  true or false
(true or false) != arrC[c]     =&gt;  true or false  (so usually true)
true            != arrD[d]     =&gt;  true or false  (so usually true)

LHS == RHS &amp;&amp; true             =&gt;  Looking for LHS == RHS


This is a bad way of writing a nested loop:

while (d &lt; 430000)
{       
    if (a == 430000)
    {           
        a = 0; 
        b++;        
    }       
    if (b == 430000) 
    {           
        a = 0; 
        b = 0; 
        c++;        
    }       
    if (c == 430000) 
    {           
        a = 0; 
        b = 0; 
        c = 0; 
        d++;        
    }               
    if (d == 430000) 
    {           
        break;      
    }   
    LHS = arrA[a] + arrB[b] + arrC[c];      
    RHS = arrD[d];
    // stuff
}


Just write:

for(int a = 0; a &lt; 430000; ++a) {
    for(int b = 0; b &lt; 430000; ++b) {
        for(int c = 0; c &lt; 430000; ++c) {
            for(int d = 0; d &lt; 430000; ++d) {
                LHS = arrA[a] + arrB[b] + arrC[c];      
                RHS = arrD[d];
                // stuff
            }
        }
    }
}


There is no point looping over all the values.

if a^4 + b^4 + c^4 &gt; 430000^4 then there is no point in running through the d loop as you will never find the value.

There is no point in checking all values of d. If you must use a search arrD then do a binary search of the array. This will vastly reduce the number of items checked in the innermost loop. Alternatively just find the cube root of the result using a maths function.

 double root = std::pow(LHS, 1.0/4.0);
 double base = std::floor(root); 
 if (floor * floor * floor * floor == LHS) {
     break;
 }


I am not convinced that calculating and saving all the powered values is going to save time. Also  you don't need to save the same result four times. Rather than have arrA and arrB and arrC and arrD have a single array arr. It is the index into the array that is important.

Also don't manually allocate this space with new use a vector&lt;double&gt;.

The question is a memory lookup faster than or slower than doing 4 multiplications (or callling std::pow(x, 4)). That is something you will need to time and find out.