Optimum algorithm to calculate pythagorean triplet

Question

I have a question for everyone. I have this problem statement where in given, x^2 + y^2 = c is the equation, you have to optimally find the tuples (x,y) such that the equation holds true.

Given a variable c, whose value is known, you have to find the values (x,y). So suppose if you have c=0, then x=0 and y=0. Suppose you have c=2, then (x,y) are (-1,1) (1,-1), (-1,-1), (1,1). Now we have to find such values.

You just have to count the amount of such tuples for a given value of c.

Now I wrote the application as such:

int getCount(int c) {

  int count=0,temp=-1000;

  for(int i=-n;i<n-1;i++) {

    for(int j=-n,j<n;j++) {

      temp= i^2+j^2;

      if(temp==c) {
        count++;
        System.out.println(i+" "+j);
      }
    }
  }
}

Is there any optimum way to do this?

Please let me know.Tanks!

Answer 1

You could start with

if ( (c % 4) == 3)
    return 0;

Every square is 0 or 1 (mod 4), so the sum can never be 3.

If c is 0, 1, 2 (mod 4), let your candidate x run from 0 to sqrt(c), calculate y and see if it's an integer. Find 3 other solutions by reversing signs.

Answer 2

Create a map or

{0 => 0, 1 => 1, 4 => 2, 9 => 3, 16 => 4, ..., i² => i}

a vector of squares

[0, 1, 4, 9, 16, ..., i²]

so that (i+1)² > c. then find all pairs of values from the container sum of which give c.

Answer 3

If you example you can see that once you have the solution (1,1) all three others are easy to find, you just have to change the signs or the order of (x,y) (ie x <--> y).

Now, you know that x^2 + y^2 = c which means that x <= sqrt(c) and y <= sqrt(c). If you suppose that x <= y then you have x <= sqrt(c/2) and sqrt(c/2) <= y <= sqrt(c).

Indeed :

• x^2+x^2 <= x^2 + y^2 = c so x <= sqrt(c/2)
• x <= y and y^2 <= x^2 + y^2 = c so sqrt(c/2) <= y <= sqrt(c)

Now, you can easily see that |sqrt(c)-sqrt(c/2)| < |sqrt(c/2)| for every c so you just have to enumerate all y between sqrt(c/2) and sqrt(c), compute the x round it and see if x^2+y^2=c.

int print(x,y) {
  System.out.println(x+" "+y);
  System.out.println(-x+" "+y);
  System.out.println(-x+" "+-y);
  System.out.println(x+" "+y);
}

int getCount(int c) {
  if ( (c % 4) == 3)
    return 0;

  int count=0;
  for(int y = Math.sqrt(c/2) ; y <= Math.sqrt() ; y++) {
      int x = (int)Math.sqrt(c-y*y);
      if(x*x + y*y == c){
        count += 4;
        print(x,y);
        if(x != y) {
          count += 4;
          print(y,x);  
        }

      }
  }
}

On an example, if c = 1000*1000 then your solution would have test 4n^2 couple (x,y) ie if n = sqrt(c), 4*1000*1000 couples.

Testing every x up to sqrt(c) would have cost 1000 tests and my solution in only doing ~300 tests.

Answer 4

For the Pythagorean triple c^2 = a^2 + b^2, Euclid's formula gives us the following relations, with m and n an arbitrary pair of positive integers with m > n:

• a = m^2 - n^2
• b = 2 * m * n
• c = m^2 + n^2

Here we are interested in finding m and n with c.

The relationships implies the following:

c = m^2 + n^2
=> m^2 = c - n^2
=> a = m^2 - n^2 = c - 2.n^2
=> n^2 = (c - a) / 2

On the other hand:

a^2 + b^2 = c^2
=> b^2 = c^2 - a^2
=> (4.m^2.m^2) = c^2 - a^2
=> m^2 = c^2 - a^2 / 4.n^2
=> m^2 = (c - a)(c + a).2 / 4.(c - a)
=> m^2 = (c + a) / 2

m and n are integers (not complexes), hence 0 <= m^2 and 0 <= n^2, hence the following constraints on a:

0 <= (c + a) / 2  and 0 <= (c - a) / 2
=> -c <= a <= c

So given c, you have to iterate over [| -c, c |] (integer range) and compute m and n. Observe that we are searching for integers here, not for real numbers, so square roots must results in integer, hence (c + a) / 2 and (c - a) / 2 must be integers too, so (c + a) and (c - a) must be multiple of 2, so a can iterate over the range by a step of 2.

  for (int a = -c; a <= c; a += 2) {
      double m2 = (c + a) * 0.5;
      double n2 = (c - a) * 0.5;

      double m_abs = Math.sqrt(m2);
      double n_abs = Math.sqrt(n2);

      if (Math.floor(m_abs) == m_abs &&
              Math.floor(n_abs) == n_abs) {

                      // sqrt(x^2) = abs(x^2) = +/- x
          System.out.println(Double.toString(-m_abs) + ", " + Double.toString(-n_abs));
          System.out.println(Double.toString(-m_abs) + ", " + Double.toString(n_abs));
          System.out.println(Double.toString(m_abs) + ", " + Double.toString(-n_abs));
          System.out.println(Double.toString(m_abs) + ", " + Double.toString(n_abs));
      }
  }

Answer 5

I'd say this is a duplicate of this question. The question here is slightly more general, i.e. the question does not ask for c to be a square, but this is addressed in previous answers too. And here is also a nice description of the factorization of Gaussian integers, which is not fully described in the other question.