A simple sieve in Phobos?

[bearophile]

Chris Williams:

> so an isPrime() method is part of that. I think I templated it 
> to accept BigInt or regular ints, but even if not, that should 
> be an easy addition.
>
> I could break out that and a few other basic math 
> functions/algorithms into its own small pull request, if 
> desired?

I suggest a Phobos module named "combinatorics" (or just 
"combs"?). It's not meant to be a complete library of 
combinatorics algorithms, nor to contain the most optimized 
algorithms around. It's meant to be a collection of efficient but 
sufficiently short implementations of the few algorithms/ranges 
you need most often. Everything else, including the most 
efficient code, I my opinion should be left to specialized 
numerical libraries external to Phobos (or could be added later 
if Phobos gains more developers).

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 (Phobos 
already has a permutations, but it's designed on the legacy C++ 
style of functions, so it's not good enough).
(See ER issue 6788 for pairwise. A the moment I can't find my 
Bugzilla ER entry for permutations/combinations, but you can see 
the good API for the permutations/combinations ranges in the code 
I have written here: 
http://rosettacode.org/wiki/Permutations#Fast_Lazy_Version  See 
also the good API of the Python combinations/permutations here: 
http://docs.python.org/3/library/itertools.html#itertools.permutations 
  note also the useful "r" and "repeat" arguments).

With such 7 functions/ranges you can do lot of things :-)

Bye,
bearophile