7
\$\begingroup\$

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<Long> numbers = new ArrayList<Long>() {
            { 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) + ".");
        }

        public static boolean isSmallestMultiple(int n) {
            for (int i = 11; i <= 20; i++) {
                if (n % i != 0) {
                    return false;
                }
            }
            return true;
        }
    }

Example output:

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

  1. Approach 2 is clearly faster, but I'm wondering if givenPrimes qualify as "magic numbers?" Or is the explanation enough (feels tenuous/not 100% certain it would qualify as an effective strategy in a different context).
  2. The first method seems the more understandable/applicable. Am I wrong? Which would you fellow CR folks prefer and why?
\$\endgroup\$
1
6
\$\begingroup\$

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 <= rangeMax; n++) {
            numbers[n - 1] = n;
        }

        long lcm = 1;
        for (int p : PSEUDOPRIMES_BELOW_20) {
            int maxExponent = 0;
            for (int i = 0; i < numbers.length; i++) {
                int exponent;
                for (exponent = 0; numbers[i] % p == 0; exponent++) {
                    numbers[i] /= p;
                }
                maxExponent = Math.max(maxExponent, exponent);
            }

            while (maxExponent --> 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 < numbers.length; i++) {
                int exponent;
                for (exponent = 0; numbers[i] % p == 0; exponent++) {
                    numbers[i] /= p;
                }
                maxExponent = Math.max(maxExponent, exponent);
            }
            return pow(p, maxExponent);
        }).reduce(1, (a, b) -> 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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This was amazingly helpful. I don't consider the second method truly "guessing," since the logic follows, and is applicable I realize I should've made it more methodical and commented in my reasoning. I've done so, in the final iteration: github.com/Javaliant/Challenges/blob/master/Euler5.java But the very last paragraph is site-wide feature worthy; something that I will carry with me for the rest of my programming life. Thank you. \$\endgroup\$ – Legato Jan 9 '15 at 20:05
3
\$\begingroup\$

About the first one: there is no need to create and populate an ArrayList. You can use LongStream.rangeClosed static method instead:

long result = LongStream.rangeClosed(1, MAX_NUM)
        .reduce(Euler5::lcm).getAsLong();

The second one contains a lot of redundant code: 2520 * 2 * 11 * 13 * 17 * 19 is already the answer, it could be just something like
System.out.print(2520 * 2 * 11 * 13 * 17 * 19); instead. So the second one does not compute anything, it just prints the answer, while the first one can be used to find an LCM for different values of MAX_NUM, not just 20.

\$\endgroup\$
1
  • \$\begingroup\$ Wow, I had no idea that already computed the answer. It just made sense to multiply by the primes. It explains why there's such a drastic difference in calculation time. \$\endgroup\$ – Legato Jan 8 '15 at 18:47
-2
\$\begingroup\$

This is my solution, it seems to be a lot faster than the ones above:

    public class LCM {
        public static void main(String[] args) {
        long startTime = System.nanoTime();
        int high = 20;
        long value = 1;
        for (int i = 0; i < high; i++) {
            int j = 1;
            if ((value % (i + 1)) == 0) {
            } else {
                while (value % (i + 1) != 0) {
                    if ((value * j) % (i + 1) == 0) {
                        value *= j;
                    }
                    j++;
                }
            }
        }
        System.out.print("Result: " + value +
                ".\nTime used for calculation in nanoseconds: " +
                (System.nanoTime() - startTime) + ".");
        }
}

It basically will check to see if the value will be divisible by the current number, and if so, will multiply. It's not very clean though, having it all in the main method.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Answers should explain how the original code should be improved, and this doesn't really seem to do that. \$\endgroup\$ – Jamal Oct 13 '15 at 1:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.