CODEWITHSUNDEEP
javaperformancealgorithm
user1007522
user1007522

Reputation: 8118

Can I make this code about EulerProblem much faster?

I've written a program that must find the solution to a EulerProblem. I want to train my program skills that's why I've signed up on euler.

This is the problem:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

and this is my code, but it runs soo slow, it take hours to give me the right abc.

static int findTriplet(int getal)
{
    boolean test = false;
    for(int a = 1; !test; a++)
        for(int b = a+1; !test; b++)
            for(int c = b+1; !test; c++)
            {
                if( a*a + b*b == c*c)
                {
                    if(a+b+c == getal)
                    {
                        return (a*b*c);
                    }
                }

            }
    return 0;
}

Is it possible to make the code much faster or is it normal that it takes hours?

Kind regards,

EDIT:

Thanks for helping. The !test boolean was useless sorry for that, This works : 

static int findTriplet(int getal)
{
    for(int a = 1; a < 1000; a++)
        for(int b = a+1; b < 1000; b++)
            for(int c = b+1; c < 1000; c++)
            {
                if( a*a + b*b == c*c)
                {
                    if(a+b+c == getal)
                    {
                        return (a*b*c);
                    }
                }

            }
    return 0;
}

I've also wrote a haskell variation that also does the trick.

Think this was easier in Haskell and more efficient.

Thaks for the tips.

Upvotes: 1

Views: 288

Answers (3)

Mike Dunlavey
Mike Dunlavey

Reputation: 40679

Look at a tall, thin, right triangle, with base a, height b, and hypotenuse c. First a and b are always less that c, and c = sqrt(a*a+b*b) so as the other posters said, you only need to search over a and b. You also know that a+b >= c so there's no point in looking at small a,b pairs.

Now, suppose you start with a=0, b=500, so c==500, and the total perimeter is 1000. Now you increase a by 1 and calculate the perimeter. It will be a little more than 1000. Then you decrease b by 1. Then the perimeter will be a little less than 1000. Then increase a by 1 until perimeter is > 1000 again.

So, as long as the perimeter is <= 1000, increase a. As long as it is > 1000, decrease b. If it is equal to 1000, you've got one answer. Then keep going.

You only need to do this as long as a<b.

This algorithm should be O(N), because it doesn't waste time with small pairs.

Then all you have to do is prove to yourself that it won't miss any answers. You do that by assuming there's a valid a,b answer that it does miss, and show that's impossible.

Upvotes: 0

Coren
Coren

Reputation: 5637

In order to optimize this naive algorithm, you have first to understand that :

  1. Your actual source code does not stop at all. It will run as long as test is false. You also take the risk to encounter an overflow of c.
  2. Trying every possible combination of a, b and c would result in trying 1000*999*988= 997 002 000 times (!).
  3. Key points in this algorithms are :
    • stop conditions in loops
    • ways to find next one to try
    • ways to reduce loops if possible

Now, you know that you need to :

  1. find ways to avoid the third loop, using conditions of your problems
  2. find ways to increment a and b more smartly, using conditions of your problems
  3. find ways to stop loops earlier, using conditions of your problems

Here are some hints for easy optimisations :

  • As amit & sirko said, you can guess c if you already know a and b.
  • You don't need to recompute a*a each time you're checking a new b
  • You don't need to check until a < 1000 and b < 999, there is far less possible combinations

And some hints for harder optimisations :

  • You don't need to recompute b*b each time too
  • You don't to need browse every possible combinations

Upvotes: 5

amit
amit

Reputation: 178471

The last for is redundant, you can find c = sqrt(a^2 + b^2), which will make your algorithm much faster.

Actually you will only have to check if there is a c in N [natural numbers] such that sqrt(a^2 + b^2) = c, and check if a+b+c == 1000

This optmization will make your solution O(n^2) instead O(n^3), 1000 times faster!

EDIT: As discussed in the comments:

  1. There could be a faster solution then checking c = sqrt(a^2 + b^2): c = 1000 - a -b, but the important part is doing it in O(n^2) and not O(n^3).
  2. This answer is more a guideline then a full answer. There is more work to be done on the stop conditions of your loop. The purpose of this answer is only to give you an idea how it can be done faster by magnitude.

Upvotes: 1

Related Questions