Re: flags in a bitmap

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

Bill, many thanks for the pointers, I'll explore.


As an alternative, maybe add a Vecbits() or Vecflags() or such.
No idea if the first bit should have offset 0 or 1.
Only with bittest(), maybe 0?

my(B=Vecbits([0], 987654321));
Vecbits_put(~B, 7654, v=1);  \\set the bit at offset 7654, by default to 1
Vecbits_put(~B, 7654, [1,0,0,1,1]); \\set bits 7654..7658 to [1,0,0,1,1]
my(b=Vecbits_get(B,7654)); \\get bit-7654
my(b=bittest(B,7653)); \\...

-- Ruud


On 2025-07-03 14:51, Bill Allombert wrote:
> On Thu, Jul 03, 2025 at 11:11:50AM +0200, Ruud H.G. van Tol wrote:
> > For OEIS:A005282 I wrote this "clean" code:
> >
> > aupto1(L)= {
> >    my(S=vector(L), A=[1]);
> >    for(i=2, L
> >    , for(j=1, #A
> >      , if(S[i-A[j]], next(2))
> >      );
> >      for(j=1, #A
> >      , S[i-A[j]]=1
> >      );
> >      A=concat(A, i)
> >    );
> >    A
> > }
> >
> > So S is a "seen" array.
> >
> > I could also use an integer and then bitand and bitor:
> >
> > aupto2(L)= {
> >    my(S=0, A=[1]);
> >    for(i=2, L
> >    , for(j=1, #A
> >      , if(bitand(S, 1<<(i-A[j]-1)), next(2))
> >      );
> >      for(j=1, #A
> >      , S=bitor(S, 1<<(i-A[j]-1))  \\or: S+= 1<<(i-A[j]-1)
> >      );
> >      A=concat(A, i)
> >    );
> >    A
> > }
> >
> > but that is (much) slower.
> >
> >
> > There are of course multiple ways to improve this code.
> > For example S=Vecsmall(0,L) uses less memory and is marginally faster.
> In GP this is the best you can do, except that you can store several bit by
> entries.
>
> alloc (n)=vectorsmall(n\32+1);
> set(~V,i)=my([q,r]=divrem(i,32));V[1+q]=bitor(V[1+q],1<<r);
> coeff(~V,i)=my(q=i>>32,r=bitand(i,31));!!bitand(V[1+q],1<<r);
> N=2^20;
> V=alloc(N);
> forprime(p=2,N,set(~V,p))
> my(S=0);for(i=1,N,S+=coeff(~V,i));S
>
> > I think a big win would be to have a (dynamic? sparse?) byte-buffer with
> > addressable bits.
> > Is there already a fast implementation of such somewhere?
> In libpari, yes! In GP you can do
>
> install(zero_F2v,L)
> install(F2v_set,vWL)
> install(F2v_clear,vWL)
> install(F2v_coeff,lGL)
>
> N=2^20;
> V=zero_F2v(N);
> forprime(p=2,N,F2v_set(~V,p))
> my(S=0);for(i=1,N,S+=F2v_coeff(V,i));
>
> But even so it will be much slower than directly in C.