patternjavaModerate
Series, Powers, and Benches
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:
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
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
Magic Numbers
You have a magic number
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
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 subjectStatic 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.