Re: binary() generalization

[Charles Greathouse <charles.greathouse@case.edu>]

I don't expect there's an efficient way to do this in GP.

First, there's no reason to expect that non-powers of two can ever be
efficient since the internal PARI representation is binary.  Second,
fast solutions will probably require access to low-level functions,
requiring library programming.

Binary splitting is one 'obvious' improvement: split the number into
halves of approximately equal size and recurse.  Then beyond a certain
threshold you can use precalculated tables (for small b, say b <= 100)
to compute multiple digits at a time.

For large numbers, I think GMP has efficient functions for this
purpose (with base-10 specializations).

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Wed, Jun 1, 2011 at 6:48 PM, Igor Schein <igorschein@gmail.com> wrote:
> Hi,
> 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?
> Thanks
> Igor
>
>