How to optimize for loop?

Question

I have a problem, let's say: Find all two pairs of numbers (x, y) and (z, t) such that x³ + y³ = z³ + t³ , where (x, y)! = (Z, t) and x³ + y³ <10000 .

Taking the cubic root of 10,000 yeilds 21.544 → rounded to 21, I got:

#include <iostream>

using namespace std;

int main() {
    for( int x = 1; x <= 20; ++x ) {
        for( int y = x + 1; y <= 21; ++y ) {
            for( int z = x + 1; z <= y - 1; ++z ) {
                for( int t = z; t <= y - 1; ++t ) {
                    if( x*x*x + y*y*y == z*z*z + t*t*t ) {
                        cout << x << ", " << y << ", " << z << ", " << t << endl; 
                    }
                }
            } 
        }
    }
    return 0;
}

I know that this code could be optimized more, and this is what I am looking for. In addition, one of my friends told me that y may be x + 2 instead of x + 1, and I doubt it, because if x = 1, then we will never have y = 2, which in this case missed one possible solution.

Any thought?

Answer 1

Typical compromise: memory for speed.

x : , (x,y) x <= y,

    x^3 + y^3 < N and x^3 < y^3 (for positive numbers)
=>  x^3 + x^3 < N (by transitivity)
<=> x^3 < N/2
<=> x <= floor((N/2)^(1/3))

, x <= 17 .

x^3 + y^3 (sum → ). , (x,x) ?

int main(int argc, char* argv[])
{
  typedef std::pair<unsigned short, unsigned short> Pair;
  typedef std::vector<Pair> PairsList;
  typedef std::unordered_map<unsigned short, PairsList> SumMap;

  // Note: arbitrary limitation, N cannot exceed 2^16 on most architectures
  // because of the choice of using an `unsigned short`
  unsigned short N = 10000;
  if (argc > 1) { N = boost::lexical_cast<unsigned short>(argv[1]);  }

  SumMap sumMap;

  for (unsigned short x = 1; x*x*x <= N/2; ++x)
  {
    for (unsigned short y = x; x*x*x + y*y*y <= N; ++y)
    {
      sumMap[x*x*x + y*y*y].push_back(Pair(x,y));
    }
  }

  for (SumMap::const_reference ref: sumMap)
  {
    if (ref.second.size() > 1)
    {
      std::cout << "Sum: " << ref.first
                << " can be achieved with " << ref.second << "\n";
      // I'll let you overload the print operator for a vector of pairs
    }
  }

  return 0;
}

O (N ^ 2).

Answer 2

, , , , 10 000. y, 10 000 x. , .

, , 4 . 2 x ^ 3 + y ^ 3 . ( , , .) API, :

multimap<int, std::pair<int, int> > map;
for (int i = 1; i < 21; i++) {
    (for int j = x; j < cube_root(10000 - i^3); j++ {
        multimap.insert (i^3 + j^3, std::pair<int, int>(i,j);

.

Answer 3

. . .

Answer 4

, .

, , .

Answer 5

(EDIT: for):

int x3, y3, z3;
for( int x = 1; x <= 20; ++x ) {
    x3 = x * x * x;
    for( int y = x + 1; y <= 21; ++y ) {
        y3 = y * y * y;
        for( int z = x + 1; z <= y - 1; ++z ) {
            z3 = z * z * z;
            for( int t = z; t <= y - 1; ++t ) {
                if( x3 + y3 == z3 + t*t*t ) {
                    cout << x << ", " << y << ", " << z << ", " << t << endl; 
                }
            }
        } 
    }
}

, ( , )? 20 ... , , .

Answer 6

:

• , , int xcubed = x*x*x; x ( y z). . , .
• , hash_table, ( -).
• , , .

1729 . 1 , 12 , 9 + 10 .

To test performance, you can of course choose a much larger maxsum value (and also run it several times).

The algorithm is strictly O (N ^ 2/3). (2/3, because you only go to the cube root of N, and then this is O (m ^ 2) in this smaller range).