## digitalmars.D - A simple sieve in Phobos?

- bearophile (76/76) Mar 18 2014 There is a efficient Sieve implementation in C++ here:
- Andrea Fontana (2/79) Mar 18 2014
- Dan Killebrew (2/3) Mar 18 2014 The link says 'A very quick (segmented) sieve of Eratosthenes'
- Kelet (5/5) Mar 18 2014 I've had good luck with Stephan Brumme's block-wise sieve[1],
- Chris Williams (8/13) Mar 18 2014 My new job has finally given me permission to continue some work
- bearophile (34/40) Mar 18 2014 I suggest a Phobos module named "combinatorics" (or just
- Chris Williams (6/9) Mar 18 2014 Yeah, several methods work just fine if you change their
- bearophile (5/10) Mar 18 2014 Don explained me that a GCD on BigInts should use a more
- Chris Williams (12/24) Mar 19 2014 There's a couple algorithms on the Wikipedia, but when I profiled
- bearophile (4/7) Mar 18 2014 A GCD is already in Phobos but it doesn't work with bigints. And
- Andrea Fontana (5/12) Mar 19 2014 I miss so much a std.geometry library with operations on 1d 2d
- Marco Leise (20/25) Mar 19 2014 I wonder if we could finally have that experimental package,
- Andrei Alexandrescu (3/6) Mar 19 2014 I think it's time to add an experimental package.
- Daniel =?ISO-8859-1?Q?Koz=E1k?= (2/12) Mar 19 2014 +1 it will be improvement
- Dicebot (3/9) Mar 19 2014 I am against it. It gives nothing over dub and creates confusion.
- Andrei Alexandrescu (3/13) Mar 19 2014 Who'd be confused?
- Dicebot (10/12) Mar 19 2014 Users who see find it in Phobos will be confused about how
- Marco Leise (15/29) Mar 19 2014 Why was that never a problem for OpenGL ?
- Dicebot (13/28) Mar 19 2014 I know nothing about OpenGL but it was (and is) huge problem for
- Andrei Alexandrescu (3/6) Mar 19 2014 It may be time to look into this. Who wants to champion this effort? --
- Dicebot (9/17) Mar 20 2014 I think it is _tiny_ bit to early - there are some relatively big
- Andrei Alexandrescu (4/19) Mar 20 2014 I think it should be pig easy to use, battle tested, and have some
- Gary Willoughby (16/24) Mar 20 2014 I'd support inclusion into the official Dlang package but it has
- David Eagen (2/9) Mar 20 2014 +1
- Russel Winder (23/30) Mar 19 2014 Well sort of. Calling from Java into any C, C++ or D library can be a
- Andrei Alexandrescu (5/16) Mar 19 2014 Ionno. To me "experimental" sounds as informative and self-explanatory
- Dicebot (20/25) Mar 19 2014 If it is in Phobos repo, it:
- Russel Winder (13/25) Mar 19 2014 The experimental package was removed from Go once the importing from
- Marco Leise (22/28) Mar 19 2014 Wait, what? Because Go has special infrastructure in the
- Andrea Fontana (15/38) Mar 19 2014 I don't need a package to build an engine on top of it. If you're
- bearophile (7/8) Mar 18 2014 This D1 code adapted from C code is much more efficient (and in
- Meta (5/13) Mar 18 2014 If all that complexity is nicely encapsulated from the user, then
- bearophile (8/10) Mar 19 2014 For practical reasons. You have to maintain Phobos code. So you
- Marco Leise (7/20) Mar 19 2014 For starters there are a lot of code blocks that differ only
- Dan Killebrew (9/43) Mar 19 2014 I've wanted exactly this. I was doing the euler project problems
- bearophile (6/7) Mar 19 2014 The sieve is a range, but isPrime() is just a predicate function
- safety0ff (20/35) Mar 30 2014 I think we need a solid integer math module more than anything on
- bearophile (11/18) Mar 30 2014 I implemented many of those in my old D1 nonstandard library. I
- safety0ff (6/16) Mar 30 2014 You can have both, it's not less useful.
- bearophile (15/16) Mar 30 2014 I have several non-toy uses for the GCD, binomial, and the
- Russel Winder (12/29) Mar 31 2014 Finance, bioinformatics, signal processing, are some of the areas I know
- Marco Leise (139/143) Mar 30 2014 More or less real world stuff:
- Dominikus Dittes Scherkl (2/3) Mar 30 2014 isPowerOf2 { x => (x && !(x & (x-1))) }
- safety0ff (5/8) Mar 31 2014 The point is that it should be in the standard library instead of
- safety0ff (6/6) Mar 30 2014 I think we should get started with a Phobos integer module
- Chris Williams (32/37) Mar 19 2014 Here's a straightforward implementation, if you don't already
- bearophile (8/10) Mar 19 2014 RosettaCode has already several sieves in D. I am not doing this
- Chris Williams (24/50) Mar 19 2014 Well bummer, my quick and easy optimization broke the result for
- Ziad Hatahet (6/79) Mar 30 2014 Can't that be written as:

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

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

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

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

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

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

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

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

On Wednesday, 19 March 2014 at 01:44:16 UTC, bearophile wrote:Chris Williams: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.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 19 2014

- 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

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

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

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

Andrei Alexandrescu píše v St 19. 03. 2014 v 08:02 -0700:On 3/19/14, 7:07 AM, Marco Leise wrote:+1 it will be improvementI 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

On Wednesday, 19 March 2014 at 15:02:55 UTC, Andrei Alexandrescu wrote:On 3/19/14, 7:07 AM, Marco Leise wrote:I am against it. It gives nothing over dub and creates confusion.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

On 3/19/14, 8:45 AM, Dicebot wrote:On Wednesday, 19 March 2014 at 15:02:55 UTC, Andrei Alexandrescu wrote:Who'd be confused? Andrei

Mar 19 2014

On Wednesday, 19 March 2014 at 15:58:43 UTC, Andrei Alexandrescu wrote:Who'd be confused? AndreiUsers 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

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:Why was that never a problem for OpenGL ?Who'd be confused? AndreiUsers 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.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

On Wednesday, 19 March 2014 at 16:35:15 UTC, Marco Leise wrote:I know nothing about OpenGL but it was (and is) huge problem for Java.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 ?There is no point in implementing moderated category until it is not abused. If it will attract abuse, we will add moderation.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.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

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

On Wednesday, 19 March 2014 at 17:40:50 UTC, Andrei Alexandrescu wrote:On 3/19/14, 10:01 AM, Dicebot wrote: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 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 20 2014

On 3/20/14, 6:07 AM, Dicebot wrote:On Wednesday, 19 March 2014 at 17:40:50 UTC, Andrei Alexandrescu wrote:I think it should be pig easy to use, battle tested, and have some security mechanism in place. AndreiOn 3/19/14, 10:01 AM, Dicebot wrote: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 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 20 2014

On Wednesday, 19 March 2014 at 17:40:50 UTC, Andrei Alexandrescu wrote:

Mar 20 2014

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

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. […]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_winderPersonally 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

On 3/19/14, 9:06 AM, Dicebot wrote:On Wednesday, 19 March 2014 at 15:58: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. AndreiWho'd be confused? AndreiUsers 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

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. AndreiIf 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

On Wed, 2014-03-19 at 15:45 +0000, Dicebot wrote:On Wednesday, 19 March 2014 at 15:02:55 UTC, Andrei Alexandrescu wrote: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

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

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

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

On Wednesday, 19 March 2014 at 01:52:07 UTC, bearophile wrote: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?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

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

Am Wed, 19 Mar 2014 10:39:36 +0000 schrieb "bearophile" <bearophileHUGS lycos.com>:Meta: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. -- MarcoIf 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

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, bearophileI'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

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

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, bearophileI 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

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

On Sunday, 30 March 2014 at 23:40:14 UTC, bearophile wrote: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?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

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

On Mon, 2014-03-31 at 00:55 +0000, bearophile wrote:safety0ff: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.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.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

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

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

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: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.I find myself often reimplementing ilog2, isqrt, isPowerOf2,isPowerOf2 { x => (x && !(x & (x-1))) }

Mar 31 2014

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

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

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

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

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:if (p ^^ 2 > b) si = si.max(p ^^ 2 - b);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