CODEWITHSUNDEEP
c++algorithmmathcomputer-science
Alizrr
Alizrr

Reputation: 13

Pythagorean triple nested loops missunderstanding

Greetings and regards;

I was trying to find Pythagorean Triple numbers less than 1000.

Fortunately I was able to find the algorithm for it, Here it is:

for (int a = 1; a < 1000; a++)
{
    for (int b = a; b < 1000; b++)
    {
        for (int c = b; c < 1000; c++)
        {
            if ((a * a) + (b * b) == (c * c))
            {
                cout << "( " << a << ", " << b << ", " << c << " )";
                cout << endl;
            }
        }
    }
}

But I don't understand a thing about this code! Why does the initial value of each loop start from the value of the previous loop ? While the initial value of each loops can be started from 1 !

What's the reason for this ?

Upvotes: 0

Views: 741

Answers (2)

Rachit Chaudhary
Rachit Chaudhary

Reputation: 98

For a < b :

Pythagorean triples appear in pairs i.e. (a,b,c) and (b,a,c) : a,b < c ∀ a,b,c ∈ ℕ. Since other one of the pair becomes a trivial solution if one is found. Suppose a Pythagorean triple (a,b,c) is found such that a < b then we immediately know that (b,a,c) is also a Pythagorean triple so we don't want our program to search for it as it will just increase the search domain and thus the execution time. To avoid that, loops are set as a≤b. However, you can also initiate them as a < b or b = a + 1

For b < c or a < b < c:

You can initiate them as a < b < c or (c = b + 1 and b = a + 1) because no Pythagorean triple can be of form (b,b,c) as b^2 + b^2 = 2 * b^2 = c^2, that means c = b * sqrt(2) in which c is an integer and b * sqrt(2) is an irrational number, so the two can never be equal and integer solution can never exist. But c = b * sqrt(2) also says that c > b.

Therefore, a < b < c

Upvotes: 1

Neven V.
Neven V.

Reputation: 452

Pythagorean triplets have only one way of being ordered: if a² + b² = c² then one can prove than a² + c² ≠ b² and b² + c² ≠ a².

From the above and a few special cases (a = 0 is excluded by definition, a ∊ (0, 2] are easy to check by hand), it follows that one only has to check triplets for which 2 < a ≤ b < c, and this is (almost) what the tree loops do.

There are two reasons for this:

  1. By setting up the loop so that a ≤ b ≤ c we guarantee that no triplet appears more than once

  2. There are fewer triplets to test, so we reduce the execution time by a constant factor.

Upvotes: 0

Related Questions