Getting all digits from a BigInt

General Usage Performance
1

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)

2

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
3

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
4

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

3 Likes