Anonymous user
Pythagorean triples/Java/Brute force primitives: Difference between revisions
Pythagorean triples/Java/Brute force primitives (view source)
Revision as of 18:13, 15 July 2011
, 12 years agoFursther optimization by skipping more a,b pair candidates (noted in the comments), rm runtime calculations
m (Incredibly slight optimization (took the runtime of a 10k perimeter limit from 90 seconds to 89 seconds on this computer)) |
(Fursther optimization by skipping more a,b pair candidates (noted in the comments), rm runtime calculations) |
||
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
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 12:
public class PythTrip2{
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
B31 = BigInteger.valueOf(31),
B127 = BigInteger.valueOf(127),
B191 = BigInteger.valueOf(191);
private static BigInteger LIMIT = BigInteger.valueOf(100);
Line 65 ⟶ 69:
public static void main(String[] args){
long primCount = 0;
//change this to whatever perimeter limit you want;the RAM's the limit
BigInteger peri2 = LIMIT.divide(BigInteger.valueOf(2)),
Line 78 ⟶ 82:
BigInteger bb = b.multiply(b);
//if a^2 + b^2 is not a perfect square then don't even test for c's
if(aa.add(bb).toString().matches(".*[2378]")) continue;▼
BigInteger ab = a.add(b);▼
BigInteger aabb = aa.add(bb);
if((aabb.and(B7).intValue() != 1) &&
(aabb.and(B31).intValue() != 4) &&
(aabb.and(B127).intValue() != 16) &&
▲ BigInteger ab = a.add(b);
for(BigInteger c = b.add(b.and(ONE).equals(ONE)? TWO:ONE);
Line 106 ⟶ 113:
System.out.println(trip);
}
System.out.println("Up to a perimeter of " + LIMIT + ", there are "
+ trips.size() + " triples, of which " + primCount + " are primitive.");
Line 129 ⟶ 135:
21, 28, 35
24, 32, 40
Up to a perimeter of 100, there are 17 triples, of which 7 are primitive.</pre>
| |||