Generating Pythagorean triples below an upper bound

Question

I've got an assigment where I have to print all the Pythagorean triples smaller than a given n. Even though I could print them directly in pythagoreanTriple function, I decided to structure everything, as I want to go deply into programming structure.(my teacher does not teach us a lot, so I'll have to study on my own).

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        System.out.println("Starting program...");
        int n = readFromKeyboard();
        printResult(pythagoreanTriple(n));
    }

    private static int  readFromKeyboard(){
        Scanner keybInput = new Scanner(System.in);
        return keybInput.nextInt();
    }

    private static List<List<Integer>> pythagoreanTriple(int n){
        List<List<Integer>> pytTri = new ArrayList<List<Integer>>();
        int i,j,k;
        for (i = 3; i < n; i++)
            for (j = n; j > i; j--)
                for (k = n; k > j; k--)
                    if (i * i + j * j == k * k){
                        ArrayList<Integer> tempArray = new ArrayList<Integer>(); //we create a list of integers
                        tempArray.add(i);
                        tempArray.add(j);
                        tempArray.add(k);
                        pytTri.add(tempArray);
                    }
        return pytTri;
    }

    private static void printResult(List<List<Integer>> resultList){
        for (List<Integer> ls: resultList){
            for (Integer i: ls){
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println(";");
        }
    }

}

Knowing these:

I am curious about the following: How are the variable/function's name, should I use underscore _ for private variables etc... I am not new to programming

(I know both C++ and Python so far), but I'm more interested in learning Java next.)

Answer 1

It's a good thing that there is a method to calculate the pythagorean triple up to a number, and then a second method to print the results.

About pythagoreanTriple

You can simply the pythagoreanTriple method in several aspects. First of all is performance. The current code does:

for (i = 3; i < n; i++)
    for (j = n; j > i; j--)
        for (k = n; k > j; k--)
            if (i * i + j * j == k * k) {

to check for triplets. This tries every possible combinations of i, j and k and checks if they form a triplet. However, you don't need to loop for every possible k: once you know i and j, you can deduce the only possible k for which (i,j,k) forms a triplet; it is exactly \$k = \sqrt{i^2+j^2}\$, when this result in an integer. Take care because such a calculation can lead to rounding issues, and there are good way to check if a number square root is an integer. I won't comment more on the performance, because if this is really a concern, there are other faster approaches than trying every possible combinations (see for example the Tree of primitive Pythagorean triples).

Second aspect, is the usage of built-in methods.

ArrayList<Integer> tempArray = new ArrayList<>();
tempArray.add(i);
tempArray.add(j);
tempArray.add(k);
pytTri.add(tempArray);

can be written more simply using the built-in Arrays.asList. You can directly have:

pytTri.add(Arrays.asList(i, j, k));

without creating any new ArrayList yourself.

Finally, even if it isn't strictly necessary, consider adding curly braces everywhere.

for (i = 3; i < n; i++)
    for (j = n; j > i; j--)

can quickly lead to problems if you want to add another statement in there, like storing the result of i * i as recommented by coderodde in their answer.

About readFromKeyboard

Currently, the code to retrieve the user input does not validate that only integers can be input. If you try to input a String like "a", an exception will be thrown; consider re-prompting for an input if that happens.

Also, this method creates a new Scanner. In the current code, it is called only once, but if later you want to read a second input from the user, it would be better to create it only once and reuse it. As such, consider creating the Scanner and passing it as parameter of readFromKeyboard.

This also has a direct impact: readFromKeyboard would not read from the keyboard anymore, it would read from a given Scanner, which makes it more reusable, since you could pass any instance of Scanner you want (for example, one reading from a file). And the method should renamed to something like readUpperBound, which makes it clear that its concern is not to read from the keyboard (which is the current technical implementation), but to fetch the upper bound to use in order to create the triplets (which is what it's really supposed to do).

Answer 2

I want to take this opportunity to constructively criticize coderodde's answer and point out some very important lessons about microbenchmarking.

As you know, Java is a hybrid between being compiled and interpreted: javac compiles your source files down to bytecode, and then the Java Virtual Machine (java) executes this bytecode, either by interpreting it or compiling it "just in time" (i.e., right before it runs).

The javac compilation process does essentially no optimization; this is by design. Rather, optimization is performed by the JVM at runtime. As your code runs, the JVM determines the "hot spots," and optimizes them as best it can. Consequently, your code's performance improves over time within a single run of the program.

Whenever you are profiling a Java program, then, there are a few critical steps you must follow:

1. "Warm up the JVM," by running your code a few times so that the JVM can begin to identify the hot spots.
2. Run both versions of your code, timing a segment that takes at least a full second to run. (Otherwise, there is too much noise.)
3. Collect the results and compare the timing data from after the JVM warmup.

The microbenchmark provided by coderodde properly handles step (2), which many people forget: the runtime of ten or more seconds is a good window to test. But this benchmark neglects to handle the JVM warmup phase. At best, it is timing the unoptimized versions of each algorithm; at worst, the second algorithm timed is benefitting partially due to the JVM having warmed up on the first one and identified similar patterns.

Here's a better driver. I'll paste in the results below:

        Runtimes (ms)
Trial   Normal  Cached  Equal?
0       10450   9418    true
1       10459   9391    true
2       2242    2194    true
3       2231    2179    true
4       2230    2185    true
5       2233    2209    true
6       2236    2186    true
7       2236    2174    true
8       2237    2189    true
9       2258    2174    true
10      2239    2196    true
11      2240    2194    true
12      2219    2218    true
13      2245    2194    true
14      2246    2195    true
15      2246    2203    true
Normal: 52247ms
Cached: 49499ms

You can see that something magical happens after the second trial: the runtime of both algorithms improves by a factor of 4–5. This is where the JVM optimization has kicked in! After this point, the differences between the two algorithms are negligible. In this particular run, the cached version always seems to do between 0.05% and 4% better than the original version; on other runs, the opposite is true.

Finally, microbenchmarks inherently have problems of their own: the performance of an algorithm in a microbenchmark may not reflect that algorithm's performance in a larger application.

For example, suppose you have two algorithms for calculating trigonometric functions: one uses Taylor series, and the other uses lookup tables. You write a microbenchmark, following all best practices, and the lookup table algorithm wins, hands down. But you start using it in your application and your performance drops by a factor of six. What happened? In the microbenchmark, the lookup table for the function was stored in cache; in the real application, there was more contention on the cache, leading to more cache misses and poorer performance overall.

One moral of the story is that you should always be exceptionally careful while profiling and optimizing, testing carefully at every step that your optimizations are not actually pessimizations.

Another moral, though, is to be skeptical of any "optimization" as simple as caching a scalar value, or reusing a variable: these are precisely the kinds of things that compilers (and run-time optimizers) are good at. It is most important to write code that is simple, clear, and uses efficient algorithms; the compiler will figure out the details of the performance.

---

In terms of the rest of your code:

• I second coderodde's suggestion to use the "diamond operator" for clarity.
• You should also remove the comment that says "we create a list of integers"—yes, that's what new ArrayList<Integer> means.
• In terms of organization, I would have created a three-field class PythagoreanTriple instead of using a List<Integer>; this clarifies the intent from the type and makes it more difficult to do something wrong, like including an empty list.
• No, you should not prefix private variables with underscores.

Overall, it's good, and pretty Java-like. Well done.

Answer 3

Your code is well written. Plus, you did the right job separating the algorithm from the output code, as it should be. However, I have a couple of advices:

Advice 1

List<List<Integer>> pytTri = new ArrayList<List<Integer>>();

Since Java 7, you can do diamond inference:

List<List<Integer>> pytTri = new ArrayList<>();

Advice 2

ArrayList<Integer> tempArray = new ArrayList<Integer>();

You can optimize the memory consuption of the ArrayList by passing the required capacity to its constructor:

List<Integer> tempArray = new ArrayList<>(3);

Optimizing the code

private static List<List<Integer>> pythagoreanTriple2(int n) {
    List<List<Integer>> pytTri = new ArrayList<>();

    for (int i = 3; i < n; i++) {
        int iSquared = i * i;

        for (int j = n; j > i; j--) {
            int iSquaredPlusJSquared = iSquared + j * j;

            for (int k = n; k > j; k--) {
                if (iSquaredPlusJSquared == k * k) {
                    List<Integer> result = new ArrayList<>(3);
                    result.add(i);
                    result.add(j);
                    result.add(k);
                    pytTri.add(result);
                }
            }
        }
    }

    return pytTri;
}

For example for n == 3000, the performance figures are:

Starting program...
3000
pythagoreanTriple(3000) in 16222.3 milliseconds.
pythagoreanTriple2(3000) in 10866.9 milliseconds.
Algorithms agree: true

The performance gain stems from the fact that your implementation computes i * i + j * j at every iteration of over k when it is not quite necessary. The downside is that the more efficient implementation does not look as concise as yours.

(Also, you can find the entire demo program here.)

Hope that helps.