Digit sum

[Décio Luiz Gazzoni Filho]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


On Mar 25, 2007, at 3:22 PM, Edwin Klement wrote:

> 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);
> }

I've written a version that's a bit shorter:

int mpz_digitsum(mpz_t q)
{
	return mpz_fdiv_ui(q, 9);
}

It's also slightly faster. Using your benchmark of 10^10000000, your  
code took 555 ms to complete on my machine, whereas my code took 31.6  
ms on the same machine (MacBook Pro with a Core Duo 2.16 GHz CPU). I  
also have a version that's even faster for the particular case of  
10^10000000 and other powers; it clocks at 0.15 ms for your  
benchmark. Unfortunately I have a patent pending on this novel  
algorithm and I can't reveal it.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Darwin)

iD8DBQFGBttO9zcAVrR+ETURAn3HAJ9c0Pt7B0EJGaD2iAiio90CtNF2qACbB9kM
K6xmdHkm++s74iqJznGMaBk=
=AjYl
-----END PGP SIGNATURE-----