Re: Datatypes for sieve algorithms

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

On Sat, Mar 24, 2018 at 10:49:00PM +0000, Jacques Gélinas wrote:
> { The algorithm in question is the sieve of S.P. Sundaram, an Indian 
>   mathematician who discovered it in 1934. It is proven correct
>   in http://en.wikipedia.org/wiki/Sieve_of_Sundaram }
> 
> Still, the sieve implementation in PARI/GP raises some
> questions for me, particularly concerning memory. 
> While PARI/GP only needs 16MB for 1,048,576 primes,
> 
> NP = 2^20;
> GP = primes_zv(NP);
> 
> the working vector P has 8,501,423 elements
> and the stack now grows to 128MB. 
> 
> N = (GP[NP]-1)/2;
> P = vectorsmall(N,n,2*n+1);
> 
> However, only one bit per integer is in fact needed to test 
> the Sundaram algorithm, which means only ~1MB.
> The sieve operations should involve offset calculations
> and bitset/bittest operations only.
> 
> my(l=1,m); for(k=1,(N-1)/3, l+=2; m=k; for(j=1,(N-k)/l, m+=l; P[m] = 0 ));
> MP = N + 1 - vecsum(apply(n->!n,Vec(P))); \\ 256MB !!!

you can replace this line by 
MP = N + 1 - sum(i=1,#P,!P[i]);
to save memory.

if you want to save more, then you can pack 64 bit in each vecsmall
components by using bitand/bitor/bittest, but at this point it is
simpler to write the code in C.

Cheers,
Bill.