Project Euler #5 (LCM 1 - 20) Follow up

I'm actually spending time on it, unlike the first time and going through, understanding and implementing the several suggestions I've landed on two different approaches.

Approach 1: Employing Java 8 Lambdas and stream functions made to be the equivalent of David Zheng's answer in Python.

import java.util.ArrayList;

public class Euler5 {
    public static void main(String[] args) {
        long startTime = System.nanoTime();
        final long MAX_NUM = 20L;

        ArrayList numbers = new ArrayList() {
            { for (long i = 1L; i <= MAX_NUM; i++) { add(i); } }
        };

        long result = numbers
            .stream().reduce(Euler5::lcm).get();

        System.out.print("Result: " + result +
                ".\nTime used for calculation in nanoseconds: " +
                (System.nanoTime() - startTime) + ".");
    }

    /*Greatest Common Divisor
    Euclidean algorithm: http://en.wikipedia.org/wiki/Euclidean_algorithm */
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b); 
    }
    // Least Common Multiple
    public static long lcm(long a, long b) {
        return (a * b) / gcd(a, b);
    }
}

Sample output:


Result: 232792560.
Time used for calculation in nanoseconds: 111370744.

Approach 2: More similar to my original method, using several suggestions, including one in the OP's comment section which I'm unsure about.

```
public class Euler5 {
public static void main(String[] args) {
long startTime = System.nanoTime();
// Multiplying by primes for a starting point * 2 for evenness
int givenTimesPrimes = 2520 2 11 13 17 * 19,
result = givenTimesPrimes;

while (!isSmallestMultiple(result)) {
result += givenTimesPrimes;
}

System.out.print("Result: " + result +
".\nTime used for calculation in nanoseconds: " +
(System.nanoTime() - startTime) + ".");

This Project Euler question is an excellent one to think about computational efficiency of algorithms. It's a horrible place to make decisions based on benchmarks, though.

Sure, your second method is faster. But you're basically cheating with the magic number 2520. It's not a particularly insightful implementation for mathematical learning, either, as it's guessing rather than computing.

To illustrate what I mean, let's consider two more implementations.

"Fast and Crappy"

This algorithm computes the LCM of \$\mathrm{numbers}_i\$ based on the principle that

$$ \mathrm{LCM}(a, b) = \prod p_j^{\max(e_{j,a}, e_{j,b})} $$

when numbers are factorized as \$a = \prod p_j^{e_{j,a}}\$ and \$b = \prod p_j^{e_{j,b}}\$.


Why do I call it "crappy"? Because it is using the same strategy as this nice-looking Ruby code, but it would take a lot of work to make it look as good in Java.

require 'prime'

lcm_factors = Hash.new(0) # Default entry is 0
(1..20).each do |n|
Prime.prime_division(n).each do |factor|
prime, exponent = *factor
lcm_factors[prime] = [lcm_factors[prime], exponent].max
end
end
puts lcm_factors.map { |prime, max_exponent| prime ** max_exponent }
.inject(:*)


public class FastCrappyEuler5 {
    private static final int[] PSEUDOPRIMES_BELOW_20 = new int[] {
        2, 3, 5, 7, 11, 13, 17, 19
        // 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
    };

    public static long lcmOfNumbersUpTo(int rangeMax) {
        if (rangeMax > 20) {
            throw new IllegalArgumentException("TODO: FIXME");
        }

        int[] numbers = new int[rangeMax];
        for (int n = 1; n  0) {
                lcm *= p;
            }
        }

        return lcm;
    }

    public static void main(String[] args) {
        long start = System.nanoTime();
        System.out.println(lcmOfNumbersUpTo(20));
        System.err.println(System.nanoTime() - start);
    }
}

This takes about 6 times as long as your fast implementation. (For me, it's on the order of ~105 nanoseconds.) I've taken a shortcut of hard-coding the primes below 20 — a "fair" move, I think, as most people know them by heart.

If you replace the pseudoprimes list with a list of all integers from 2 to 20, you get the same answer, with no significant difference in running time.

Using streams

This implements exactly the same algorithm as FastCrappyEuler5, but does so using Java 8 streams to be more elegant.

import java.util.stream.IntStream;
import java.util.stream.LongStream;

public class StreamsEuler5 {
    private static LongStream pseudoPrimesBelow(int max) {
        // We should be more selective, but as we saw above,
        // it shouldn't make much difference.
        return LongStream.range(2, max);
    }

    private static long pow(long base, /* unsigned */ int exponent) {
        long power = 1;
        while (exponent --> 0) {
            power *= base;
        }
        return power;
    }

    public static long lcmOfNumbersUpTo(int rangeMax) {
        final int[] numbers = IntStream.rangeClosed(1, rangeMax).toArray();

        // Warning: computation is not parallelizable
        return pseudoPrimesBelow(rangeMax).map((p) -> {
            int maxExponent = 0;
            for (int i = 0; i  a * b);
    }

    public static void main(String[] args) {
        long start = System.nanoTime();
        System.out.println(lcmOfNumbersUpTo(20));
        System.err.println(System.nanoTime() - start);
    }
}

Unfortunately, it's two orders of magnitude slower! (For me, it's on the order of 5 ⨉ 107 nanoseconds.)

Conclusion

$$\begin{array}{l|r}
\textrm{Implementation} & \textrm{Approx. running time} \\
\hline
\textrm{Legato's streams} & 1 \times 10^8 \mathrm{ns} \\
\textrm{Legato's cheat-and-guess} & 5 \times 10^4 \mathrm{ns} \\
\textrm{200_success's fast-and-crappy} & 1 \times 10^5 \mathrm{ns} \\
\textrm{200_success's streams} & 5 \times 10^7 \mathrm{ns} \\
\end{array}$$

Are the streams-based implementations worse because they are slower? I don't think so. The overhead of the streams seems to dwarf everything else. But I don't mind waiting a few million nanoseconds if it means that I like the code better. My streams-based solution is the same algorithm as "Fast and Crappy", so the complexity must be the same. Presumably, the startup costs would be inconsequential for larger problems.

Basically, do the "right thing" for readability, maintainability, and educational value. Time measurements mean nothing when you haven't taken scalability into account. Worry about speed when it's noticeably slow.

StackExchange Code Review Q#76996, answer score: 6