Charles Greathouse on Thu, 02 Jun 2011 01:36:02 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: binary() generalization |
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 > >