Rosetta Code

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

Page Discussion

Pythagorean triples/Java/Brute force primitives (view source)

Revision as of 20:45, 20 December 2011

127 bytes removed ,  12 years ago
m
Somewhere in there I got rid of the need for 12 as a BigInteger, reformat
m (It turns out that the GCD check can speed it up a little bit)
m (Somewhere in there I got rid of the need for 12 as a BigInteger, reformat)
 
(2 intermediate revisions by the same user not shown)
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, 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 markmarks the primitives.
 
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.
Line 8:
import java.util.Set;
import java.util.TreeSet;
 
import static java.math.BigInteger.*;
 
public class PythTrip{
publicprivate static final BigInteger TWO = BigInteger.valueOf(2),
B3 = BigInteger.valueOf(3), B3B4 = BigInteger.valueOf(34),
B7 = BigInteger.valueOf(7), B4B31 = BigInteger.valueOf(431),
B7B127 = BigInteger.valueOf(7127), B191 //used= for checking primitive propertiesBigInteger.valueOf(191);
//change this to whatever perimeter limit you want;the RAM's the limit▼
B12 = BigInteger.valueOf(12),▼
private static BigInteger B31LIMIT = BigInteger.valueOf(31100),;
 
B127 = BigInteger.valueOf(127),▼
public static class Triple implements Comparable<Triple>{▼
B191 = BigInteger.valueOf(191);
BigInteger a, b, c, peri;
▲ //change this to whatever perimeter limit you want;the RAM's the limit
boolean prim;▼
private static BigInteger LIMIT = BigInteger.valueOf(100);
 
▼
public Triple(BigInteger a, BigInteger b, BigInteger c, boolean prim){
▲ public static class Triple implements Comparable<Triple>{
BigInteger this.a, b,= c, peria;
}this.b = b;▼
publicthis.c Triple(BigInteger a, BigInteger b, BigInteger= c) {;
this.aperi = a.add(b).add(c);
this.bprim = bprim;
this.c = c;}
 
peri = a.add(b).add(c);▼
public Triple scale(long }k){
▲ return new B127 = Triple(a.multiply(BigInteger.valueOf(127k)), b
▲
▲ B12 = .multiply(BigInteger.valueOf(12k)), c.multiply(BigInteger
public Triple scale(long k){▼
return new Triple(a.multiply(BigInteger.valueOf(k)), prim && k == 1);
▲ }
b.multiply(BigInteger.valueOf(k)),
 
c.multiply(BigInteger.valueOf(k)));
}@Override
▲ public Tripleboolean scaleequals(longObject kobj){
@Overrideif(obj.getClass() != this.getClass())
public boolean equals(Object obj) {return false;
Triple trip if(obj.getClass() != this.getClass()Triple) return falseobj;
return a.equals(trip.a) && Triple b.equals(trip.b) =&& c.equals(Tripletrip.c)obj;
}▼
return a.equals(trip.a) && b.equals(trip.b) && c.equals(trip.c);
 
▲ }
@Override▼
public int compareTo(Triple @Overrideo){
public int compareToif(!a.equals(Triple o.a)) {
//sort byreturn a, then b, then c.compareTo(o.a);
if(!ab.equals(o.ab)) return a.compareTo(o.a);
if(!b.equals(o.b)) return b.compareTo(o.b);
if(!c.equals(o.c)) return c.compareTo(o.c);
return 0c.compareTo(o.c);
}return 0;
}
 
▲ @Override
public String toString(){
return a + ", " + b + ", " + c + (prim ? " primitive" : "");
}
}
 
▲
private static Set<Triple> trips = new TreeSet<Triple>();
 
public static void addAllScales(Triple trip){
long k = 2;
Triple tripCopy = new Triple(trip.a, trip.b, trip.cscale(k++);
while(tripCopy.peri.compareTo(LIMIT) <= 0){
trips.add(tripCopy);
tripCopy = trip.scale(k++);
}
}
 
public static void main(String[] args){
long primCount = 0;
long start = System.currentTimeMillis();
 
BigInteger peri2 = LIMIT.divide(TWO), peri3 = LIMIT.divide(B3);
peri3 = LIMIT.divide(B3);▼
 
for(BigInteger a = B3; a.compareTo(peri3) < 0; a = a.add(ONE)){
Line 83 ⟶ 84:
 
//b is the opposite evenness of a so increment by 2
for(BigInteger b = a.add(ONE); b.compareTo(peri2) < 0; b = b
b.compareTo(peri2) < 0; b = b.add(TWO)){
//skip if both or neither of a and b are divisible by each of 3 and 4
if(amod3 == b.mod(B3).equals(ZERO) ||
|| amod4 == b.mod(B4).equals(ZERO)) continue;
//if a^2 + b^2 is not a perfect square then don't even test for c'scontinue;
//if a^2+b^2 isn't a perfect square, don't even test for c's
BigInteger aabb = aa.add(b.multiply(b));
if((aabb.and(B7).intValue() != 1) &&
&& (aabb.and(B31).intValue() != 4) &&
&& (aabb.and(B127).intValue() != 16) &&
&& (aabb.and(B191).intValue() != 0)) continue;
if(!a.gcd(b).equals(ONE)) continue;
if(!a.gcd(b).equals(ONE))
▲ peri = a.add(b).add(c)continue;
BigInteger ab = a.add(b);
 
for(BigInteger// c =is always odd for primitives so if b.add(b.testBit(0) ?is TWO:ONE);odd start at b+2
// otherwise c.compareTo(peri2) < 0; c = c.add(TWO)){b+1
for(BigInteger c = b.add(b.testBit(0) //if? a+b+cZERO >: periLimitONE); c
if(ab.add(c) .compareTo(LIMITperi2) >< 0; c = c.add(TWO)){
 
break;▼
}// 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){
break;
}else if (compare == 0){
Triple prim = new Triple(a, b, c, true);
if(trips.add(prim)){ //if it's new
primCount++; //count it
addAllScales(prim); //add its scales
}
}
Line 118 ⟶ 123:
}
}
for(Triple trip : trips){
System.out.println(trip);
}
System.out.println("Runtime: " + (System.currentTimeMillis() - start));
System.out.println("Up to a perimeter of " + LIMIT + ", there are "
+ trips.size() + " triples, of which " + primCount + " are primitive.");
▲ peri3+ =" LIMITare primitive.divide(B3");
}
}</lang>
Output:
<pre>3, 4, 5 primitive
5, 12, 13 primitive
6, 8, 10
7, 24, 25 primitive
8, 15, 17 primitive
9, 12, 15
9, 40, 41 primitive
10, 24, 26
12, 16, 20
12, 35, 37 primitive
15, 20, 25
15, 36, 39
16, 30, 34
18, 24, 30
20, 21, 29 primitive
21, 28, 35
24, 32, 40
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/194068...194071"