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 reply "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
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 "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 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
next sibling parent reply "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
next sibling parent reply "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
parent reply "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
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 reply "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
parent reply "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
parent reply 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
next sibling 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
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
 
 


+1 it will be improvement
Mar 19 2014
prev sibling parent reply "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
next sibling 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
parent reply "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
next sibling parent reply 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
parent reply "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
next 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
next sibling parent reply "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
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 parent reply "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
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 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 parent reply 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
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 parent reply 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
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 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 reply "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
parent reply "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
parent reply "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
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 reply "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
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 parent reply "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
next sibling parent reply "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
parent reply "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
parent reply "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
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
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 parent reply "Dominikus Dittes Scherkl" writes:
On Sunday, 30 March 2014 at 23:05:57 UTC, safety0ff wrote:


 I find myself often reimplementing ilog2, isqrt, isPowerOf2,


isPowerOf2 { x => (x && !(x & (x-1))) }
Mar 30 2014
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,


 isPowerOf2 { x => (x && !(x & (x-1))) }


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 "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 reply "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
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 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 parent Ziad Hatahet <hatahet gmail.com> writes:
      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
Mar 30 2014