Anonymous user
Pythagorean triples/Java/Brute force primitives: Difference between revisions
Pythagorean triples/Java/Brute force primitives (view source)
Revision as of 01:48, 12 August 2011
, 12 years agoWhen I said "very very slight speedup" I was only looking at the perimeter < 1000 results. It actually makes a huge difference.
m (a*b = 0 (mod 12) for all triples, very very slight speedup, checking that a*b*c = 0 (mod 60) actually slowed it down) |
(When I said "very very slight speedup" I was only looking at the perimeter < 1000 results. It actually makes a huge difference.) |
||
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.
| |||