A simple sieve in Phobos?

[safety0ff]

On Wednesday, 19 March 2014 at 01:29:16 UTC, bearophile wrote:
>
> I think the most commonly useful functions are:
>
> - A lazy range (a simple unbounded segmented Sieve) that 
> generates primes numbers very quickly, in a given range, or 
> from 2;
> - A isPrime() function. Probably it should cache some of its 
> computations.
>
> - A function to compute the GCD on ulongs/longs/bigints is 
> useful.
> (Issues 4125 and 7102).
>
> - An efficient and as much as possibly overflow-safe 
> binomial(n,k) that returns a single number.
>
> I'd also like permutations/combinations/pairwise ranges [Snip]
>
> With such 7 functions/ranges you can do lot of things :-)
>
> Bye,
> bearophile

I think we need a solid integer math module more than anything on 
this list.
I find myself often reimplementing ilog2, isqrt, isPowerOf2, etc, 
etc.
This would be a complement to std.math, std.bitmanip and 
core.bitop.
GCD and binomial would fit well in here.

I've recently made use of a prime sieve[1] and something similar 
to a pairwise range (triangular range: [0,0],[1,0],[1,1]...)

I think we should be careful about adding an isPrime method, I 
think adding an isProbablePrime plus the prime sieve should cover 
most use cases.

I agree that combination/pairwise ranges are high on my wishlist, 
higher than having GCD/binomial/prime sieve, below having a basic 
integer math module.
One important feature of the pairwise range I wrote was slicing 
which makes parallelising O(N^2) algorithms much easier.

[1] http://dpaste.dzfl.pl/e91ffe7e4609 Based on the code from 
http://create.stephan-brumme.com/eratosthenes/