From owner-freebsd-hackers@FreeBSD.ORG Tue Jun 24 17:06:26 2003 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 92C7837B401 for ; Tue, 24 Jun 2003 17:06:26 -0700 (PDT) Received: from mailout.informatik.tu-muenchen.de (mailout.informatik.tu-muenchen.de [131.159.0.5]) by mx1.FreeBSD.org (Postfix) with ESMTP id 8D07C43F85 for ; Tue, 24 Jun 2003 17:06:25 -0700 (PDT) (envelope-from barner@in.tum.de) Received: by zi025.glhnet.mhn.de (Postfix, from userid 1000) id B7B633822F; Wed, 25 Jun 2003 02:06:23 +0200 (CEST) Date: Wed, 25 Jun 2003 02:06:23 +0200 From: Simon Barner To: Matthew Dillon Message-ID: <20030625000623.GB2291@zi025.glhnet.mhn.de> References: <20030624111942.GO31354@spc.org> <3EF8900A.6030803@acm.org> <200306242211.h5OMBb12095342@apollo.backplane.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200306242211.h5OMBb12095342@apollo.backplane.com> User-Agent: Mutt/1.5.4i X-Virus-Scanned: by amavisd-new at informatik.tu-muenchen.de cc: hackers@freebsd.org cc: Tim Kientzle Subject: Re: Page Coloring Defines in vm_page.h X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 25 Jun 2003 00:06:26 -0000 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