Digit sum

[Edwin Klement]

Hello,

I'm very interesting in number theory. Therefore I found GMP
very useful for calculation using large numbers.

Now I found a way to calculate the digit sum (sometimes called
also digit root) for a given large number in a small amount of
time. For example a given number 632 will result in 6+3+2=11
and finally in 1+1=2.
I tried it with number like 10^10000000 and my small SUN workstion
with 200 MHz did the calculation in a few second.

Here is the C-code for the calculation using GMP library.
Hopefully it is useful and you will include it in the next GMP version.

int mpz_digitsum(mpz_t q)
{
          mp_limb_t limb;
          int result;
          int i;
          int j;
          int qtab[] = {1, 2, 4, 8, 7, 5};
          int qind;
          int qsiz = sizeof(qtab) / sizeof(qtab[0]);
          int sizeoflimb = GMP_NUMB_BITS;

          result = 0;
          qind = 0;
          if (mpz_sgn(q) <= 0) return(0);
          for (i = 0; i < q->_mp_size; i++)
          {
                  limb = q->_mp_d[i];
                  for (j = 0; j < sizeoflimb; j++)
                  {
                          if (limb & 1)
                          {
                                  result = result + qtab[qind];
                                  while (result >= 10) result = 1 + result %
10;
                          }
                          qind = (qind + 1) % qsiz;
                          limb >>= 1;
                  }
          }
          return(result);
}

Regards,

Edwin Klement