Re: flags in a bitmap

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

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.

Cheers,
Bill