www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4164] New: sieve Sample D Program

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4164

           Summary: sieve Sample D Program
           Product: D
           Version: future
          Platform: All
               URL: http://www.digitalmars.com/webnews/newsgroups.php?art_
                    group=digitalmars.D.learn&article_id=19692
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: www.digitalmars.com
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



R. Tenton in D.learn reports that the Sample D Program (sieve.d) at the bottom
of this page gives a wrong result:
http://digitalmars.com/d/2.0/overview.html

I suggest to replace it with this code that gives a correct result and shows D2
foreach (tested with DMD 2.043):


import std.stdio: writefln;

int sieve(int pmax) {
    if (pmax < 2)
        return 0;

    auto isPrime = new bool[pmax]; // fist initialization
    isPrime[] = true; // second initialization

    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() {
    enum int m = 8191;
    writefln("Primes in [2 .. %d) = %d", m, sieve(m));
}


In 2 .. 8191 there are 1027 primes, not counting 8191.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 09 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4164


Walter Bright <bugzilla digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugzilla digitalmars.com



16:30:47 PDT ---
Are you sure it gives the wrong answer? I've seen this code for 25 years.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 14 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4164


Steven Schveighoffer <schveiguy yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schveiguy yahoo.com
            Summary|sieve Sample D Program      |sieve Sample D Program --
                   |                            |need documentation for
                   |                            |array representation



20:38:19 PDT ---
The issue is there is no documentation.  The array actually represents the
values 3 to 16383 inclusive, with a stride of 2.

i.e. index 0 represents the number 3, index 1 represents the number 5.  This
relationship can be seen in the prime = i + i + 3 line.

With that in mind, the code is correct, it's just confusing :)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 14 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4164




21:45:48 PDT ---
Steven wrote in the n.g.:

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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 14 2010