Thread: Problem with Pythagorean triple etc.

void main - see faq -

SKeane: But then again, they aren't really expected to know the math... what a sham society it is nowadays.

This will generate and print all triples {a^2 + b^2 == c^2} for c < 100 million using fast "m-n" algorithm. Have fun turning it in.

Code:

#include <stdio.h>

size_t gcd(size_t m, size_t n)
{
	if(m == n) return m;
	else if(m < n) return gcd(n - m, m);
	else return gcd(m - n, n);
}
int main(void)
{
	size_t max = 10000, k, m, n;
	for(m = 1; m < max; ++m)
		for(n = m+1; n < max; n += 2)
			if(gcd(m, n) == 1)
				for(k = 1; (n*n + m*m)*k < max*max; ++k)
					printf("%d^2 + %d^2 = %d^2\n", (n*n - m*m)*k, 2*m*n*k, (n*n + m*m)*k);
	return 0;
}

Originally Posted by jafet

This will generate and print all triples [...] for c < 100 million using fast "m-n" algorithm. Have fun turning it in.

It seems to miss things like (5,12,13) or (7,24,25).

I tinkered with this, just because, and found a couple ways to help speed up and make safer the brute force method. FWIW.

Code:

/**
 * Display Pythagorean triples up to 'size'.
 * @param  size  the maximum length of a side
 * @return the number of Pythagorean triples found
 * @example <code>unsigned int count = pythagorean_triples(500);</code>
 * @Notes  Being brute force, this gets very slow for large values of size.
 * @Notes  This code <i>does</i> check for integer overflow with the squared
 *         values.
 */
unsigned int pythagorean_triples(unsigned int size)
{
    unsigned int a, b, c, len = 0, count = 0;
    for ( a = 1; a < size && a < UINT_MAX / a; ++a )
    {
        for ( b = a + 1; b < size && b < UINT_MAX / b; ++b )
        {
            for ( c = b + 1; c < size && c < UINT_MAX / c; ++c )
            {
                unsigned int lhs = a * a + b * b;
                unsigned int rhs = c * c;
                if ( lhs < rhs )
                {
                    break; /* rhs will only get bigger */
                }
                else if ( lhs == rhs )
                {
                    if ( ++count == UINT_MAX )
                    {
                        goto done;
                    }
                    len += printf("(%u,%u,%u),", a, b, c);
                    if ( len >= 60 )
                    {
                        len = 0;
                        putchar('\n');
                    }
                    fflush(stdout);
                    break; /* no reason to continue checking more c's */
                }
            }
        }
    }
    done:
    if ( len )
    {
        putchar('\n');
    }
    return count;
}

ok SKeane, what is your idea of a good assignment? well, not for experts, but for those still learning the language. can you give examples on: (not the overly complicated ones)

1.) loops and nested loops
2.) pointers
3.) arrays and multidimensional arrays
4.) strings
5.) linear linked lists
6.) a combination of some or all of this.

hehehe! so when a classmate or friend of mine asks me to help them, i'd have sumthin to let them solve.

It seems to miss things like (5,12,13) or (7,24,25).

Or maybe you just aren't patient enough (It prints the first aforementioned pair at least 20,000 lines down.) I could try print them out in sorted order, but it might get a little messy.


sangken: Try a tic-tac-toe AI. Study minimax trees, alpha-beta pruning and (very effective for this game) transposition tables. It's not very hard once you get the hang of it.

Learns you: most conventional C/C++ constructs, recursion, hash tables, arrays (if you use conventional board representation) or bitwise operators (if you use bitboards). You can practise making a simple GUI, and you can show off your work to non-programmers too.

ok SKeane, what is your idea of a good assignment?

Presumably something which allows a student to practise programming in a useful and constructive way, instead of imposing stupid restrictions and forcing students to turn to inefficient practices, like coming to this board for trivial help.