Date: Wed, 25 Jun 2003 02:06:23 +0200 From: Simon Barner <barner@in.tum.de> To: Matthew Dillon <dillon@apollo.backplane.com> Cc: Tim Kientzle <kientzle@acm.org> Subject: Re: Page Coloring Defines in vm_page.h Message-ID: <20030625000623.GB2291@zi025.glhnet.mhn.de> In-Reply-To: <200306242211.h5OMBb12095342@apollo.backplane.com> References: <20030624111942.GO31354@spc.org> <3EF8900A.6030803@acm.org> <200306242211.h5OMBb12095342@apollo.backplane.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030625000623.GB2291>