## digitalmars.D.learn - Example in the overview

- R.Tenton (33/33) May 08 2010 At the very bottom of http://digitalmars.com/d/2.0/overview.html
- bearophile (20/20) May 08 2010 D2 code, the 8191 too is counted:
- R.Tenton (3/3) May 09 2010 The sieve algorith was not my problem. I wanted to point out that
- bearophile (5/6) May 09 2010 The right place to report errors in the docs is the bugzilla...
- R.Tenton (1/1) May 09 2010 That would be nice.
- bearophile (2/3) May 09 2010 http://d.puremagic.com/issues/show_bug.cgi?id=4164
- R.Tenton (1/1) May 09 2010 Thanks!
- Walter Bright (8/13) May 14 2010 It is a translation of the C benchmark that was common in the 1980's. Th...
- bearophile (9/10) May 14 2010 This is the code in the Overview, it prints 1899:
- Walter Bright (3/14) May 14 2010 It's been printing 1899 primes since the 80's. Just for fun, google [sie...
- Ary Borenszweig (2/19) May 14 2010 A small observation: count +=1 is performed for i = 0, hmmm...
- bearophile (5/6) May 14 2010 It lacks unit tests. A basic unit testing can catch that bug.
- bearophile (6/10) May 14 2010 You are right, isn't life fun? :-)
- Simen kjaeraas (10/22) May 14 2010 I wonder if that has to with there being 1899 primes in 3..16384.
- Steven Schveighoffer (15/22) May 14 2010 I think the issue is that the expectation is that array index x represen...
- Walter Bright (2/3) May 14 2010 Well, I did add your explanation to the bugzilla report! Thanks.

At the very bottom of http://digitalmars.com/d/2.0/overview.html there is an example implementation of the Eratosthenes' sieve. That code is broken! It counts 1899 prime numbers, while there are only 1028 primes in the interval [1,8191]! What is the outermost for loop good for? This example is just screwed up! And this was the first D source I ever encountered... I am referring to the following: /* Sieve of Eratosthenes prime numbers */ import std.stdio; bool[8191] flags; int main() { int i, count, prime, k, iter; writefln("10 iterations"); for (iter = 1; iter <= 10; iter++) { count = 0; flags[] = 1; for (i = 0; i < flags.length; i++) { if (flags[i]) { prime = i + i + 3; k = i + prime; while (k < flags.length) { flags[k] = 0; k += prime; } count += 1; } } } writefln("%d primes", count); return 0; }

May 08 2010

D2 code, the 8191 too is counted: import std.stdio: writeln; int sieve(int m) { auto isPrime = new bool[m + 1]; isPrime[] = true; int count; foreach (i; 2 .. isPrime.length) { if (isPrime[i]) { count++; for (int k = i * 2; k < isPrime.length; k += i) isPrime[k] = false; } } return count; } void main() { writeln(sieve(8191)); } Bye, bearophile

May 08 2010

The sieve algorith was not my problem. I wanted to point out that the example is totally screwed up, so it would be corrected. Or is this the wrong place to ask?

May 09 2010

R.Tenton:Or is this the wrong place to ask?The right place to report errors in the docs is the bugzilla... But if you don't want to subscribe some people here can do it for you. Bye, bearophile

May 09 2010

R.Tenton:That would be nice.http://d.puremagic.com/issues/show_bug.cgi?id=4164

May 09 2010

R.Tenton wrote:At the very bottom of http://digitalmars.com/d/2.0/overview.html there is an example implementation of the Eratosthenes' sieve. That code is broken! It counts 1899 prime numbers, while there are only 1028 primes in the interval [1,8191]!Are you sure? What's the mistake in the code?What is the outermost for loop good for?It is a translation of the C benchmark that was common in the 1980's. The outermost loop is to make it take longer so the test can be timed better. The original: http://home.iae.nl/users/mhx/nsieve.c The more common later version: http://www.paxcompiler.com/js_sieve.htm

May 14 2010

Walter Bright:Are you sure? What's the mistake in the code?This is the code in the Overview, it prints 1899: http://codepad.org/lzRtggEL This is the code I have suggested in bugzilla, it prints 1027: http://ideone.com/D9ZqQ Wolfram Alpha says they are 1027 (I have left out the last number because Alpha uses a closed interval) http://www.wolframalpha.com/input/?i=primes+in+2+..+8190 Bye, bearophile

May 14 2010

bearophile wrote:Walter Bright:It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]Are you sure? What's the mistake in the code?This is the code in the Overview, it prints 1899: http://codepad.org/lzRtggEL This is the code I have suggested in bugzilla, it prints 1027: http://ideone.com/D9ZqQ Wolfram Alpha says they are 1027 (I have left out the last number because Alpha uses a closed interval) http://www.wolframalpha.com/input/?i=primes+in+2+..+8190

May 14 2010

Walter Bright wrote:bearophile wrote:A small observation: count +=1 is performed for i = 0, hmmm...Walter Bright:It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]Are you sure? What's the mistake in the code?This is the code in the Overview, it prints 1899: http://codepad.org/lzRtggEL This is the code I have suggested in bugzilla, it prints 1027: http://ideone.com/D9ZqQ Wolfram Alpha says they are 1027 (I have left out the last number because Alpha uses a closed interval) http://www.wolframalpha.com/input/?i=primes+in+2+..+8190

May 14 2010

Ary Borenszweig:A small observation: count +=1 is performed for i = 0, hmmm...It lacks unit tests. A basic unit testing can catch that bug. Recently I have ready a quote: "If it has no unit tests then it's broken". Experience shows me that this is more often true than false. Bye, bearophile

May 14 2010

Walter Bright:It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]You are right, isn't life fun? :-) But there is little double the result is:1027 Bye, bearophilepr = (x for x in xrange(2,8191) if all(x % i for i in xrange(2,x))) len(list(pr))

May 14 2010

Walter Bright <newshound1 digitalmars.com> wrote:bearophile wrote:I wonder if that has to with there being 1899 primes in 3..16384. http://www.wolframalpha.com/input/?i=primes+in+2+..+16384 An implementation of just that is what I found most of the time, owing back to "A High-Level Language Benchmark" by Jim Gilbreath, in BYTE Magazine, september 1981, pages 180-198. Sadly, I cannot seem to find a version of the original article online. Anyone know of one, that we may get to the bottom of this? -- SimenWalter Bright:It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]Are you sure? What's the mistake in the code?This is the code in the Overview, it prints 1899: http://codepad.org/lzRtggEL This is the code I have suggested in bugzilla, it prints 1027: http://ideone.com/D9ZqQ Wolfram Alpha says they are 1027 (I have left out the last number because Alpha uses a closed interval) http://www.wolframalpha.com/input/?i=primes+in+2+..+8190

May 14 2010

On Fri, 14 May 2010 19:37:58 -0400, Walter Bright <newshound1 digitalmars.com> wrote:R.Tenton wrote:I think the issue is that the expectation is that array index x represents the number x. But it doesn't seem that way. the i + i + 3 is very odd indeed. If we consider each index, it means the first element represents 0 + 0 + 3 = 3; The second element represents 1 + 1 + 3 = 5; The third element represents 2 + 2 + 3 = 7; So it looks like the numbers represented by the array actually go from 3 to (8190 + 8190 + 3) or 16383. According to Wolfram Alpha, the number of primes in that list is 1899 http://www.wolframalpha.com/input/?i=primes+in+3+..+16383 A comment to explain the representation of the array may be good. -SteveAt the very bottom of http://digitalmars.com/d/2.0/overview.html there is an example implementation of the Eratosthenes' sieve. That code is broken! It counts 1899 prime numbers, while there are only 1028 primes in the interval [1,8191]!Are you sure? What's the mistake in the code?

May 14 2010

Steven Schveighoffer wrote:A comment to explain the representation of the array may be good.Well, I did add your explanation to the bugzilla report! Thanks.

May 14 2010