HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaModerate

Series, Powers, and Benches

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
andseriespowersbenches

Problem

Project Euler problem 48


The series, \$1^1 + 2^2 + 3^3 + ... + 10^{10} = 10405071317\$.


Find the last ten digits of the series, \$1^1 + 2^2 + 3^3 + ... + 1000^{1000}\$.

I made two different implementations of this problem, and added a benchmark, using rolfl's UBench library.

The code:

public class ProjEuler48 {

    private static final int DIGITS = 10;
    private static final BigInteger MOD = BigInteger.TEN.pow(DIGITS);

    public static void main(String[] args) {
        final int max = 1000;
        UBench bench = new UBench(ProjEuler48.class.getSimpleName());
        Predicate predicate = value -> value.longValue() == 9110846700L;
        bench.addTask("Loops", () -> selfPowerSumMod(max, MOD), predicate);
        bench.addTask("Streams", () -> selfPowerSumModStreams(max, MOD), predicate);
        bench.report("RESULTS", bench.press(1000));
    }

    private static BigInteger selfPowerSumModStreams(int max, BigInteger mod) {
        return IntStream.rangeClosed(1, max)
                .parallel()
                .mapToObj(i -> BigInteger.valueOf(i))
                .map(bi -> bi.modPow(bi, MOD))
                .reduce(BigInteger.ZERO, BigInteger::add, BigInteger::add)
                .mod(mod);
    }

    public static BigInteger selfPowerSumMod(int max, BigInteger mod) {
        BigInteger sum = BigInteger.ZERO;
        for (int i = 1; i <= max; i++) {
            sum = sum.add(selfPower(i)).mod(mod);
        }
        return sum;
    }

    public static BigInteger selfPower(int i) {
        BigInteger result = BigInteger.valueOf(i);
        return result.modPow(result, MOD);
    }

}


Benchmark results on my machine:

`RESULTS
=======

Task ProjEuler48 -> Loops: (Unit: MILLISECONDS)
Count : 1000 Average : 2.5267
Fastest : 2.0137 Slowest : 35.8331
95Pctile : 4.2812 99Pctile : 8.3346
TimeBlock : 4.718 2.646 2.801 2.280 2.191 2.128 2.119 2.124 2.132 2.127
Histogram : 936 53 10 0

Solution

This looks pretty good. A few changes I would make:
Performance

10^10, 20^20, and all higher powers will always end in 0000000000, which means they don't affect the sum. You should be able to get an approximately 10% performance improvement by not computing these powers. This would be easy to do in your loops case but would require a little syntactical cleverness in the streams way.
Magic Numbers

You have a magic number 9110846700L in your code. It's not immediately clear what this is, especially if you are unfamiliar with the UBench library. This should be refactored into a magic number constant, in this case. Further reading on this subject
Static methods

Even for a program as simple as this, I would always shy away from putting your business logic in static methods. Obviously, in this case it isn't a problem, but for an application could grow at all, you will quickly regret it. More further reading
Inconsistent method scope

One of your methods is private, the others are public. Again, this issue is not super relevant for such a short program, but allowing encapsulation to be broken starts to matter as soon a program reaches two classes.

Context

StackExchange Code Review Q#83922, answer score: 10

Revisions (0)

No revisions yet.