I have found two ways in which I can generate the Collatz sequence given a start number. I have looked briefly into their performance, but I'd like a more in depth/solid review into the difference in the two methods.
The main difference really is, one of them doesn't have if statements. But the down side to this method is there's a fair bit of math involved, which is where I'm concerned with performance.
The main questions I have are:
- Do computers get slower when they have to make (slightly) complex calculations?
- Do if statements actually have a significant affect on performance?
- If we were generating the numbers in the Collatz sequence for large numbers (for example numbers > 1,000,000,000), would the performance difference actually be noticeable?
Here are the two methods I have created:
private static ArrayList<Integer> generateCollatz1(int n) {
ArrayList<Integer> results = new ArrayList<>();
while(n != 1) {
if(n % 2 == 0) {
n = n / 2;
results.add(n);
}else {
n = ((n * 3) + 1);
results.add(n);
}
}
return results;
}
private static ArrayList<Integer> generateCollatz2(int n) {
ArrayList<Integer> results = new ArrayList<>();
while(n != 1) {
n = (int) ( (7 * n + 2) - (Math.pow(-1, n)) * (5 * n + 2) ) / 4;
results.add(n);
}
return results;
}
The math in the second method (generateCollatz2
) is using the following formula:
$$ f(n) = \frac{7n + 2 - (-1)^n (5n + 2)}{4}$$