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

Content added Content deleted
m (Don't have to scale by 1. Negligible effect on the run time.)
(Another slight speedup)
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, 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]]). 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.


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>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.
Line 13: Line 13:
public class PythTrip2{
public class PythTrip2{
public static final BigInteger TWO = BigInteger.valueOf(2),
public static final BigInteger TWO = BigInteger.valueOf(2),
B7 = BigInteger.valueOf(7), //B7...B191 are used for skipping non-square "a^2 + b^2"s
B3 = BigInteger.valueOf(3),
B4 = BigInteger.valueOf(4),
B7 = BigInteger.valueOf(7), //used for checking primitive properties
B12 = BigInteger.valueOf(12),
B12 = BigInteger.valueOf(12),
B31 = BigInteger.valueOf(31),
B31 = BigInteger.valueOf(31),
Line 72: Line 74:
long primCount = 0;
long primCount = 0;


BigInteger peri2 = LIMIT.divide(BigInteger.valueOf(2)),
BigInteger peri2 = LIMIT.divide(TWO),
peri3 = LIMIT.divide(BigInteger.valueOf(3));
peri3 = LIMIT.divide(B3);


for(BigInteger a = ONE; a.compareTo(peri3) < 0; a = a.add(ONE)){
for(BigInteger a = B3; a.compareTo(peri3) < 0; a = a.add(ONE)){
BigInteger aa = a.multiply(a);
BigInteger aa = a.multiply(a);
boolean amod3 = a.mod(B3).equals(ZERO);
boolean amod4 = a.mod(B4).equals(ZERO);


//b is the opposite evenness of a so increment by 2
//b is the opposite evenness of a so increment by 2
for(BigInteger b = a.add(ONE);
for(BigInteger b = a.add(ONE);
b.compareTo(peri2) < 0; b = b.add(TWO)){
b.compareTo(peri2) < 0; b = b.add(TWO)){
//only one of a and b can be divisible by 3
if(amod3 && b.mod(B3).equals(ZERO)) continue;
//only one of a and b can be divisible by 4
if(amod4 && b.mod(B4).equals(ZERO)) continue;
//if a^2 + b^2 is not a perfect square then don't even test for c's
//if a^2 + b^2 is not a perfect square then don't even test for c's
BigInteger aabb = aa.add(b.multiply(b));
BigInteger aabb = aa.add(b.multiply(b));
Retrieved from "https://rosettacode.org/wiki/Pythagorean_triples/Java/Brute_force_primitives"