Unknown Software Exception

This is a discussion on Unknown Software Exception within the C++ Programming forums, part of the General Programming Boards category; Hey guys I'm working on a Pythagorean Triple program. In my program everything worked and I found all the possible ...

  1. #1
    Registered User
    Join Date
    May 2005
    Posts
    9

    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";
    }

  2. #2
    Registered User
    Join Date
    Mar 2005
    Posts
    28
    For one thing, 500^3/1024/1024 = 238 MEGABYTES OF RAM.

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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're only born perfect.

  4. #4
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,793
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  5. #5
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Quote 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

  6. #6
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote 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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Exception handling in a large project
    By EVOEx in forum C++ Programming
    Replies: 7
    Last Post: 01-25-2009, 06:33 AM
  2. exception handling
    By coletek in forum C++ Programming
    Replies: 2
    Last Post: 01-12-2009, 04:28 PM
  3. get keyboard and mouse events
    By ratte in forum Linux Programming
    Replies: 10
    Last Post: 11-17-2007, 04:42 PM
  4. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  5. UNICODE and GET_STATE
    By Registered in forum C++ Programming
    Replies: 1
    Last Post: 07-15-2002, 03:23 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21