Skip to content

Instantly share code, notes, and snippets.

@Karunamon
Last active May 16, 2016 15:30
Show Gist options
  • Save Karunamon/467eef90c29bbe2e4fb6cdf8fd4101a5 to your computer and use it in GitHub Desktop.
Save Karunamon/467eef90c29bbe2e4fb6cdf8fd4101a5 to your computer and use it in GitHub Desktop.
Pythagorean triple finders, comparing a basic for loop vs a parallelStream
import java.util.*;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.stream.*;
class Main {
private static class tripleCandidate {
BigDecimal a;
BigDecimal b;
BigDecimal c;
tripleCandidate(BigDecimal a, BigDecimal b, BigDecimal c){
this.a = a;
this.b = b;
this.c = c;
}
}
private static BigDecimal bigSqrt(BigDecimal A, final int SCALE) {
BigDecimal x0 = new BigDecimal("0");
BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
while (!x0.equals(x1)) {
x0 = x1;
x1 = A.divide(x0, SCALE, RoundingMode.HALF_UP);
x1 = x1.add(x0);
x1 = x1.divide(new BigDecimal(2), SCALE, RoundingMode.HALF_UP);
}
return x1;
}
private static Vector<String> findTriple(BigDecimal hyp, int precision) {
BigDecimal csquared = hyp.multiply(hyp);
Vector<String> output = new Vector<>();
BigDecimal hyp_div = hyp.divide(new BigDecimal(2), RoundingMode.UP );
if (csquared.remainder(new BigDecimal(1)).compareTo(new BigDecimal(0)) == 0) {
for (BigDecimal a = new BigDecimal(1); a.compareTo( hyp_div ) <= 0 ; a = a.add(new BigDecimal(1))) {
BigDecimal b = bigSqrt(csquared.subtract( a.multiply(a) ), precision);
if (b.remainder(BigDecimal.ONE).compareTo(BigDecimal.ZERO) == 0)
{
output.add(String.valueOf(a.setScale(precision, RoundingMode.FLOOR)) + " " + String.valueOf(b) + " " + String.valueOf(hyp));
}
}
}
return output;
}
private static BigDecimal calculateB(BigDecimal a, BigDecimal csquared, int precision){
return bigSqrt(csquared.subtract( a.multiply(a) ), precision);
}
private static Vector<String> findTripleParallelStream(BigDecimal hyp, int precision) {
BigDecimal csquared = hyp.multiply(hyp);
//ArrayList<Integer> aVals = new ArrayList<>();
Vector<String> output = new Vector<>();
//BigDecimal hyp_div = hyp.divide(new BigDecimal(2), RoundingMode.UP);
//IntStream.range(1, hyp.intValue()).forEach(aVals::add); //We need integers, not ints
if (csquared.remainder(new BigDecimal(1)).compareTo(new BigDecimal(0)) != 0) {
System.exit(1);
}
IntStream.range(1, hyp.divide(new BigDecimal(2), RoundingMode.UP).intValue()).parallel()
//.mapToObj(BigDecimal::new) // Turn these Integers into BigDecimals -- 10 megs more memory, identical execution time
.mapToObj(aVal -> new tripleCandidate(new BigDecimal(aVal), calculateB(new BigDecimal(aVal), csquared, precision), hyp)) //Box it into an object
.filter(candidate -> candidate.b.remainder(BigDecimal.ONE).compareTo(BigDecimal.ZERO) == 0) //Modulo zero?
.map(candidate -> String.valueOf(candidate.a) + " " + String.valueOf(candidate.b) + " " + String.valueOf(candidate.c)) //Convert to a string
.forEach(output::add);
return output;
}
public static void main(String[] args) {
if (args.length != 3){
System.out.println("Usage: triples.jar <hypotenuse> <precision> (SingleLoop|Parallel)");
System.exit(1);
}
Vector<String> triples;
String hyp = args[0];
String precision = args[1];
String mode = args[2];
BigDecimal arg_hyp = new BigDecimal(hyp);
Integer arg_prec = Integer.valueOf(precision);
switch (mode){
case "SingleLoop":
triples = findTriple(arg_hyp, arg_prec);
System.out.println("Finding pythagorean triples of " + hyp + " with precision " + precision + ". Using basic loop");
break;
case "Parallel" :
triples = findTripleParallelStream(arg_hyp, arg_prec);
System.out.println("Finding pythagorean triples of " + hyp + " with precision " + precision + ". Using parallelStream");
break;
default:
triples = new Vector<>();
}
System.out.println(triples.toString());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment