Double factorial and primorial

[bodrato at mail.dm.unipi.it]

Ciao,

Il Mar, 20 Dicembre 2011 12:23 pm, Torbjorn Granlund ha scritto:

> I agree we want a shared prime sieve, at least for internal use.
> It would be nice not to have two (as today).
>
> Perhaps it makes sense to have two, but then we should have a clear
> idea why both are really needed.

I can answer to the question: "Why did you write a second prime sieve?"

Basically, I needed a sieve allowing to repeatedly iterate on intervals,
with an "a priori" upper bound. I.e. sub-intervals of ]1,n].
In practice, to compute n! I need to iterate on primes in ]2,n/3] and in
]n/2,n], then by recursion in ]2,n/6] and ]n/4,n/2], then ...

That's why I decided to write a sieve storing its results in a compact
format: each byte covers a range of 24 natural numbers (one bit for each
number = +/-1 (mod 6), to iterate on primes).


Can this sieve fit the needs addressed by the previous one? It can be
generated block by block, to save memory, as the previous one does...

... but, when sieving the [x,y] interval, it needs a memory area where the
sieve on [5,sqrt(y)] is stored. This is not easy to reserve (and
pre-sieve) if we don't know a bound on y, and current code does not give
any.
With y <= 2^32, the bitmap needed by [5,2^16] fits in 3Kb, or it can be
extended on the fly when needed...

> As to a public interface, I am more hesitant, but vote me down if
> you feel the need.

It is hard to decide what a public interface should give as a result:
a list of primes? a bit-by-bit representation of the characteristic
function of primes? A couple of functions: init_prime_iterator,
get_next_prime? always starting from 2 or from an arbitrary offset?
iterating on UI? on limbs? on mpz_t? a third function to skip some primes
or to jump to a new offset?



-- 
http://bodrato.it/software/