Hi,

I am experimenting with the PrimeSearch code-bit and I have modified it so that the a, b, and c integers used in the constructor are "really pseudo-random". (I have simply added a CRandom member, randomized it in every call to the constructor and get a, b, and c by assigning them to random.random(13) + 1 (or 7, or 5, respectively)).

Problem is now, that for a set of 10 numbers, I often get the sequence:

10, 9, 8, 7, 6, 5, 4, 3, 2, 1

another favorite (albeit less frequently) seems to be:

2, 3, 4, 5, 6, 7, 8, 9, 10, 1

Is this rather "unshuffled" ordering a problem of the algorithm itself? Could my modifications have lead to the problem (I checked CRandom: those numbers _are_ pseudo random)? What can I do to further enhance entropy?

Thanks for any help!
Philipp

P.s.: Oh and: FANTASTIC book!! I think, I'll buy another copy, so that I can read it twice (and I'm going to tell all my friends --- wait... What friends, hmmm.... ---- Just kidding! Great book!)

P.p.s.: And another thing (I am usually typing faster than I think---that often kills me...): Mr. Mike, you are saying "why use -1 as bad flag when you can have something as elegant as an Optional class?" (or something to that effect) and then you are using -1 as return value if PrimeSearch::GetNext fails?!?! -- Talk about inconsistencies... [irony]And I am sure I am the first to notice and you have never heard of that before...[/irony]

Hmmmm... But in the original code, a, b, and c are defined as follows:

a = (rand() % 13) + 1;
b = (rand() % 7) + 1;
c = (rand() % 5) + 1;

(from memory; I have no access to my copy right now).

So --- they are not prime numbers, are they?
a is from 1 through 13 inclusive, but not neccesarily a prime number...

Anyway: I'll give it a try and keep them prime... Thanks!

Embarassed??? Why??? *looks puzzled* -- There's hardly ever a need to be; certainly not for trying to help.

I did try different random seeds.
My (modified part of the) constructor of PrimeSearch looks like this (m_random is an instance of CRandom):

...
m_random.randomize();
a = m_random.random(13) + 1;
b = m_random.random(7) + 1;
c = m_random.random(5) + 1;
...

This _should_ set the random seed each time the constructor gets called, right?

I call the constructor in my main 20 times and I often get the unshuffled list (say maybe 7 or 8 times, and an additional 3 to 4 times the 2, 3, 4..., 1)

Now I'm even more puzzled...

I just tried the code on a different computer. And what I have found out now is that "time(NULL)" _always_ returns the _same_ number on that computer... That is: What I get here is a sufficiently shuffled list, but _always_ the same. Thus, at least at this computer, CRandom does not work either! If I use rand() in the code, I always get _one_ list, but this list is pretty shuffled. If I use CRandom, I get the list shown at the end of this post...
Conclusion: there seems to be something wrong with time(NULL) --- at least on this computer. (Yes, I included <time.h>).

Just to make sure that I don't do something horribly wrong, here is the constructor part of CRandom in all its beauty (I downloaded the source code from the forum and made my modifications---next thing to try: Run it without my modifications).

Here's my main function:

int main() {
for (int i = 0; i < 20; i++) {
printf("---%d---\n", (unsigned int) time(NULL));
CPrimeSearch cps(20);
char result[256];
strcpy(result, "");
int number;
while ((number = cps.getNext()) != -1) {
char help[10];
sprintf(help, "%d, ", number);
strcat(result, help);
}
result[strlen(result) - 2] = 0;
printf("%s\n", result);
}
}

and the constructor of CPrimeSearch:

...
m_maxElements = elements;

srand((unsigned int) time(NULL));
int a = (rand() % 13) + 1;
int b = (rand() % 7) + 1;
int c = (rand() % 5) + 1;

m_skip = (a * m_maxElements * m_maxElements) + (b * m_maxElements) + c;
m_skip &= ~0xc0000000;

restart();
...

Result:

---1114874832---
2, 4, 6, 8, 10, 12, 14, 16, 18, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 0

(repeat 20 times...)

Strange, isn't it...

No need to apologize: I am rather busy myself...
But what I found out is that I've been stupid...
time(NULL) returns the number of _seconds_ passed since some day in 1970... Obviously, the snippet cited above runs much faster than a second, thus the seed is always the same.
Ok. So much for that problem, but still: Several misteries remain (for example: Why do all the PrimeSearch numbers end with 0??). I'll investigate further and will post any results here...

I rephrase: "Why do all PrimeSearch numbers end with 0" was a bit of nonsense. What I meant was that I got the following number sequences when I called PrimeSearch:

7 6 2 3 8 4 9 5 1 0
8 2 6 3 1 5 4 9 7 0
. . . 0
. . . 0
etc.

And the reason for it (yes, I found it finally!) is that the currentPosition variable in PrimeSearch is never initialized! It is first used in "GetNext" but never assigned a value before. Thus, it is always 0 at the first call and so I get those rather unshuffled series. I still don't fully understand why 0 is _always_ the last number, no matter which length I specify in PrimeSearch, but if I initialize currentPosition with a random value in the constructor (ranging from 0 to elements) it works just fine.

So, to sum it up, I have modified PrimeSearch in three ways:

- First I replaced the -1 return value with the Optional class; trivial.
- Second, I now add a static CRandom number generator to the class and initialize it with a random seed. The initialization happens only once and so there's no problem.
- Third, I initialize currentPosition with a random number from the above CRandom number generator.

Now it works without any problems.

Thanks for your hints and ideas, guys!