Anonymous user
Pythagorean triples/Java/Brute force primitives: Difference between revisions
Pythagorean triples/Java/Brute force primitives (view source)
Revision as of 17:07, 15 July 2011
, 12 years agoExtra notes and comments, move a comparison so it is only calculated if needed.
m (Notes about the Triple class, also THREE and FOUR were never used) |
m (Extra notes and comments, move a comparison so it is only calculated if needed.) |
||
Line 1:
{{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 3 times faster than [[Pythagorean triples#Java|the other brute force version]]. For a perimeter limit of 10000, it is about 5 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.
Note: this implementation also keeps all triples in memory. Be mindful of large perimeter limits.
<lang java5>import java.math.BigInteger;
import java.util.Set;
Line 25 ⟶ 27:
public Triple scale(long k){
return new Triple(a.multiply(BigInteger.valueOf(k)),
}
Line 38 ⟶ 40:
@Override
public int compareTo(Triple o) {
//sort by a, then b, then c
if(!a.equals(o.a)) return a.compareTo(o.a);
if(!b.equals(o.b)) return b.compareTo(o.b);
Line 60 ⟶ 63:
}
}
public static void main(String[] args){
long primCount = 0;
long start = System.currentTimeMillis();
Line 66 ⟶ 69:
BigInteger peri2 = LIMIT.divide(BigInteger.valueOf(2)),
peri3 = LIMIT.divide(BigInteger.valueOf(3));
for(BigInteger a = ONE; a.compareTo(peri3) < 0; a = a.add(ONE)){
BigInteger aa = a.multiply(a);
//b is the opposite evenness of a so increment by 2
for(BigInteger b = a.add(ONE);
Line 76 ⟶ 81:
BigInteger ab = a.add(b);
BigInteger aabb = aa.add(bb);
for(BigInteger c = b.add(b.and(ONE).equals(ONE)? TWO:ONE);
c.compareTo(peri2) < 0; c = c.add(TWO)){
int compare = aabb.compareTo(c.multiply(c));▼
//if a+b+c > periLimit
if(ab.add(c).compareTo(LIMIT) > 0){
break;
}
▲ int compare = aabb.compareTo(c.multiply(c));
//if a^2 + b^2 != c^2
if(compare < 0){
| |||