www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Example in the overview

reply R.Tenton <Tentresh web.de> writes:
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
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
parent reply R.Tenton <Tentresh web.de> writes:
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
parent reply bearophile <bearophileHUGS lycos.com> writes:
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
parent reply R.Tenton <Tentresh web.de> writes:
That would be nice.
May 09 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
R.Tenton:

 That would be nice.


http://d.puremagic.com/issues/show_bug.cgi?id=4164
May 09 2010
parent R.Tenton <Tentresh web.de> writes:
Thanks!
May 09 2010
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
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
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
parent reply Walter Bright <newshound1 digitalmars.com> writes:
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
next sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
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
parent bearophile <bearophileHUGS lycos.com> writes:
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
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
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))






1027

Bye,
bearophile
May 14 2010
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Walter Bright <newshound1 digitalmars.com> 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]


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
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
parent Walter Bright <newshound1 digitalmars.com> writes:
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