# Getting all digits from a BigInt

I am trying to collect and then sum all the digits from a BigInt.
Example: sum all digits of 2^1000000

Intuitively, my first solution was using the `digits` function:

``````@time sum(digits(BigInt(2)^1000000))
29.189925 seconds (3.15 M allocations: 50.253 GiB, 6.13% gc time)
1351546
``````

However, I found this to be very inefficient. My second solution is much more efficient but less intuitive (converting a BigInt to a string and then parsing all chars):

``````@time sum(map(x -> parse(Int, x),  collect(string(BigInt(2)^1000000))))
0.062261 seconds (59.30 k allocations: 9.278 MiB, 8.69% gc time)
1351546
``````

I guess that there should be a better way of doing this (e.g. accessing the internal representation of the BigInt)… or the `digits` function is not optimized for BigInt.

Any thoughts?
Thanks!

Julia version 1.0.5 (2019-09-09)

Indeed, the string solution is optimized for `BigInt`, calling out `mpz_get_str`, which is the GMP API to get the digits. But it supports only limited bases.
On the other hand, the Julia `digits` function is generic, but for such a huge bigint as in your example, uses a lot of intermediate bigints for the computation.

A solution could be to make `digits` use `mpz_get_str` when the base is supported (I think such a PR would be accepted).

5 Likes

You can save some memory, and a tiny bit of time and typing by doing

``````sum(parse(Int, c) for c in string(b))
``````

instead of first allocating a string, then a character vector and then an integer array before summing.

2 Likes

If you’re going to do it repeatedly until you get a single digit, this is equivalent to reduction modulo 9.

2 Likes