Project Euler #16 - Sum of all digits of 2^1000

Question

2^15 = 32768 and the sum of its digits is 3 +たす 2 +たす 7 +たす 6 +たす 8 =わ 26.

What is the sum of the digits of the number 2^1000?

 BigInteger big = new BigInteger("2");
 big = big.pow(1000);
 String num = big.toString();
 System.out.println(num);
 int result = 0;
 for(char i : num.toCharArray()) {
 result += Integer.parseInt(String.valueOf(i));
 }
 System.out.println(result);

• ShapeOfMatter: What kind of feedback are you looking for? Is there anything about the code you've posted that you're not satisfied with?
• Omar_Hafez: yes, I feel that there is a better way. instead of converting BigInteger to string and then to charArray and again I return it to int
• TorbenPutkonen: Use Character.getNumericalValue(char) instead of Integer.parseInt(String.valueOf(i)).
• Omar_Hafez: @TorbenPutkonen yeah it's more clear. thanks a lot.

Answer 1

This looks good. I assume this results in correct answer.

• What you can use instead of converting to String and back to int is to use divideAndRemainder method with 10 since we need to treat this as a base 10 number.
• This method is available in BigInteger for situations like this.
• We can also directly use BigInteger constants such as TWO and TEN.

---

Alternative Implementation

BigInteger big = BigInteger.TWO.pow(1000);
String num = big.toString();
System.out.println(num);
int result = 0;
BigInteger[] components;
components = big.divideAndRemainder(BigInteger.TEN);
while (components[0].signum() != 0) {
 result += components[1].intValue();
 components = components[0].divideAndRemainder(BigInteger.TEN);
}
result += components[1].intValue();
System.out.println(result);

• _{I've used signum method here to check if result after integer division is zero.}
• _{Note: This seems to be creating lot of objects.}

---

Benchmark with JMH

After the some discussion in comments with @TorbenPutkonen, I agreed with TorbenPutkonen that alternative implementation might be creating more objects. However there is no way to see which implementation performs faster without doing a benchmark.

public class X {
 public static void main(String[] a) throws Exception {
 org.openjdk.jmh.Main.main(a);
 }
 @State(Scope.Benchmark)
 public static class BenchmarkState {
 BigInteger multiple = BigInteger.TWO.pow(1000);
 public BenchmarkState() {
 System.out.println(multiple);
 }
 }
 @Benchmark
 @Warmup(iterations = 5)
 public int withDivide(BenchmarkState x) {
 BigInteger[] components;
 components = x.multiple.divideAndRemainder(BigInteger.TEN);
 int result = 0;
 while (components[0].signum() != 0) {
 result += components[1].intValue();
 components = components[0].divideAndRemainder(BigInteger.TEN);
 }
 result += components[1].intValue();
 return result;
 }
 @Benchmark
 @Warmup(iterations = 5)
 public int withChars(BenchmarkState x) {
 String num = x.multiple.toString();
 int result = 0;
 for(char i : num.toCharArray()) {
 result += Integer.parseInt(String.valueOf(i));
 }
 return result;
 }
 @Benchmark
 @Warmup(iterations = 5)
 public int withCharsNumerical(BenchmarkState x) {
 String num = x.multiple.toString();
 int result = 0;
 for(char i : num.toCharArray()) {
 result += Character.getNumericValue(i);
 }
 return result;
 }
 @Benchmark
 @Warmup(iterations = 5)
 public int withCharAt(BenchmarkState x) {
 String num = x.multiple.toString();
 int len = num.length();
 int result = 0;
 for(int i = 0; i < len; i++) {
 result += Integer.parseInt(String.valueOf(num.charAt(i)));
 }
 return result;
 }
 @Benchmark
 @Warmup(iterations = 5)
 public int withCharsNumericalCharAt(BenchmarkState x) {
 String num = x.multiple.toString();
 int len = num.length();
 int result = 0;
 for(int i = 0; i < len; i++) {
 result += Character.getNumericValue(num.charAt(i));
 }
 return result;
 }
}

# Run complete. Total time: 00:21:29
Benchmark Mode Cnt Score Error Units
X.withCharAt thrpt 200 117285.320 ± 644.505 ops/s
X.withChars thrpt 200 116882.706 ± 779.233 ops/s
X.withCharsNumerical thrpt 200 110849.659 ± 3901.095 ops/s
X.withCharsNumericalCharAt thrpt 200 121480.705 ± 2040.597 ops/s
X.withDivide thrpt 200 11306.787 ± 35.711 ops/s

• This concludes that original version is roughly 10x faster than divideAndRemainder
• Original version is also slightly faster than using getNumericValue by itself.
• However we can use charAt and avoid creating a character array too.

---

Why is using divideAndRemainder slow?

• toString method of BigInteger uses a faster algorithm to create the string representation.
• divideAndRemainder creates lot of BigInteger objects.

• JaDogg: @OmarAhmed Updated my answer with code. Also if you want to it would be more fun to write the BigInt yourself ;)
• TorbenPutkonen: Looking quickly at the code in divideAndRemainder I'd say this approach results in about 2000 or more unnecessary object creations. Despite toString().toCharArray() creating an unnecessary array I would bet that it'd be much more efficient to do it char by char.
• JaDogg: @TorbenPutkonen doesn't Integer.parseInt(String.valueOf(i)) create temporary objects too? This avoids string conversion all together (except for printing). However I'm now curious to run a benchmark and see. 🤔
• TorbenPutkonen: @bhathiya-perera Character.getNumericValue(char) does it without creating an Integer object. Benchmarking with 300 digit number is probably not going to show much difference, though. My point is that divideAndRemainder is more costly than it appears on the surface and that should be taken into account if performance is being thrown around.
• JaDogg: @TorbenPutkonen I've updated the answer with a benchmark. Seems like you are correct. Good catch. :)