Page Coloring Defines in vm_page.h

[Simon Barner]

Hi,

> :Ummmm....  Actually, Matt, the property you've stated is much more
> :common than you seem to believe.  If you generate a sequence
> :    N = ( N + Stride ) % ArraySize
> :then you will visit every element of (0 ... ArraySize-1) as long as
> 
>     I was just answering a question.  Most people aren't interested in that
>     level of detail (or, if they are, I'm sure Terry would happily chime in),
>     they just want to know the purpose.

I admit, this has nothing to do with FreeBSD, but this thread aroused my
interest ...

Theorem (informal version)
   For every array length n and every stride p, that has no common
   divisors with n (apart from 1), the function
   
   f_{i+1} = f_i + p mod n
   
   will generated a sequence that will visit very element of
   {0, ..., n-1}.

Since this is a tail recursion, one can also write:

f_i = i*p mod n

Theorem (formal version):
   For every n, p in Z, gcd (n, p) = 1 the function
   
   f: Z_n -> Z_n
   f: i |-> i*p mod n
   
   is a bijection.
   
Proof:
   f is a surjection (we can choose every i in {0, ..., n-1} we want to).
   
   f is a injection.
   
   Proof by contradiction. Let's assume that f is not an injection, i.e.
   there exist j != k mod n such that
   
   f (j) = f (k) mod n  <=>
   j*p   = k*p mod n
   
   By definition this means, that there exists t, such that
   
   j*p - k*p = t*n  <=>
   (j-k)*p   = t*n
   
   Since p and n are relatively prime, this condition can only hold if
   (j-k) = s*n, which is a contradiction of our assumption that
   j != k mod n.
   
   Hence, f is a bijection.

Since array lengths, that are powers of 2, are relatively prime to every
odd number, every stride apart from 2 will work.

Regards,
 Simon