Digit sum
Edwin Klement
edwin.klement at netsurf.de
Sun Mar 25 20:22:23 CEST 2007
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
More information about the gmp-discuss
mailing list