www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - A simple sieve in Phobos?

reply "bearophile" <bearophileHUGS lycos.com> writes:
There is a efficient Sieve implementation in C++ here:

http://code.activestate.com/recipes/577966-even-faster-prime-generator/?in=lang-cpp

There are of course far faster implementations, but its 
performance is not bad, while being still simple and quite short.

A D implementation (it's not a final version because the global 
enums should be removed and replaced with run-time variables or 
template arguments. And something different from just counting 
must be added):


import std.stdio, std.algorithm, std.typecons;

enum uint MAX_N = 1_000_000_000U;
enum uint RT_MAX_N = 32_000; // square of max prime under this 
limit should exceed MAX_N.
enum uint B_SIZE = 20_000;   // not sure what optimal value for 
this is;
                              // currently must avoid overflow 
when squared.

// mod 30, (odd) primes have remainders 1,7,11,13,17,19,23,29.
// e.g. start with mark[B_SIZE/30]
// and offset[] = {1, 7, 11, ...}
// then mark[i] corresponds to 30 * (i / 8) + b - 1 + offset[i % 
8].
Tuple!(uint, size_t, uint) calcPrimes() pure nothrow {
     // Assumes p, b odd and p * p won't overflow.
     static void crossOut(in uint p, in uint b, bool[] mark)
     pure nothrow {
         uint si = (p - (b % p)) % p;
         if (si & 1)
             si += p;
         if (p ^^ 2 > b)
             si = si.max(p ^^ 2 - b);

         for (uint i = si / 2; i < B_SIZE / 2; i += p)
             mark[i] = true;
     }

     uint pCount = 1; uint lastP = 2;
     // Do something with first prime (2) here.

     uint[] smallP = [2];

     bool[B_SIZE / 2] mark = false;
     foreach (immutable uint i; 1 .. B_SIZE / 2) {
         if (!mark[i]) {
             pCount++; lastP = 2 * i + 1;
             // Do something with lastP here.

             smallP ~= lastP;
             if (lastP ^^ 2 <= B_SIZE)
                 crossOut(2 * i + 1, 1, mark);
         } else
             mark[i] = false;
     }

     for (uint b = 1 + B_SIZE; b < MAX_N; b += B_SIZE) {
         for (uint i = 1; smallP[i] ^^ 2 < b + B_SIZE; ++i)
             crossOut(smallP[i], b, mark);
         foreach (immutable uint i; 0 .. B_SIZE / 2) {
             if (!mark[i]) {
                 pCount++; lastP = 2 * i + b;
                 // Do something with lastP here.

                 if (lastP <= RT_MAX_N)
                     smallP ~= lastP;
             } else
                 mark[i] = false;
         }
     }

     return tuple(pCount, smallP.length, lastP);
}

void main() {
     immutable result = calcPrimes;

     writeln("Found ", result[0], " primes in total.");
     writeln("Recorded ", result[1], " small primes, up to ", 
RT_MAX_N);
     writeln("Last prime found was ", result[2]);
}


Is it a good idea to add a simple but reasonably fast Sieve 
implementation to Phobos? I have needed a prime numbers lazy 
range, and a isPrime() function numerous times. (And as for 
std.numeric.fft, people that need even more performance will use 
code outside Phobos).

Bye,
bearophile
Mar 18 2014
next sibling parent "Andrea Fontana" <nospam example.com> writes:
I can't understand whether or not this is a sieve of atkin...


On Tuesday, 18 March 2014 at 14:23:32 UTC, bearophile wrote:
 There is a efficient Sieve implementation in C++ here:

 http://code.activestate.com/recipes/577966-even-faster-prime-generator/?in=lang-cpp

 There are of course far faster implementations, but its 
 performance is not bad, while being still simple and quite 
 short.

 A D implementation (it's not a final version because the global 
 enums should be removed and replaced with run-time variables or 
 template arguments. And something different from just counting 
 must be added):


 import std.stdio, std.algorithm, std.typecons;

 enum uint MAX_N = 1_000_000_000U;
 enum uint RT_MAX_N = 32_000; // square of max prime under this 
 limit should exceed MAX_N.
 enum uint B_SIZE = 20_000;   // not sure what optimal value for 
 this is;
                              // currently must avoid overflow 
 when squared.

 // mod 30, (odd) primes have remainders 1,7,11,13,17,19,23,29.
 // e.g. start with mark[B_SIZE/30]
 // and offset[] = {1, 7, 11, ...}
 // then mark[i] corresponds to 30 * (i / 8) + b - 1 + offset[i 
 % 8].
 Tuple!(uint, size_t, uint) calcPrimes() pure nothrow {
     // Assumes p, b odd and p * p won't overflow.
     static void crossOut(in uint p, in uint b, bool[] mark)
     pure nothrow {
         uint si = (p - (b % p)) % p;
         if (si & 1)
             si += p;
         if (p ^^ 2 > b)
             si = si.max(p ^^ 2 - b);

         for (uint i = si / 2; i < B_SIZE / 2; i += p)
             mark[i] = true;
     }

     uint pCount = 1; uint lastP = 2;
     // Do something with first prime (2) here.

     uint[] smallP = [2];

     bool[B_SIZE / 2] mark = false;
     foreach (immutable uint i; 1 .. B_SIZE / 2) {
         if (!mark[i]) {
             pCount++; lastP = 2 * i + 1;
             // Do something with lastP here.

             smallP ~= lastP;
             if (lastP ^^ 2 <= B_SIZE)
                 crossOut(2 * i + 1, 1, mark);
         } else
             mark[i] = false;
     }

     for (uint b = 1 + B_SIZE; b < MAX_N; b += B_SIZE) {
         for (uint i = 1; smallP[i] ^^ 2 < b + B_SIZE; ++i)
             crossOut(smallP[i], b, mark);
         foreach (immutable uint i; 0 .. B_SIZE / 2) {
             if (!mark[i]) {
                 pCount++; lastP = 2 * i + b;
                 // Do something with lastP here.

                 if (lastP <= RT_MAX_N)
                     smallP ~= lastP;
             } else
                 mark[i] = false;
         }
     }

     return tuple(pCount, smallP.length, lastP);
 }

 void main() {
     immutable result = calcPrimes;

     writeln("Found ", result[0], " primes in total.");
     writeln("Recorded ", result[1], " small primes, up to ", 
 RT_MAX_N);
     writeln("Last prime found was ", result[2]);
 }


 Is it a good idea to add a simple but reasonably fast Sieve 
 implementation to Phobos? I have needed a prime numbers lazy 
 range, and a isPrime() function numerous times. (And as for 
 std.numeric.fft, people that need even more performance will 
 use code outside Phobos).

 Bye,
 bearophile

Mar 18 2014
prev sibling next sibling parent "Kelet" <kelethunter gmail.com> writes:
I've had good luck with Stephan Brumme's block-wise sieve[1], 
also based on the Sieve of Eratosthenes. It's best when 
calculating several blocks in parallel, of course. But it's still 
pretty fast even when used sequentially.

[1]: http://create.stephan-brumme.com/eratosthenes/
Mar 18 2014
prev sibling next sibling parent "Dan Killebrew" <danielk.misc gmail.com> writes:
On Tuesday, 18 March 2014 at 15:54:23 UTC, Andrea Fontana wrote:
 I can't understand whether or not this is a sieve of atkin...

The link says 'A very quick (segmented) sieve of Eratosthenes'
Mar 18 2014
prev sibling next sibling parent reply "Chris Williams" <yoreanon-chrisw yahoo.co.jp> writes:
On Tuesday, 18 March 2014 at 14:23:32 UTC, bearophile wrote:
 Is it a good idea to add a simple but reasonably fast Sieve 
 implementation to Phobos? I have needed a prime numbers lazy 
 range, and a isPrime() function numerous times. (And as for 
 std.numeric.fft, people that need even more performance will 
 use code outside Phobos).

My new job has finally given me permission to continue some work I was doing for Phobos, which includes an implementation of RSA. RSA uses primes quite heavily, 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?
Mar 18 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/19/14, 7:07 AM, Marco Leise wrote:
 I wonder if we could finally have that experimental package,
 call it "ext" or "etc" or whatever that has only one barrier
 to entry: the intent of the module must pass review.

I think it's time to add an experimental package. Andrei
Mar 19 2014
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/19/14, 8:45 AM, Dicebot wrote:
 On Wednesday, 19 March 2014 at 15:02:55 UTC, Andrei Alexandrescu wrote:
 On 3/19/14, 7:07 AM, Marco Leise wrote:
 I wonder if we could finally have that experimental package,
 call it "ext" or "etc" or whatever that has only one barrier
 to entry: the intent of the module must pass review.

I think it's time to add an experimental package. Andrei

I am against it. It gives nothing over dub and creates confusion.

Who'd be confused? Andrei
Mar 19 2014
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/19/14, 9:06 AM, Dicebot wrote:
 On Wednesday, 19 March 2014 at 15:58:43 UTC, Andrei Alexandrescu wrote:
 Who'd be confused?

 Andrei

Users who see find it in Phobos will be confused about how experimental exactly it is and what to expect from it. Developers will be confused about what is expected from them maintenance-wise starting from this point and what to do with reported bugs / issues. Don't put stuff which is naturally bleeding edge into scheduled controlled distributions. dub has special category for Phobos proposals, we need to better popularize it.

Ionno. To me "experimental" sounds as informative and self-explanatory as it gets, and puts things up for experimentation with the distribution and without requiring users to take special steps. Andrei
Mar 19 2014
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/19/14, 10:01 AM, Dicebot wrote:
 I avoid it too but it is my personal problem to deal with. dub is
 de-facto standard in D tool chain and I am pretty sure eventually will
 be distributed with dmd.

It may be time to look into this. Who wants to champion this effort? -- Andrei
Mar 19 2014
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/20/14, 6:07 AM, Dicebot wrote:
 On Wednesday, 19 March 2014 at 17:40:50 UTC, Andrei Alexandrescu wrote:
 On 3/19/14, 10:01 AM, Dicebot wrote:
 I avoid it too but it is my personal problem to deal with. dub is
 de-facto standard in D tool chain and I am pretty sure eventually will
 be distributed with dmd.

It may be time to look into this. Who wants to champion this effort? -- Andrei

I think it is _tiny_ bit to early - there are some relatively big intrusive changes planned for dub (like switching to SDL as default description grammar) and it is better to start distributing it once this stuff stabilizes. I'll keep it in my notes though and start poking people once it looks feasible :) Do you have any personal requirements in mind that need to be met before "legitimization" of dub?

I think it should be pig easy to use, battle tested, and have some security mechanism in place. Andrei
Mar 20 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Mar 18 2014
prev sibling next sibling parent "Chris Williams" <yoreanon-chrisw yahoo.co.jp> writes:
On Wednesday, 19 March 2014 at 01:29:16 UTC, bearophile wrote:
 - A function to compute the GCD on ulongs/longs/bigints is 
 useful.
 (Issues 4125 and 7102).

Yeah, several methods work just fine if you change their declaration to isIntegral!T || is(typeof(T) == BigInt). gcd() is one of them. Unfortunately, I don't trust rewriting isIntegral, so this sort of change would need to be on a function-by-function basis.
Mar 18 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 - A function to compute the GCD on ulongs/longs/bigints is 
 useful.
 (Issues 4125 and 7102).

A GCD is already in Phobos but it doesn't work with bigints. And putting it in the std.combinatorics is better. Bye, bearophile
Mar 18 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Chris Williams:

 Yeah, several methods work just fine if you change their 
 declaration to isIntegral!T || is(typeof(T) == BigInt). gcd() 
 is one of them.

 Unfortunately, I don't trust rewriting isIntegral, so this sort 
 of change would need to be on a function-by-function basis.

Don explained me that a GCD on BigInts should use a more efficient algorithm. Bye, bearophile
Mar 18 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 nor to contain the most optimized algorithms around.

This D1 code adapted from C code is much more efficient (and in D2 with ranges and TypeTuple-foreach it could become more efficient and much shorter), but I think something like this is overkill for Phobos: http://dpaste.dzfl.pl/cf97d15ade27 Bye, bearophile
Mar 18 2014
prev sibling next sibling parent "Meta" <jared771 gmail.com> writes:
On Wednesday, 19 March 2014 at 01:52:07 UTC, bearophile wrote:
 nor to contain the most optimized algorithms around.

This D1 code adapted from C code is much more efficient (and in D2 with ranges and TypeTuple-foreach it could become more efficient and much shorter), but I think something like this is overkill for Phobos: http://dpaste.dzfl.pl/cf97d15ade27 Bye, bearophile

If all that complexity is nicely encapsulated from the user, then why not put it in some theoretical Phobos package? Are you thinking of highly-optimized functionality that makes a usability tradeoff to be even faster?
Mar 18 2014
prev sibling next sibling parent "Dan Killebrew" <danielk.misc gmail.com> writes:
On Wednesday, 19 March 2014 at 01:29:16 UTC, bearophile wrote:

 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

I've wanted exactly this. I was doing the euler project problems and had to implement my own prime sieve, isPrime range, GCD, binomial, and combination function (I used Phobos' permutation function, but was a bit disappointed that it wasn't implemented as a range). Being familiar with the Python combinations/permutations functions, I was looking for similar functionality in Phobos and was sad to find it missing. So +1 for a combinatorics module, and for a numerical/prime module.
Mar 19 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Meta:

 If all that complexity is nicely encapsulated from the user, 
 then why not put it in some theoretical Phobos package?

For practical reasons. You have to maintain Phobos code. So you need people that understands the code. A very complex implementation is understood only by few persons. Also a very long piece of code needs more work to be maintained. Every line of code has a live cost. Bye, bearophile
Mar 19 2014
prev sibling next sibling parent "Andrea Fontana" <nospam example.com> writes:
I miss so much a std.geometry library with operations on 1d 2d 
and 3d objects (intersections, unions, difference, and so on...) 
in d style...

It would open a whole new world for me :)

On Wednesday, 19 March 2014 at 01:42:38 UTC, bearophile wrote:
 - A function to compute the GCD on ulongs/longs/bigints is 
 useful.
 (Issues 4125 and 7102).

A GCD is already in Phobos but it doesn't work with bigints. And putting it in the std.combinatorics is better. Bye, bearophile

Mar 19 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Dan Killebrew:

and had to implement my own prime sieve, isPrime range,<

The sieve is a range, but isPrime() is just a predicate function (possibly only logically pure, to store some precedent computation), it's not a range. Bye, bearophile
Mar 19 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Wed, 19 Mar 2014 11:22:55 +0000
schrieb "Andrea Fontana" <nospam example.com>:

 I miss so much a std.geometry library with operations on 1d 2d 
 and 3d objects (intersections, unions, difference, and so on...) 
 in d style...
 
 It would open a whole new world for me :)

I wonder if we could finally have that experimental package, call it "ext" or "etc" or whatever that has only one barrier to entry: the intent of the module must pass review. The API and code can build up over time as people start using it. At some point it can be called finished and thoroughly reviewed. I think the barrier of entry is currently very high since the reviews expect perfect quality from the start, but good things need time to collect corner cases and use cases that might cause major refactorings. It's straight forward to implement for rectangles or circles, but would any design still be good when someone tries to implement a 2D physics engine on top of that? Would CSG operations be part of the module? What about paths, curves and loading from and saving to vector graphics (SVG)? (I.e. you could literally draw the collision shape of a tree bitmap in Inkscape and load it as 2D geometry.) -- Marco
Mar 19 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Wed, 19 Mar 2014 10:39:36 +0000
schrieb "bearophile" <bearophileHUGS lycos.com>:

 Meta:
 
 If all that complexity is nicely encapsulated from the user, 
 then why not put it in some theoretical Phobos package?

For practical reasons. You have to maintain Phobos code. So you need people that understands the code. A very complex implementation is understood only by few persons. Also a very long piece of code needs more work to be maintained. Every line of code has a live cost. Bye, bearophile

For starters there are a lot of code blocks that differ only in 1 or 2 values. These should be extracted into inline functions with a nice name. -- Marco
Mar 19 2014
prev sibling next sibling parent "Andrea Fontana" <nospam example.com> writes:
I don't need a package to build an engine on top of it. If you're 
going to write a game with 3d and physic probably you're going to 
use ogre, irrlicht, physx or everything else. And they have their 
own optimized implementation of these objects.

But a geometry package is not only for game or physics. Just an 
example: I wrote (in c++) an app to merge two images. Here a 
test: http://www.e-nuts.net/test2.jpg (the right image is an 
automatic merge of the other two). In this case a geometry 
package would simplify my life a lot :)

Another thing I would like to do is a generator of solids to 
print with a 3d printer. Some strange math objects. Or maybe a 
slicer for 3d printer's software stack. Or something like 
openscad.

Here we need productivity rather than realtime performance.

On Wednesday, 19 March 2014 at 14:05:19 UTC, Marco Leise wrote:
 Am Wed, 19 Mar 2014 11:22:55 +0000
 schrieb "Andrea Fontana" <nospam example.com>:

 I miss so much a std.geometry library with operations on 1d 2d 
 and 3d objects (intersections, unions, difference, and so 
 on...) in d style...
 
 It would open a whole new world for me :)

I wonder if we could finally have that experimental package, call it "ext" or "etc" or whatever that has only one barrier to entry: the intent of the module must pass review. The API and code can build up over time as people start using it. At some point it can be called finished and thoroughly reviewed. I think the barrier of entry is currently very high since the reviews expect perfect quality from the start, but good things need time to collect corner cases and use cases that might cause major refactorings. It's straight forward to implement for rectangles or circles, but would any design still be good when someone tries to implement a 2D physics engine on top of that? Would CSG operations be part of the module? What about paths, curves and loading from and saving to vector graphics (SVG)? (I.e. you could literally draw the collision shape of a tree bitmap in Inkscape and load it as 2D geometry.)

Mar 19 2014
prev sibling next sibling parent Daniel =?ISO-8859-1?Q?Koz=E1k?= <kozzi11 gmail.com> writes:
Andrei Alexandrescu píše v St 19. 03. 2014 v 08:02 -0700:
 On 3/19/14, 7:07 AM, Marco Leise wrote:
 I wonder if we could finally have that experimental package,
 call it "ext" or "etc" or whatever that has only one barrier
 to entry: the intent of the module must pass review.

I think it's time to add an experimental package. Andrei

Mar 19 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Wednesday, 19 March 2014 at 15:02:55 UTC, Andrei Alexandrescu 
wrote:
 On 3/19/14, 7:07 AM, Marco Leise wrote:
 I wonder if we could finally have that experimental package,
 call it "ext" or "etc" or whatever that has only one barrier
 to entry: the intent of the module must pass review.

I think it's time to add an experimental package. Andrei

I am against it. It gives nothing over dub and creates confusion.
Mar 19 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Wednesday, 19 March 2014 at 15:58:43 UTC, Andrei Alexandrescu 
wrote:
 Who'd be confused?

 Andrei

Users who see find it in Phobos will be confused about how experimental exactly it is and what to expect from it. Developers will be confused about what is expected from them maintenance-wise starting from this point and what to do with reported bugs / issues. Don't put stuff which is naturally bleeding edge into scheduled controlled distributions. dub has special category for Phobos proposals, we need to better popularize it.
Mar 19 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Wed, 19 Mar 2014 16:06:44 +0000
schrieb "Dicebot" <public dicebot.lv>:

 On Wednesday, 19 March 2014 at 15:58:43 UTC, Andrei Alexandrescu 
 wrote:
 Who'd be confused?

 Andrei

Users who see find it in Phobos will be confused about how experimental exactly it is and what to expect from it. Developers will be confused about what is expected from them maintenance-wise starting from this point and what to do with reported bugs / issues.

Why was that never a problem for OpenGL ?
 Don't put stuff which is naturally bleeding edge into scheduled 
 controlled distributions. dub has special category for Phobos 
 proposals, we need to better popularize it.

That much is true. Last time I checked it wasn't there. Then again everyone can add categories there. I added two myself. Everyone can tag their package as Phobos candidate. But I cannot imagine random packages on dub getting the same exposure as modules included in Phobos. They will be auto-tested, the idea has the approval of the community and they are ready to use when you install the compiler. Personally I avoid dub, so to that end I'm probably biased. -- Marco
Mar 19 2014
prev sibling next sibling parent Russel Winder <russel winder.org.uk> writes:
On Wed, 2014-03-19 at 15:45 +0000, Dicebot wrote:
 On Wednesday, 19 March 2014 at 15:02:55 UTC, Andrei Alexandrescu 
 wrote:
 On 3/19/14, 7:07 AM, Marco Leise wrote:
 I wonder if we could finally have that experimental package,
 call it "ext" or "etc" or whatever that has only one barrier
 to entry: the intent of the module must pass review.

I think it's time to add an experimental package. Andrei

I am against it. It gives nothing over dub and creates confusion.

The experimental package was removed from Go once the importing from repositories worked properly. The core had only in it that which had been agreed by the process, nothing experimental. This made everything a lot cleaner. So I think keeping Phobos with only vetted and approved code is a better solution. -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Mar 19 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Wednesday, 19 March 2014 at 16:42:43 UTC, Andrei Alexandrescu 
wrote:
 Ionno. To me "experimental" sounds as informative and 
 self-explanatory as it gets, and puts things up for 
 experimentation with the distribution and without requiring 
 users to take special steps.

 Andrei

If it is in Phobos repo, it: - floods Phobos notifications / activity list - gets bug reports into D bugzilla ..except author does not have direct access to it anymore. And if author decides it is not worth pursuing anymore, unsupported module will still be kept in distribution. "experimental" by definition implies that author is supposed to tinker about it and it needs rapid edit-feedback cycle. You can't get it if put code out of authors control into Phobos. It will be same problem as with Deimos - stuff just rots there. With only exception that you don't need to change C bindings often, contrary to experimental Phobos modules. Also different people have different expectation of "experimental" stability. Some may think it is something almost fleshed in stone (it is going to be proposed to Phobos after all!) but with occasional tweaks. In practice it is something that can be completely re-written or even disappear by next Phobos release.
Mar 19 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Wednesday, 19 March 2014 at 16:35:15 UTC, Marco Leise wrote:
 Users who see find it in Phobos will be confused about how 
 experimental exactly it is and what to expect from it. 
 Developers will be confused about what is expected from them 
 maintenance-wise starting from this point and what to do with 
 reported bugs / issues.

Why was that never a problem for OpenGL ?

I know nothing about OpenGL but it was (and is) huge problem for Java.
 Don't put stuff which is naturally bleeding edge into 
 scheduled controlled distributions. dub has special category 
 for Phobos proposals, we need to better popularize it.

That much is true. Last time I checked it wasn't there. Then again everyone can add categories there. I added two myself. Everyone can tag their package as Phobos candidate.

There is no point in implementing moderated category until it is not abused. If it will attract abuse, we will add moderation.
 But I cannot imagine random packages on dub getting the same
 exposure as modules included in Phobos.

The problem is exactly that those are random package right now. Instead those should be cleanly visible in code.dlang.org interface and possibly also linked from dlang.org main page. Linked from distributed Phobos documentation. Everything should beg user to go and try it.
 Personally I avoid dub, so to that end I'm probably biased.

I avoid it too but it is my personal problem to deal with. dub is de-facto standard in D tool chain and I am pretty sure eventually will be distributed with dmd.
Mar 19 2014
prev sibling next sibling parent "Chris Williams" <yoreanon-chrisw yahoo.co.jp> writes:
On Wednesday, 19 March 2014 at 01:44:16 UTC, bearophile wrote:
 Chris Williams:

 Yeah, several methods work just fine if you change their 
 declaration to isIntegral!T || is(typeof(T) == BigInt). gcd() 
 is one of them.

 Unfortunately, I don't trust rewriting isIntegral, so this 
 sort of change would need to be on a function-by-function 
 basis.

Don explained me that a GCD on BigInts should use a more efficient algorithm. Bye, bearophile

There's a couple algorithms on the Wikipedia, but when I profiled them on some -very large- values, they all had similar performance times, including the ones that were just a few lines of simple code. It's possible that there's an optimized variant somewhere on the greater internet, but that might take some hunting to track down. Ultimately, it's probably better to expose functionality in Phobos, even if they're simple implementations. Eventually, some enterprising person will find and implement an optimized version, and in the meantime, everyone has a working, tested version that they didn't have to write nor validate themselves.
Mar 19 2014
prev sibling next sibling parent Russel Winder <russel winder.org.uk> writes:
On Wed, 2014-03-19 at 17:01 +0000, Dicebot wrote:
[…]
 I know nothing about OpenGL but it was (and is) huge problem for 
 Java.

Well sort of. Calling from Java into any C, C++ or D library can be a bit of a pain, involving JNI (or possibly JNA). JOGL has shown that Java calling OpenGL is doable and works. Likewise JavaFX connects into the OpenGL infrastructure. So this is now essentially a solved problem. What is much more of a problem for Java is GPGPU parallelism. There are a couple of groups working on this and there will be a solution. There has to be as the team members of one of the teams actually have to make it work or start losing money. […]
 Personally I avoid dub, so to that end I'm probably biased.

I avoid it too but it is my personal problem to deal with. dub is de-facto standard in D tool chain and I am pretty sure eventually will be distributed with dmd.

SCons currently has no real "play" in this dependency management area and given that all the support in the D community appears to be for Dub, there seems no point in adding the features to SCons. Gradle has all the dependency management stuff sorted already and now has C and C++ build capability. I wonder if it might be worth adding D support to that? -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Mar 19 2014
prev sibling next sibling parent "Chris Williams" <yoreanon-chrisw yahoo.co.jp> writes:
On Tuesday, 18 March 2014 at 14:23:32 UTC, bearophile wrote:
 There is a efficient Sieve implementation in C++ here:

 http://code.activestate.com/recipes/577966-even-faster-prime-generator/?in=lang-cpp

 There are of course far faster implementations, but its 
 performance is not bad, while being still simple and quite 
 short.

Here's a straightforward implementation, if you don't already have one (I assume you're doing this for Rosetta Code). I had to decrease your MAX_N by 100-fold to get a similar runtime, but it's a fairly faithful implementation of Eratosthenes' method as written. enum uint MAX_N = 10_000_000U; void calcPrimes() pure nothrow { uint[][uint] markers; for (uint L = 2; L < MAX_N; L++) { uint[]* pList = (L in markers); if (pList is null) { markers[L + L] = [L]; } else { uint[] list = *pList; size_t len = list.length - 1; for (uint L2 = 0; L2 < len; L2++) { uint val = list[L2]; markers[ L + val ] ~= val; } // reuse the current list for the last item to save allocations list[0] = list[len]; list.length = 1; markers[ L + list[len] ] = list; } } } void main() { calcPrimes; }
Mar 19 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Chris Williams:

 Here's a straightforward implementation, if you don't already 
 have one (I assume you're doing this for Rosetta Code).

RosettaCode has already several sieves in D. I am not doing this for RosettaCode. What I am doing in this thread is to ask if there's desire for a efficient (quite more than your version) but still sufficiently simple implementation of a unbounded lazy Sieve range for Phobos. Bye, bearophile
Mar 19 2014
prev sibling next sibling parent "Chris Williams" <yoreanon-chrisw yahoo.co.jp> writes:
On Wednesday, 19 March 2014 at 18:40:49 UTC, Chris Williams wrote:
 enum uint MAX_N = 10_000_000U;

 void calcPrimes() pure nothrow {
     uint[][uint] markers;

     for (uint L = 2; L < MAX_N; L++) {
         uint[]* pList = (L in markers);
         if (pList is null) {
             markers[L + L] = [L];
         }
         else {
             uint[] list = *pList;
             size_t len = list.length - 1;
             for (uint L2 = 0; L2 < len; L2++) {
                 uint val = list[L2];
                 markers[ L + val ] ~= val;
             }

             // reuse the current list for the last item to save 
 allocations
             list[0] = list[len];
             list.length = 1;
             markers[ L + list[len] ] = list;
         }
     }
 }

 void main() {
     calcPrimes;
 }

Well bummer, my quick and easy optimization broke the result for some reason. Here's a version that actually produces the correct answers, while I try and debug: enum uint MAX_N = 10_000_000U; void calcPrimes() { uint[][uint] markers; for (uint L = 2; L < MAX_N; L++) { uint[]* pList = (L in markers); if (pList is null) { markers[L + L] = [L]; } else { uint[] list = *pList; for (uint L2 = 0; L2 < list.length; L2++) { uint val = list[L2]; markers[ L + val ] ~= val; } } } } void main() { calcPrimes; }
Mar 19 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Wed, 19 Mar 2014 16:45:45 +0000
schrieb Russel Winder <russel winder.org.uk>:

 The experimental package was removed from Go once the importing from
 repositories worked properly. The core had only in it that which had
 been agreed by the process, nothing experimental. This made everything a
 lot cleaner.

 So I think keeping Phobos with only vetted and approved code is a better
 solution.

Wait, what? Because Go has special infrastructure in the compiler front-end that enables it to import directly from repositories like this import ( "fmt" "github.com/user/newmath" ) we should also keep experimental modules out of the standard library? Shouldn't we first get this technology? It's a whole different story if the compiler front-end seamlessly downloads missing imports in the background, than if you have to install dub and create a project file first. Besides you are relying on a third party tool you may or may not plan to use for building. Anyways, I just thought an experimental package right in Phobos would be the straight forward way to give the most exposure to new modules that we want tried in the field before inclusion. That's where my vote goes. -- Marco
Mar 19 2014
prev sibling next sibling parent "Dicebot" <public dicebot.lv> writes:
On Wednesday, 19 March 2014 at 17:40:50 UTC, Andrei Alexandrescu 
wrote:
 On 3/19/14, 10:01 AM, Dicebot wrote:
 I avoid it too but it is my personal problem to deal with. dub 
 is
 de-facto standard in D tool chain and I am pretty sure 
 eventually will
 be distributed with dmd.

It may be time to look into this. Who wants to champion this effort? -- Andrei

I think it is _tiny_ bit to early - there are some relatively big intrusive changes planned for dub (like switching to SDL as default description grammar) and it is better to start distributing it once this stuff stabilizes. I'll keep it in my notes though and start poking people once it looks feasible :) Do you have any personal requirements in mind that need to be met before "legitimization" of dub?
Mar 20 2014
prev sibling next sibling parent "Gary Willoughby" <dev nomad.so> writes:
On Wednesday, 19 March 2014 at 17:40:50 UTC, Andrei Alexandrescu 
wrote:
 On 3/19/14, 10:01 AM, Dicebot wrote:
 I avoid it too but it is my personal problem to deal with. dub 
 is
 de-facto standard in D tool chain and I am pretty sure 
 eventually will
 be distributed with dmd.

It may be time to look into this. Who wants to champion this effort? -- Andrei

I'd support inclusion into the official Dlang package but it has to be ready for distribution. I'm a big fan of it but it doesn't seem 100% stable yet. For experimental libs i'd rather they were kept out of phobos and placed within the dub registry. We can load and use them at leisure from there without expecting any sort of support from the language maintainers. If included in phobos i can almost guarantee that even though they will be marked experimental devs will moan when they change because they will have an official stamp. Dub should be more embraced by the official language maintainers especially moving the Deimos repo's into there. I myself have had to duplicate and package a deimos repo and add it just to move on with a project.
Mar 20 2014
prev sibling next sibling parent "David Eagen" <davideagen mailinator.com> writes:
On Thursday, 20 March 2014 at 21:31:13 UTC, Gary Willoughby wrote:
 For experimental libs i'd rather they were kept out of phobos 
 and placed within the dub registry. We can load and use them at 
 leisure from there without expecting any sort of support from 
 the language maintainers. If included in phobos i can almost 
 guarantee that even though they will be marked experimental 
 devs will moan when they change because they will have an 
 official stamp.

+1
Mar 20 2014
prev sibling next sibling parent "safety0ff" <safety0ff.dev gmail.com> writes:
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/
Mar 30 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
safety0ff:

 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.

I implemented many of those in my old D1 nonstandard library. I still port some of them to D2 now and then. So I agree they are needed.
 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.

This is an interesting opinion. Can you explain why an isPrime is less useful than a isProbablePrime (like this: http://en.wikipedia.org/wiki/Miller-Rabin_primality_test ) plus a sieve? Can't you have both a isPrime and a isProbablePrime in Phobos? Bye, bearophile
Mar 30 2014
prev sibling next sibling parent "safety0ff" <safety0ff.dev gmail.com> writes:
On Sunday, 30 March 2014 at 23:40:14 UTC, bearophile wrote:
 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.

This is an interesting opinion. Can you explain why an isPrime is less useful than a isProbablePrime (like this: http://en.wikipedia.org/wiki/Miller-Rabin_primality_test ) plus a sieve? Can't you have both a isPrime and a isProbablePrime in Phobos? Bye, bearophile

You can have both, it's not less useful. I just wonder if there are real-world use-cases worth supporting in Phobos where you want need a one-off primality test where a definite answer is require. I.E. Are there non-toy uses to support inclusion?
Mar 30 2014
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
safety0ff:

 I.E. Are there non-toy uses to support inclusion?

I have several non-toy uses for the GCD, binomial, and the permutations/combinations/pairwise ranges. The other little discrete numerical functions like the integer square root, etc, are useful sufficiently often. The other two (isPrime and a sieve) are less practical, so their inclusion is more debatable. Sometimes you want some small primes for hashing, or in the unittests of a Rational type, and few other situations. But D is for mathematics usage too. Given the commonality of prime numbers in discrete mathematics (example: if you want to study certain graphs), I think such two/three functions/generators are acceptable, if they aren't too much complex. Bye, bearophile
Mar 30 2014
prev sibling next sibling parent Marco Leise <Marco.Leise gmx.de> writes:
Am Sun, 30 Mar 2014 23:05:55 +0000
schrieb "safety0ff" <safety0ff.dev gmail.com>:

 I think we need a solid integer math module more than anything on=20
 this list.
 I find myself often reimplementing ilog2, isqrt, isPowerOf2, etc,=20
 etc.

More or less real world stuff: minMax(x, low, high) Returns x clamped the low and high boundary so that low <=3D x <=3D high. setMax(x, high) Same but only clamps high values. setMin(x, low) Same but only clamps low values. isWithin(x, low, high) Checks if x is within a given range. isPowerOfTwo(x) Basically checks if only one bit is set. nextPowerOfTwo(x) Returns x rounded up to be a power of two. bitMask(T)(T bitNum) Returns cast(T) 1 << x. The result is always the type of the parameter. bitMaskRange(firstBitNum, bitCount) Generates a mask of consecutive set bits starting with 'firstBitNum' and counting 'bitCount' bits. log2(x) Returns the highest power of 2 in 'x'. roundUp(x, multiple) Rounds 'x' up to the next multiple of 'multiple'. A version that works with pointers is also useful. roundDown(x, multiple) Rounds 'x' down to the next multiple of 'multiple'. roundUpDiv(x, divisor) Normal integer division rounds down. This version rounds up. sqr(x) x*x KiB(x) x*1024 MiB(x) x*1024*1024 isEven(x) !(x & 1) =46rom Project Euler solutions: sum_1_to_n(n) Returns the sum of all integers [1 .. n] in O(1) time complexity. sum_1_to_n_dividable_by(n, d) Same as above but counts only values dividable by 'd'. generalized_pentagonal_number(n) Don't know what this is, but it is O(1) as well. gcd(u, v) Greatest common divisor. Some copied&pasted algorithm, that works by comparing set bits in 'u' and 'v'. Very fast for being implemented in standard C without assembly hacks. are_coprime(u, v) Returns true, iff the greatest common divisor of 'u' and 'v' is 1. pascal_row(n) Returns the n-th row of Pascal's triangle. This gives you "n choose k" for a fixed 'n' and all k in 0<=3Dk<=3Dn. (This function allocates an integer array.) Also there is a Pascal's triangle struct, that allows marching through the triangle quickly using methods like 'rightUp' or 'left'. Pascal's triangle operations are useful in combinatorics. ----------8<------------- /** * The ultimate tool to move around in Pascal's triangle. Pascal(0, 0) is t= he * top of the triangle with the value of 1. */ struct Pascal { this(=E2=84=95 n, =E2=84=95 k) { // internally we offset these by +1, to simplify the math ++n; ++k; _n =3D n; if (k > n / 2) { _k =3D _n; left(_n - k); } else { right(k - 1); } } =09 =E2=84=95 left(=E2=84=95 amount) { while (amount--) { _value *=3D --_k; _value /=3D _n - _k; } return _value; } =09 =E2=84=95 right(=E2=84=95 amount) { while (amount--) { _value *=3D _n - _k; _value /=3D _k++; } return _value; } =09 =E2=84=95 rightDown(=E2=84=95 amount) { while (amount--) { _value *=3D _n++; _value /=3D _k++; } return _value; } =E2=84=95 leftDown(=E2=84=95 amount) { while (amount--) { _value *=3D _n++; _value /=3D _n - _k; } return _value; } =E2=84=95 leftUp(=E2=84=95 amount) { while (amount--) { _value *=3D --_k; _value /=3D --_n; } return _value; } =E2=84=95 rightUp(=E2=84=95 amount) { while (amount--) { _value *=3D _n - _k; _value /=3D --_n; } return _value; } =09 property =E2=84=95 value() { return _value; } =09 alias value this; =09 private: =09 =E2=84=95 _n =3D 1, _k =3D 1; =E2=84=95 _value =3D 1; } --=20 Marco
Mar 30 2014
prev sibling next sibling parent "safety0ff" <safety0ff.dev gmail.com> writes:
I think we should get started with a Phobos integer module 
proposal/implementation.

What is the best way to move forward?
A community editable document with a repo to merge our 
contributions to?

I am not familiar with using dub.
Mar 30 2014
prev sibling next sibling parent Ziad Hatahet <hatahet gmail.com> writes:
--bcaec53f2e27d1b9e504f5df00fe
Content-Type: text/plain; charset=ISO-8859-1

      if (p ^^ 2 > b)
            si = si.max(p ^^ 2 - b);


Can't that be written as: auto t = p ^^ 2 - b; if (t > 0 && t > si) si = t; -- Ziad On Tue, Mar 18, 2014 at 7:23 AM, bearophile <bearophileHUGS lycos.com>wrote:
 There is a efficient Sieve implementation in C++ here:

 http://code.activestate.com/recipes/577966-even-faster-
 prime-generator/?in=lang-cpp

 There are of course far faster implementations, but its performance is not
 bad, while being still simple and quite short.

 A D implementation (it's not a final version because the global enums
 should be removed and replaced with run-time variables or template
 arguments. And something different from just counting must be added):


 import std.stdio, std.algorithm, std.typecons;

 enum uint MAX_N = 1_000_000_000U;
 enum uint RT_MAX_N = 32_000; // square of max prime under this limit
 should exceed MAX_N.
 enum uint B_SIZE = 20_000;   // not sure what optimal value for this is;
                              // currently must avoid overflow when squared.

 // mod 30, (odd) primes have remainders 1,7,11,13,17,19,23,29.
 // e.g. start with mark[B_SIZE/30]
 // and offset[] = {1, 7, 11, ...}
 // then mark[i] corresponds to 30 * (i / 8) + b - 1 + offset[i % 8].
 Tuple!(uint, size_t, uint) calcPrimes() pure nothrow {
     // Assumes p, b odd and p * p won't overflow.
     static void crossOut(in uint p, in uint b, bool[] mark)
     pure nothrow {
         uint si = (p - (b % p)) % p;
         if (si & 1)
             si += p;
         if (p ^^ 2 > b)
             si = si.max(p ^^ 2 - b);

         for (uint i = si / 2; i < B_SIZE / 2; i += p)
             mark[i] = true;
     }

     uint pCount = 1; uint lastP = 2;
     // Do something with first prime (2) here.

     uint[] smallP = [2];

     bool[B_SIZE / 2] mark = false;
     foreach (immutable uint i; 1 .. B_SIZE / 2) {
         if (!mark[i]) {
             pCount++; lastP = 2 * i + 1;
             // Do something with lastP here.

             smallP ~= lastP;
             if (lastP ^^ 2 <= B_SIZE)
                 crossOut(2 * i + 1, 1, mark);
         } else
             mark[i] = false;
     }

     for (uint b = 1 + B_SIZE; b < MAX_N; b += B_SIZE) {
         for (uint i = 1; smallP[i] ^^ 2 < b + B_SIZE; ++i)
             crossOut(smallP[i], b, mark);
         foreach (immutable uint i; 0 .. B_SIZE / 2) {
             if (!mark[i]) {
                 pCount++; lastP = 2 * i + b;
                 // Do something with lastP here.

                 if (lastP <= RT_MAX_N)
                     smallP ~= lastP;
             } else
                 mark[i] = false;
         }
     }

     return tuple(pCount, smallP.length, lastP);
 }

 void main() {
     immutable result = calcPrimes;

     writeln("Found ", result[0], " primes in total.");
     writeln("Recorded ", result[1], " small primes, up to ", RT_MAX_N);
     writeln("Last prime found was ", result[2]);
 }


 Is it a good idea to add a simple but reasonably fast Sieve implementation
 to Phobos? I have needed a prime numbers lazy range, and a isPrime()
 function numerous times. (And as for std.numeric.fft, people that need even
 more performance will use code outside Phobos).

 Bye,
 bearophile

--bcaec53f2e27d1b9e504f5df00fe Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div><div>&gt;&gt;=A0 =A0 =A0 if (p ^^ 2 &gt; b)<br>&gt;&g= t;=A0 =A0 =A0 =A0 =A0 =A0 si =3D si.max(p ^^ 2 - b);<br><br></div>Can&#39;t= that be written as:<br><br></div>auto t =3D p ^^ 2 - b;<br>if (t &gt; 0 &a= mp;&amp; t &gt; si) si =3D t;<br> <br></div><div class=3D"gmail_extra"><br clear=3D"all"><div>--<br>Ziad</div=

ile <span dir=3D"ltr">&lt;<a href=3D"mailto:bearophileHUGS lycos.com" targe= t=3D"_blank">bearophileHUGS lycos.com</a>&gt;</span> wrote:<br><blockquote = class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid= ;padding-left:1ex"> There is a efficient Sieve implementation in C++ here:<br> <br> <a href=3D"http://code.activestate.com/recipes/577966-even-faster-prime-gen= erator/?in=3Dlang-cpp" target=3D"_blank">http://code.activestate.com/<u></u=
recipes/577966-even-faster-<u></u>prime-generator/?in=3Dlang-cpp</a><br>

There are of course far faster implementations, but its performance is not = bad, while being still simple and quite short.<br> <br> A D implementation (it&#39;s not a final version because the global enums s= hould be removed and replaced with run-time variables or template arguments= . And something different from just counting must be added):<br> <br> <br> import std.stdio, std.algorithm, std.typecons;<br> <br> enum uint MAX_N =3D 1_000_000_000U;<br> enum uint RT_MAX_N =3D 32_000; // square of max prime under this limit shou= ld exceed MAX_N.<br> enum uint B_SIZE =3D 20_000; =A0 // not sure what optimal value for this is= ;<br> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0// currently mus= t avoid overflow when squared.<br> <br> // mod 30, (odd) primes have remainders 1,7,11,13,17,19,23,29.<br> // e.g. start with mark[B_SIZE/30]<br> // and offset[] =3D {1, 7, 11, ...}<br> // then mark[i] corresponds to 30 * (i / 8) + b - 1 + offset[i % 8].<br> Tuple!(uint, size_t, uint) calcPrimes() pure nothrow {<br> =A0 =A0 // Assumes p, b odd and p * p won&#39;t overflow.<br> =A0 =A0 static void crossOut(in uint p, in uint b, bool[] mark)<br> =A0 =A0 pure nothrow {<br> =A0 =A0 =A0 =A0 uint si =3D (p - (b % p)) % p;<br> =A0 =A0 =A0 =A0 if (si &amp; 1)<br> =A0 =A0 =A0 =A0 =A0 =A0 si +=3D p;<br> =A0 =A0 =A0 =A0 if (p ^^ 2 &gt; b)<br> =A0 =A0 =A0 =A0 =A0 =A0 si =3D si.max(p ^^ 2 - b);<br> <br> =A0 =A0 =A0 =A0 for (uint i =3D si / 2; i &lt; B_SIZE / 2; i +=3D p)<br> =A0 =A0 =A0 =A0 =A0 =A0 mark[i] =3D true;<br> =A0 =A0 }<br> <br> =A0 =A0 uint pCount =3D 1; uint lastP =3D 2;<br> =A0 =A0 // Do something with first prime (2) here.<br> <br> =A0 =A0 uint[] smallP =3D [2];<br> <br> =A0 =A0 bool[B_SIZE / 2] mark =3D false;<br> =A0 =A0 foreach (immutable uint i; 1 .. B_SIZE / 2) {<br> =A0 =A0 =A0 =A0 if (!mark[i]) {<br> =A0 =A0 =A0 =A0 =A0 =A0 pCount++; lastP =3D 2 * i + 1;<br> =A0 =A0 =A0 =A0 =A0 =A0 // Do something with lastP here.<br> <br> =A0 =A0 =A0 =A0 =A0 =A0 smallP ~=3D lastP;<br> =A0 =A0 =A0 =A0 =A0 =A0 if (lastP ^^ 2 &lt;=3D B_SIZE)<br> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 crossOut(2 * i + 1, 1, mark);<br> =A0 =A0 =A0 =A0 } else<br> =A0 =A0 =A0 =A0 =A0 =A0 mark[i] =3D false;<br> =A0 =A0 }<br> <br> =A0 =A0 for (uint b =3D 1 + B_SIZE; b &lt; MAX_N; b +=3D B_SIZE) {<br> =A0 =A0 =A0 =A0 for (uint i =3D 1; smallP[i] ^^ 2 &lt; b + B_SIZE; ++i)<br> =A0 =A0 =A0 =A0 =A0 =A0 crossOut(smallP[i], b, mark);<br> =A0 =A0 =A0 =A0 foreach (immutable uint i; 0 .. B_SIZE / 2) {<br> =A0 =A0 =A0 =A0 =A0 =A0 if (!mark[i]) {<br> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 pCount++; lastP =3D 2 * i + b;<br> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 // Do something with lastP here.<br> <br> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 if (lastP &lt;=3D RT_MAX_N)<br> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 smallP ~=3D lastP;<br> =A0 =A0 =A0 =A0 =A0 =A0 } else<br> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 mark[i] =3D false;<br> =A0 =A0 =A0 =A0 }<br> =A0 =A0 }<br> <br> =A0 =A0 return tuple(pCount, smallP.length, lastP);<br> }<br> <br> void main() {<br> =A0 =A0 immutable result =3D calcPrimes;<br> <br> =A0 =A0 writeln(&quot;Found &quot;, result[0], &quot; primes in total.&quot= ;);<br> =A0 =A0 writeln(&quot;Recorded &quot;, result[1], &quot; small primes, up t= o &quot;, RT_MAX_N);<br> =A0 =A0 writeln(&quot;Last prime found was &quot;, result[2]);<br> }<br> <br> <br> Is it a good idea to add a simple but reasonably fast Sieve implementation = to Phobos? I have needed a prime numbers lazy range, and a isPrime() functi= on numerous times. (And as for std.numeric.fft, people that need even more = performance will use code outside Phobos).<br> <br> Bye,<br> bearophile<br> </blockquote></div><br></div> --bcaec53f2e27d1b9e504f5df00fe--
Mar 30 2014
prev sibling next sibling parent "Dominikus Dittes Scherkl" writes:
On Sunday, 30 March 2014 at 23:05:57 UTC, safety0ff wrote:

 I find myself often reimplementing ilog2, isqrt, isPowerOf2,

Mar 30 2014
prev sibling next sibling parent "safety0ff" <safety0ff.dev gmail.com> writes:
On Monday, 31 March 2014 at 06:10:08 UTC, Dominikus Dittes 
Scherkl wrote:
 On Sunday, 30 March 2014 at 23:05:57 UTC, safety0ff wrote:

 I find myself often reimplementing ilog2, isqrt, isPowerOf2,


The point is that it should be in the standard library instead of copy pasted every time I have a short 1-file program that requires it.
Mar 31 2014
prev sibling parent Russel Winder <russel winder.org.uk> writes:
On Mon, 2014-03-31 at 00:55 +0000, bearophile wrote:
 safety0ff:
 
 I.E. Are there non-toy uses to support inclusion?

I have several non-toy uses for the GCD, binomial, and the permutations/combinations/pairwise ranges.

Finance, bioinformatics, signal processing, are some of the areas I know of where all this sort of stuff is useful. Python, Mathematica, Julia all provide these either fast using hardware numbers or to arbitrary accuracy using software numbers.
 The other little discrete numerical functions like the integer 
 square root, etc, are useful sufficiently often.
 
 The other two (isPrime and a sieve) are less practical, so their 
 inclusion is more debatable. Sometimes you want some small primes 
 for hashing, or in the unittests of a Rational type, and few 
 other situations. But D is for mathematics usage too. Given the 
 commonality of prime numbers in discrete mathematics (example: if 
 you want to study certain graphs), I think such two/three 
 functions/generators are acceptable, if they aren't too much 
 complex.

Or for force cracking of encodings? ;-) -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Mar 31 2014