Hello! :]
I started reading your book the other day and I was wondering about this part. You mention some "mathematical feature of prime numbers and quadratic equations" which makes the skipping work, and I'm trying to understand why, but I'm not sure, if i got this right. It would be nice to know what the feature is called, so I have some clue for starting a search for more information. I didn't find anything particularly useful on goole, as most of what turned up was concerning roots of quadratics modulo primes.
So what i was thinking is:
If you don't want a sequence like
f(n+1) = (f(n) + c) mod p
to repeat before all values < p turned up, c and p have to be relatively prime e.g.:
c = 2, p = 5, f(0) = 3 gives you
3, 0, 2, 4, 1 and then it starts over.
c = 2, p = 4, f(0) = 3 gives you
3, 1 and then starts over.
But with a skip value being calculated as Skip = RandomA*members*members + RandomB*members + RandomC this won't always work out, I think.
Taking, for example, the numbers from the chapter:
members = 10, prime = 11
and suppose RandomA = 1, RandomB = 2, RandomC = 1
Then we get:
1*10*10 + 2*10 + 1 = 100 + 20 + 1 = 121
which has 11 as a factor. And now
nextMember += skip;
nextMember %= prime;
will always yield the same result (nextMember) as 121 % 11 is 0 thus breaking the algorithm and, even worse, resulting in an infinite loop in the GetNext() function, right?
Of course, it's not very likely to happen, especially with larger numbers, but it can.
And now I'm wondering if all this is correct, or if I'm just missing something, so I hope someone can help me out here :]
Really enjoying this book so far btw, I like it's approach!
[edit: typo and trying to get this a little bit more readable...]
I started reading your book the other day and I was wondering about this part. You mention some "mathematical feature of prime numbers and quadratic equations" which makes the skipping work, and I'm trying to understand why, but I'm not sure, if i got this right. It would be nice to know what the feature is called, so I have some clue for starting a search for more information. I didn't find anything particularly useful on goole, as most of what turned up was concerning roots of quadratics modulo primes.
So what i was thinking is:
If you don't want a sequence like
f(n+1) = (f(n) + c) mod p
to repeat before all values < p turned up, c and p have to be relatively prime e.g.:
c = 2, p = 5, f(0) = 3 gives you
3, 0, 2, 4, 1 and then it starts over.
c = 2, p = 4, f(0) = 3 gives you
3, 1 and then starts over.
But with a skip value being calculated as Skip = RandomA*members*members + RandomB*members + RandomC this won't always work out, I think.
Taking, for example, the numbers from the chapter:
members = 10, prime = 11
and suppose RandomA = 1, RandomB = 2, RandomC = 1
Then we get:
1*10*10 + 2*10 + 1 = 100 + 20 + 1 = 121
which has 11 as a factor. And now
nextMember += skip;
nextMember %= prime;
will always yield the same result (nextMember) as 121 % 11 is 0 thus breaking the algorithm and, even worse, resulting in an infinite loop in the GetNext() function, right?
Of course, it's not very likely to happen, especially with larger numbers, but it can.
And now I'm wondering if all this is correct, or if I'm just missing something, so I hope someone can help me out here :]
Really enjoying this book so far btw, I like it's approach!
[edit: typo and trying to get this a little bit more readable...]
The post was edited 1 time, last by powderedtoastman ().