Digit sum
Décio Luiz Gazzoni Filho
decio at decpp.net
Sun Mar 25 22:27:54 CEST 2007
-----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-----
More information about the gmp-discuss
mailing list