Re: binary() generalization

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

* Igor Schein [2011-06-02 00:55]:
> I am looking for an efficient generalization of gp's binary() function.
> 
> digits(n,b)=local(m=n,L=List);while(m,v=divrem(m,b);listinsert(L,v[2],1);m=v[1]);
> 
> It's very inefficient compared to the native function:
> 
> ? for(k=10^5,10^6,digits(k,2))
> time = 18,749 ms.
> ? for(k=10^5,10^6,digits(k,10))
> time = 6,401 ms.
> ? for(k=10^5,10^6,binary(k))
> time = 236 ms.
> 
> 
> Can I do better than that?

For conversion to base 10, you can use Str(), which uses DAC to convert from
base 2^64 => 10, in almost linear time. So either of 

(1). Vecsmall(Str(k))

(2). Vec(Str(k))

Unfortunately (1) only gives the ASCII code. But you can retrieve
the corresponding integer by subtracting 48 (= '0'), as in C.

Unfortunately (2), only gives the individual caracters as t_STR. You can
retrieve the corresponding integer using eval(), but this will be slooow.

Here are some suggestions, the complexity of all following functions should be
O( M(log k) ), where M(n) is the time needed to multiply two n-bit numbers, and
is softly linear in n.

digits1(k) = my(v=Vecsmall(Str(k))); vector(#v, i, v[i] - 48)

\\ unfortunately, eval() doesn't allow t_VECSMALLs
digits2(k)=apply(x->eval(x)-48, Vec(Str(k)))
 
digits3(k)=apply(x->x-48, Vec(Vecsmall(Str(k))))

(09:45) gp > for(k=10^5,10^6,digits(k,10))
time = 3,660 ms.

(09:46) gp > for(k=10^5,10^6,digits1(k))
time = 1,293 ms.

(09:46) gp > for(k=10^5,10^6,digits2(k))
time = 3,692 ms.

(09:46) gp > for(k=10^5,10^6,digits3(k))
time = 1,152 ms.

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/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`