Bill Allombert on Thu, 03 Jul 2025 14:51:17 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: flags in a bitmap |
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