Unknown Software Exception

Hey guys I'm working on a Pythagorean Triple program.

In my program everything worked and I found all the possible Pythagorean triples below the value 500. Unfortunately I had repeats due to the fact that the legs of the triangle could just "swap" value. I tried to correct the problem by using a three dimensional array called "used." Because I have a maximum of 500 on each side of the triangle I had to use 500 three times in my boolean value "used." I think this is just too large a value for my compiler but maybe I did something wrong. Check it out.

Code:

void calculate()
{
	int side1 = 1;
	int side2 = 1;
	int hypo = 1;
	int triplecounter = 0;
	bool used[500][500][500] = {false};

	for (side1 = 1; side1 <= 500; side1++)	{

		for (side2 = 1; side2 <= 500; side2++)	{

			for (hypo = 1; hypo <= 500; hypo++)	{

				if (used[side1][side2][hypo] == false)	{

					if (used[side2][side1][hypo] == false)	{

						if ((hypo * hypo) == (side1 * side1) + (side2 * side2))	{

							used[side1][side2][hypo] = true;

							used[side2][side1][hypo] = true;

							cout << "A Pythagorean triple is " << hypo << " " << side1 << " " << side2 << "\n\n";

							triplecounter = (triplecounter + 1);

						}

					}
				}
			}
		}
	}

	cout << triplecounter << "\n\n";
}

For one thing, 500^3/1024/1024 = 238 MEGABYTES OF RAM.

Because you want any of the three sides to have a maximum size of 500, then you really only need to limit the size of the hypotenuse, since it is always going to be greater than either of the two other sides.

If you can generate all combinations with the code you already have and you don't care which side is the hypotenuse and you don't care which non-hypotenuse side is which, for example 3-4-5 is the same as 4-3-5 is the same as 5-3-4, etc., then you could generate all three sides and place the smaller of the three sides in memberA, the next smallest side in membeB, and the hypotenuse in memberC of a struct and store the struct in a container. Once you have generated a triple and sorted the sizes, then search the container for any triple already found for the value of one of the members of the current triple. If any triple already found contains any of the members values in the current triple as the same member value, then don't add the current triple to the container. Since the hypotenuse size will always be in memberC and there can only be one set of non-hypotenuse sides that will generate the give hypotenuse and still be a Pythagorean triple, then that's the member I'd compare, but it really shouldn't matter if the sides are sorted by length, because I don't believe there is any Pythagorean triple that has any of the three sides equal to any of the three sides of another Pythagorean triple unless the hypotenuse of one triple is used as the non-hypotenuse side of another triple.

You are probably getting a stack overflow because of the size of the "used" array which (assuming 1 byte bools) looks like it weighs in at about 125,000,000 bytes (approx 119 MB... I guess Orbode is thinking 2 byte bools?). That is way too much to allocate on the stack. So you can do a couple things:

1. You could do dynamic memory allocation of the used array:

Code:

bool ***used;

used = new bool**[500];
for( int i = 0; i < 500; ++i )
{
    used[i ] = new bool*[500];
    for( int j = 0; j < 500; ++j )
    {
        used[i ][j] = new bool[500];
        for( int k = 0; k < 500; ++k ) used[i ][j][k] = false;
    }
}

You could allocate a contiguous chunk instead of all the smaller allocations but you are still wasting a lot of space since there are only 386 triples that I found using your code and the above method. Plus you then need to remember to delete all that memory.

2. Create a triple/triangle object (method hinted at by elad) and overload the == operator. Push your triples into a container, checking first to make sure that a match does not already exist in the container. This would only require you to store the 386 objects and that's all. Since you basically already have a "working" program, I'll show you what I was thinking of:

Code:

class triple
{
    int side1, side2, hypotenuse;
public:
    triple(int s1 = 1, int s2 = 1, int hyp = 1) : side1(s1),
                                                  side2(s2),
                                                  hypotenuse(hyp)
    {
    }
    bool operator()() const
    {
        return side1*side1+side2*side2==hypotenuse*hypotenuse;
    }
    friend bool operator==(const triple& lhs,const triple& rhs);
    friend ostream& operator<<(ostream& os,const triple& rhs);
};

bool operator==(const triple& lhs,const triple& rhs)
{
    return ( lhs.hypotenuse == rhs.hypotenuse &&
             ( ((lhs.side1==rhs.side1) && (lhs.side2==rhs.side2)) ||
               ((lhs.side1==rhs.side2) && (lhs.side2==rhs.side1))
             )
          );
}

ostream& operator<<(ostream& os,const triple& rhs)
{
    return os << hyp << ' ' << side1 << ' ' << side2;
}

...

vector<triple> triples;
for( int i = 1; i <= 500; ++i )
    for( int j = 1 j <= 500; ++j )
        for( int k = 1; k <= 500; ++k )
        {
            triple trip(i,j,k);
            if( trip() && (find(triples.begin(),triples.end(),trip) == triples.end()) )
                triples.push_back(trip);
            cout << "A Pythagorean triple is " << trip << endl;
        }

cout << triples.size() << endl << endl;

386 triple objects only takes up 4636 bytes (assuming 4 byte ints) then you also have the vectors overhead which is constant regardless of the number of elements it stores so we wind up with a big space savings doing it this way.

BTW, there was one other problem with your code I saw (if you had been able to get it to work as posted):

Code:

bool used[500][500][500] = {false};

for (side1 = 1; side1 <= 500; side1++) {
    for (side2 = 1; side2 <= 500; side2++) {
        for (hypo = 1; hypo <= 500; hypo++) {
            if (used[side1][side2][hypo] == false) {
                if (used[side2][side1][hypo] == false) {
                    if ((hypo * hypo) == (side1 * side1) + (side2 * side2)) {
                        used[side1][side2][hypo] = true;

Tell me, is used[500][500][500] a valid array element? You seemed to forget that arrays are 0-based in C/C++ so the indicies can only go up to 499 and still be valid. I think you meant to put used[side1-1][side2-1][hypo-1] instead.

Originally Posted by elad

Since the hypotenuse size will always be in memberC and there can only be one set of non-hypotenuse sides that will generate the give hypotenuse and still be a Pythagorean triple

That's not true, take these triplets for example

7 24 25 and 15 20 25

both have hypotenuse 25 with different set of non-hypotenuse legs

Originally Posted by Denied88

Hey guys I'm working on a Pythagorean Triple program.

In my program everything worked and I found all the possible Pythagorean triples below the value 500.

Instead of generating all possible triplets and eliminating equivalent ones, why not just generate unique triplets in the first place:

Suppose a is the shortest side, b is the next side, (and c is the hypotenuse):

Code:

Let a go from 1 to 498 (obviously, could be less than 498, but what the heck)
  Let b go from a to 499 (obviously, could be less than 499, but what the heck)
    Let c go from b+1 to 500 
      Calculate a-squared, b-squared and c-squared and do the comparison.

Regards,

Dave