Re: reverse of digits()

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Bill Allombert [2013-12-04 00:03]:
> On Tue, Dec 03, 2013 at 05:40:21PM -0500, Charles Greathouse wrote:
> > I see convi here:
> > 
> > GEN
> > sumdigits(GEN n)
> > {
> >   pari_sp av = avma;
> >   ulong s, *res;
> >   long l;
> > 
> >   if (typ(n) != t_INT) pari_err_TYPE("sumdigits", n);
> >   l = lgefint(n);
> >   switch(l)
> >   {
> >     case 2: return gen_0;
> >     case 3: return utoipos(sumdigitsu(n[2]));
> >   }
> >   res = convi(n, &l);
> > 
> > in the git HEAD.
> 
> Then it is worse than what I imagined: the only reason sumdigits
> is faster than digits is that it use convi which use mpn_get_str
> which only works for basis <=256.

Nope, this is independent of GMP. Using Configure --kernel=none
(portable C kernel, no GMP) :

  gp> test(f,N)=for(i=N+1,N+10^6,f(i));

  gp> test(digits,    0)
  time = 556 ms.
  gp> test(digits,    10^20)
  time = 1,417 ms.
  gp> test(digits,    10^100)
  time = 5283 ms.

  gp> test(sumdigits, 0)
  time = 72 ms.
  gp> test(sumdigits, 10^20)
  time = 252 ms.
  gp> test(sumdigits, 10^100)
  time = 1200 ms.

Same pattern with Configure --kernel=auto-none
(here x86-64 kernel, no GMP)

  gp> test(digits,    0)
  time = 536 ms.
  gp> test(digits,    10^20)
  time = 1,324 ms.
  gp> test(digits,    10^100)
  time = 4810 ms.
  gp> test(digits,    10^1000)
  time = 47,271 ms

  gp> test(sumdigits, 0)
  time = 64 ms.
  gp> test(sumdigits, 10^20)
  time = 248 ms.
  gp> test(sumdigits, 10^100)
  time = 1040 ms.
  gp> test(sumdigits, 10^1000)
  time = 11,598 ms.


The main reason for the difference is that convi / sumdigits get out of the
DAC recursion sooner (writing in base 10^9 first instead of base 10 directly,
then handling blocks of 9 digits).

> However, what is the purpose of sumdigits ?

It's frequently encountered in elementary number theory, was requested a few
times, and is not obvious to get right (= fast) in pure GP script (and even C).

I'll add an optional argument to cater for an arbitrary basis in
sumdigits one of these days...

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`