Path: utzoo!attcan!uunet!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!swrinde!ucsd!rutgers!mephisto!bloom-beacon!eru!hagbard!sunic!news.funet.fi!funic!fuug!tuura!risto From: risto@tuura.UUCP (Risto Lankinen) Newsgroups: comp.lang.c Subject: Re: % operator (was Re: count of bits set in a long) Message-ID: <793@tuura.UUCP> Date: 2 Oct 90 08:17:08 GMT References: <37545@ut-emx.uucp> <3820@goanna.cs.rmit.oz.au> <34281@cup.portal.com> <2859@litchi.bbn.com> <51467@brunix.UUCP> <3417@gmdzi.gm Organization: Nokia Data Systems Oy Lines: 39 wittig@gmdzi.gmd.de (Georg Wittig) writes: >tac@cs.brown.edu (Theodore A. Camus) writes: >>However, 077 in octal is 63 in decimal, and I believe the following > ^^^^^^^^^ >>relationship is true : x % 63 = [(x % 64) + (x / 64)] % 63 > Does there exist a proof for that equation? Can it be found in > literature? Is the following true? > > x % n = (x%(n+1) + floor(x/(n+1))) % n (n != 0;n != -1) > > Do there exist similar "surprising" equations? Hi! Not in attempt to 'prove' anything, but ... Let 'x' be of form 'X*2^k + x' (where X and x are distinguished and x is less than 2^k). Subtract 'X*(2^k-1)' to get 'x+X' which will have the same remainder as the original formula, when divided by '2^k-1' . Were the X greater than 2^k-1 , the same procedure could be repeated until the remaining sum of 'hi- and lo-parts' becomes less than 2^k-1 This works in decimal base, too. For example, 147 MOD 9 = (14+7) MOD 9 = 21 MOD 9 = (2+1) MOD 9 = 3 . There's a similar formula for modulus '2^k+1' . By the way, when 'k=0' in '2^k-1' , this reduces to a 'x MOD 1' , which is how the parity bit is calculated in a binary number. Has anyone got more to tell about the mathematics involved in parity function? Terveisin: Risto Lankinen -- Risto Lankinen / product specialist *************************************** Nokia Data Systems, Technology Dept * 2 2 * THIS SPACE INTENTIONALLY LEFT BLANK * 2 -1 is PRIME! Now working on 2 +1 * replies: risto@yj.data.nokia.fi ***************************************