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

- R.Tenton <Tentresh web.de> May 08 2010
- bearophile <bearophileHUGS lycos.com> May 08 2010
- R.Tenton <Tentresh web.de> May 09 2010
- bearophile <bearophileHUGS lycos.com> May 09 2010
- R.Tenton <Tentresh web.de> May 09 2010
- bearophile <bearophileHUGS lycos.com> May 09 2010
- R.Tenton <Tentresh web.de> May 09 2010
- Walter Bright <newshound1 digitalmars.com> May 14 2010
- bearophile <bearophileHUGS lycos.com> May 14 2010
- Walter Bright <newshound1 digitalmars.com> May 14 2010
- Ary Borenszweig <ary esperanto.org.ar> May 14 2010
- bearophile <bearophileHUGS lycos.com> May 14 2010
- bearophile <bearophileHUGS lycos.com> May 14 2010
- "Simen kjaeraas" <simen.kjaras gmail.com> May 14 2010
- "Steven Schveighoffer" <schveiguy yahoo.com> May 14 2010
- Walter Bright <newshound1 digitalmars.com> May 14 2010

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: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

It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]

May 14 2010

Walter Bright wrote:bearophile wrote: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

It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]

A small observation: count +=1 is performed for i = 0, hmmm...

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:pr = (x for x in xrange(2,8191) if all(x % i for i in xrange(2,x))) len(list(pr))

Bye, bearophile

May 14 2010

Walter Bright <newshound1 digitalmars.com> wrote:bearophile wrote:Walter Bright:Are you sure? What's the mistake in the code?

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

It's been printing 1899 primes since the 80's. Just for fun, google [sieve of eratosthenes 1899 primes]

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? -- Simen

May 14 2010

On Fri, 14 May 2010 19:37:58 -0400, Walter Bright <newshound1 digitalmars.com> wrote: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?

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

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