[prev in list] [next in list] [prev in thread] [next in thread]
List: gmp-discuss
Subject: Digit sum
From: decio () decpp ! net (=?ISO-8859-1?Q?D=E9cio_Luiz_Gazzoni_Filho?=)
Date: 2007-03-25 20:27:54
Message-ID: A7998F00-2AE0-4255-AE1B-1F697B5487BA () decpp ! net
[Download RAW message or body]
-----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-----
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic