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

359 bytes added ,  12 years ago
m
Somewhere in there I got rid of the need for 12 as a BigInteger, reformat
m (Moved the LIMIT declaration but forgot to take the comment with it)
m (Somewhere in there I got rid of the need for 12 as a BigInteger, reformat)
 
(10 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]]). NotablyAfter using those rules to eliminate candidates for a,b pairs, it doesn'tchecks usethat a GCDand functionb toare checkcoprime. forSince primitivesmany (<code>BigInteger.gcd()</code>a,b usespair thecandidates binaryhave GCDalready algorithmbeen eliminated, [[wp:Computational_complexity_of_mathematical_operations#Number_theory|whichthis ischeck O(n<sup>2</sup>)]])actually speeds things up a little bit by letting the program skip some c loops. For a perimeter limit of 1000, it is about 45 times faster than [[Pythagorean triples#Java|the other brute force version]]. For a perimeter limit of 10000, it is about 817 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>SetTreeSet</code> for easy sorting and to remove duplicates (e.g.the thisGCD algorithmcheck findsshould [15,remove 20duplicates, 25] as a primitive candidate afterbut it's hadnice alreadyto been added by scaling [3, 4,make 5]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.
Line 8:
import java.util.Set;
import java.util.TreeSet;
import static java.math.BigInteger.ONE;▼
 
▲import static java.math.BigInteger.ONE*;
public class PythTrip2{▼
 
public static final BigInteger TWO = BigInteger.valueOf(2),▼
▲public class PythTrip2PythTrip{
B7 = BigInteger.valueOf(7), //B7...B191 are used for skipping non-square "a^2 + b^2"s
private static final BigInteger B31TWO = BigInteger.valueOf(312),
B3 = BigInteger.valueOf(3), B127B4 = BigInteger.valueOf(1274),
B7 = BigInteger.valueOf(7), B191B31 = BigInteger.valueOf(19131);,
private static B127 = BigInteger.valueOf(127), LIMITB191 = BigInteger.valueOf(100191);▼
//change this to whatever perimeter limit you want;the RAM's the limit
▲ private static BigInteger LIMIT = BigInteger.valueOf(100);
▲ publicprivate static final BigInteger TWOLIMIT = BigInteger.valueOf(2100),;
▼
 
public static class Triple implements Comparable<Triple>{
BigInteger a, b, c, peri;
boolean }prim;▼
public Triple(BigInteger a, BigInteger b, BigInteger c) {▼
 
this.a = a;▼
▲ public Triple(BigInteger a, BigInteger b, BigInteger c), boolean prim){
this.b = b;▼
this.ca = ca;
perithis.b = a.add(b).add(c);
}this.c = c;
peri = a.add(b).add(c);
publicthis.prim Triple= scale(long k){prim;
}▼
return new Triple(a.multiply(BigInteger.valueOf(k)),▼
 
b.multiply(BigInteger.valueOf(k)),▼
public booleanTriple equalsscale(Objectlong objk) {▼
c.multiply(BigInteger.valueOf(k)));▼
▲ return new Triple(a.multiply(BigInteger.valueOf(k)), b
▲ }
▲ b.multiply(BigInteger.valueOf(k)), c.multiply(BigInteger
@Override .valueOf(k)), prim && k == 1);
}
▲ public boolean equals(Object obj) {
 
if(obj.getClass() != this.getClass()) return false;▼
@Override
Triple trip = (Triple)obj;▼
public boolean equals(Object obj){
return a.equals(trip.a) && b.equals(trip.b) && c.equals(trip.c);
}if(obj.getClass() != this.getClass())
▲ if(obj.getClass() != this.getClass()) return false;
@OverrideTriple trip = (Triple) obj;
publicreturn int compareToa.equals(Tripletrip.a) o&& b.equals(trip.b) {&& c.equals(trip.c);
}
//sort by a, then b, then c
 
if(!a.equals(o.a)) return a.compareTo(o.a);▼
@Override
if(!b.equals(o.b)) return b.compareTo(o.b);▼
public int compareTo(Triple o){
if(!c.equals(o.c)) return c.compareTo(o.c);
return 0;if(!a.equals(o.a))
} return a.compareTo(o.a);
if(!b.equals(o.b))
@Override return b.compareTo(o.b);
public String toStringif(!c.equals(o.c)){
return a + ", " + b + ", " + c.compareTo(o.c);
}return 0;
}
 
▼
public String toString(){
private static Set<Triple> trips = new TreeSet<Triple>();▼
return a + ", " + b + ", " + c + (prim ? " primitive" : "");
}
public static void addAllScales(Triple trip){▼
▲ }
long k = 1;▼
 
Triple tripCopy = new Triple(trip.a, trip.b, trip.c);▼
▲ private static Set<Triple> trips = new TreeSet<Triple>();
while(tripCopy.peri.compareTo(LIMIT) < 0){▼
 
trips.add(tripCopy);▼
public static void tripCopy =addAllScales(Triple trip.scale(k++);{
long k = }2;
▲ Triple tripCopy = new Triple(trip.a, trip.b, trip.cscale(k++);
▲ }
▲ while(tripCopy.peri.compareTo(LIMIT) <= 0){
public static void main(String[] args){
▲ trips.add(tripCopy);
▲ long ktripCopy = 1trip.scale(k++);
}
▲ }
 
▲ public static void addAllScalesmain(TripleString[] tripargs){
long primCount = 0;
long start = System.currentTimeMillis();
 
BigInteger peri2 = LIMIT.divide(BigIntegerTWO), peri3 = LIMIT.valueOfdivide(2B3)),;
peri3 = LIMIT.divide(BigInteger.valueOf(3));
 
for(BigInteger a = ONEB3; a.compareTo(peri3) < 0; a = a.add(ONE)){
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
for(BigInteger b = a.add(ONE); b.compareTo(peri2) < 0; b = b
b.compareTo(peri2) < 0; b = b.add(TWO)){
BigInteger//skip bbif =both or neither of a and b.multiply(b); are divisible by 3 and 4
//if(amod3 a^2 +== b^2 is not a perfect square then don't even test for c's.mod(B3).equals(ZERO)
BigInteger aabb || amod4 == aab.addmod(bbB4).equals(ZERO));
if((aabb.and(B7).intValue() != 1) && continue;
//if a^2+b^2 isn't (aabb.and(B31).intValue()a !=perfect 4)square, &&don't even test for c's
BigInteger aabb = (aabbaa.andadd(B127)b.intValuemultiply(b) != 16) && ;
if((aabb.and(B191B7).intValue() != 01)) continue;
break;&& (aabb.and(B31).intValue() != 4)▼
&& (aabb.and(B127).intValue() != 16)
▲ && c(aabb.multiplyand(BigIntegerB191).valueOfintValue(k) != 0));
▲ this.a = acontinue;
▲ if(!ba.equalsgcd(o.b)) return b.compareToequals(o.bONE));
▲ this.b = bcontinue;
BigInteger ab = a.add(b);
 
// c is always odd for primitives so if b is odd start at b+2
for(BigInteger c = b.add(b.and(ONE).equals(ONE)? TWO:ONE);
// 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(!aab.equalsadd(o.ac)) return a.compareTo(o.aLIMIT) > 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 110 ⟶ 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.");
▲ + " Tripleare trip = (Tripleprimitive.")obj;
}
}</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/194060...194071"