Documentation and Structure

[wackywendell]

I've been working on trying to write some additional documentation for this module (here). This module already has great detail on the parts, but I was thinking it would be really nice if it also had something like the std::collections introduction:

To get this out of the way: you should probably just use Vec or HashMap. These two collections cover most use cases for generic data storage and processing.

std::collections has lots of classes for niche cases, but really, if you only ever look at those two, you'll probably be fine.

Similarly, it would be nice if this module had something similar. Primes covers many cases, but not is_prime or factor. I was thinking of perhaps adding two usability features to Sieve: the first a new_with_n function, and the second an iterator over all primes in Sieve (perhaps an iter() function, or maybe just an IntoIterator implementation). That way, the introductory material can direct people to Sieve for any case where they know how many primes they need, or to Primes if not. I've started work on that here, and would like to know what you think.

Another possibility would be to implement an auto-expanding sieve, that can both go on to infinity (like Primes), but also still "remember" enough to be able to factorize numbers or check primality. Is there a way to do that with Sieve and StreamingSieve?

[huonw]

Thanks for looking at this. I'm traveling for the next few days so can't discuss right now, but your ideas do seem reasonable to me.

[wackywendell]

Great! I'll look forward to hearing from you when you return. In the meantime, I'll think about things and maybe submit a "candidate" PR or two as possibilities.

[huonw]

I was thinking of perhaps adding two usability features to Sieve: the first a new_with_n function

Could you clarify what this functionality would do?

the second an iterator over all primes in Sieve (perhaps an iter() function, or maybe just an IntoIterator implementation).

Do you mean all the primes in a specific instance of Sieve?

Another possibility would be to implement an auto-expanding sieve, that can both go on to infinity (like Primes), but also still "remember" enough to be able to factorize numbers or check primality. Is there a way to do that with Sieve and StreamingSieve?

I think this should be possible... I've got some experiments I want to do with Primes, which probably can be converted back to apply to Sieve.

[wackywendell]

Hi! Sorry, on vacation for a bit.

I was thinking of perhaps adding two usability features to Sieve: the first a new_with_n function

Could you clarify what this functionality would do?

new_with_n would be a function that has at least n primes in it. Its a simple wrapper of nth_prime followed by Sieve::new, since I imagine that would be the main use case (note that in my branch I named it new_at_least; I don't have a good name for it).

Do you mean all the primes in a specific instance of Sieve?

Yes, sorry for the lack of clarity!

Another possibility would be to implement an auto-expanding sieve [...]

I think this should be possible... I've got some experiments I want to do with Primes, which probably can be converted back to apply to Sieve.

Hurray! If that's the case, I imagine that would make documentation much easier: people can be recommended to almost always use that "catch all" class, with the underlying Sieve and StreamingSieve classes saved for those who really want to eke out every last drop of performance.

Anyways, I'll submit a PR for the new_at_least branch and my more documentation branch soon.

[huonw]

Hi! Sorry, on vacation for a bit.

Don't apologise: I took 18 days to reply. Hope your vacation is/was great!

new_with_n would be a function that has at least n primes in it. Its a simple wrapper of nth_prime followed by Sieve::new, since I imagine that would be the main use case (note that in my branch I named it new_at_least; I don't have a good name for it).

Oh I see. I like the functionality but I don't like the name as you say. I'll mull on it.

Hurray! If that's the case, I imagine that would make documentation much easier: people can be recommended to almost always use that "catch all" class, with the underlying Sieve and StreamingSieve classes saved for those who really want to eke out every last drop of performance.

I've now published it: basically instead of storing a list of all primes it has generated Primes will progressively sieve more and more of the small primes it needs. I guess a good summary is that it is doing this lazily, while Sieve/StreamingSieve are eager.

I haven't thought how much to fold things together yet, but it seems like there's scope for it.

[huonw]

(I also want to tackle like, generating the primes between like 10¹⁶ and 10¹⁶ + 1000, which is something the technique used in primal works well for, I'm not sure where this will fit in to the overall scheme.)

Anyways, I'll submit a PR for the new_at_least branch and my more documentation branch soon.

Yes please! (Feel free to submit the PR before we've found the best name. :smile: )