Pythagorean triples/Java/Brute force primitives: Difference between revisions

Content added Content deleted
(This is what I was really looking for when I made that last optimization)
m (It turns out that the GCD check can speed it up a little bit)
Line 1: Line 1:
{{works with|Java|1.5+}}
{{works with|Java|1.5+}}
This version brute forces primitive triple candidates and then scales them to find the rest (under the perimeter limit of course). Since it only finds the primitives mathematically it can optimize its candidates based on some of the properties [[wp:Pythagorean_triple#Elementary_properties_of_primitive_Pythagorean_triples|here]] -- namely that a and b have opposite evenness, only one of a and b is divisible by 3, only one of a and b is divisible by 4, c is always odd, and that a<sup>2</sup> + b<sup>2</sup> must be a perfect square (which [[wp:Square_number#Properties|don't ever end in 2, 3, 7, or 8]]). Notably, it doesn't use a GCD function to check for primitives (<code>BigInteger.gcd()</code> uses the binary GCD algorithm, [[wp:Computational_complexity_of_mathematical_operations#Number_theory|which is O(n<sup>2</sup>)]]). For a perimeter limit of 1000, it is about 5 times faster than [[Pythagorean triples#Java|the other brute force version]]. For a perimeter limit of 10000, it is about 15 times faster. It also does not mark the primitives.
This version brute forces primitive triple candidates and then scales them to find the rest (under the perimeter limit of course). Since it only finds the primitives mathematically it can optimize its candidates based on some of the properties [[wp:Pythagorean_triple#Elementary_properties_of_primitive_Pythagorean_triples|here]] -- namely that a and b have opposite evenness, only one of a and b is divisible by 3, only one of a and b is divisible by 4, c is always odd, and that a<sup>2</sup> + b<sup>2</sup> must be a perfect square (which [[wp:Square_number#Properties|don't ever end in 2, 3, 7, or 8]]). After using those rules to eliminate candidates for a,b pairs, it checks that a and b are coprime. Since many a,b pair candidates have already been eliminated, this check actually speeds things up a little bit by letting the program skip some c loops. For a perimeter limit of 1000, it is about 5 times faster than [[Pythagorean triples#Java|the other brute force version]]. For a perimeter limit of 10000, it is about 17 times faster. It also does not mark the primitives.


It defines a <code>Triple</code> class which is comparable so it can be placed in a <code>Set</code> to remove duplicates (e.g. this algorithm finds [15, 20, 25] as a primitive candidate after it had already been added by scaling [3, 4, 5]). It also can scale itself by an integer factor.
It defines a <code>Triple</code> class which is comparable so it can be placed in a <code>TreeSet</code> for easy sorting and to remove duplicates (the GCD check should remove duplicates, but it's nice to make sure). It also can scale itself by an integer factor.


Note: this implementation also keeps all triples in memory. Be mindful of large perimeter limits.
Note: this implementation also keeps all triples in memory. Be mindful of large perimeter limits.
Line 11: Line 11:
import static java.math.BigInteger.*;
import static java.math.BigInteger.*;


public class PythTrip2{
public class PythTrip{
public static final BigInteger TWO = BigInteger.valueOf(2),
public static final BigInteger TWO = BigInteger.valueOf(2),
B3 = BigInteger.valueOf(3),
B3 = BigInteger.valueOf(3),
Line 94: Line 94:
(aabb.and(B127).intValue() != 16) &&
(aabb.and(B127).intValue() != 16) &&
(aabb.and(B191).intValue() != 0)) continue;
(aabb.and(B191).intValue() != 0)) continue;
if(!a.gcd(b).equals(ONE)) continue;
BigInteger ab = a.add(b);
BigInteger ab = a.add(b);


Retrieved from "https://rosettacode.org/wiki/Pythagorean_triples/Java/Brute_force_primitives"