Bug 4164 – sieve Sample D Program -- need documentation for array representation
Status
RESOLVED
Resolution
FIXED
Severity
normal
Priority
P2
Component
dlang.org
Product
D
Version
D2
Platform
All
OS
All
Creation time
2010-05-09T04:43:00Z
Last change time
2015-06-09T05:13:48Z
Assigned to
nobody
Creator
bearophile_hugs
Comments
Comment #0 by bearophile_hugs — 2010-05-09T04:43:07Z
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.
Comment #1 by bugzilla — 2010-05-14T16:30:47Z
Are you sure it gives the wrong answer? I've seen this code for 25 years.
Comment #2 by schveiguy — 2010-05-14T20:38:19Z
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 :)
Comment #3 by bugzilla — 2010-05-14T21:45:48Z
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.
Comment #4 by lt.infiltrator — 2014-03-18T22:59:45Z