wittig@gmdzi.gmd.de (Georg Wittig) (10/01/90)
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? -- Georg Wittig GMD-Z1.IT | wittig@gmdzi.gmd.de | "Freedom's just another word P.O. Box 1240 | | for nothing left to lose" D-5205 St. Augustin 1 | | (Kris Kristofferson) West Germany | (+49) 2241 14-2294 |
bs@linus.mitre.org (Robert D. Silverman) (10/01/90)
In article <3417@gmdzi.gmd.de> 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 Here's a simple, well known trick for computing x mod (2^n-1) when x > 0. If x is less than 0, make it positive first, then negate the final result. let x = a*2^n + b, that is partition x into lower and upper n bits. Then: x = a*(2^n-1) + a + b So: x mod (2^n-1) = a + b. Let mask[n] be a mask representing the lowest n bits all lit. Then we have x mod (2^n-1) = (x & mask[n]) + (x >> n) This is one add, one logical bitwise and, and one shift. -- Bob Silverman #include <std.disclaimer> Mitre Corporation, Bedford, MA 01730 "You can lead a horse's ass to knowledge, but you can't make him think"
djh@xipe.osc.edu (David Heisterberg) (10/01/90)
In article <3417@gmdzi.gmd.de> 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? It should hold for any n,m relatively prime. x % n = (x % m + x / m) % n <=> x = k * n + (x % m + x / m) <=> x % m = k * n % m + x % m % m + x / m % m [x % m % m = x % m] <=> k * n % m + x / m % m = 0 <=> k * n + l * m = -(x / m) k' * n + l' * m = 1 has solutions in integers if (n,m) = 1, let k = -(x / m) * k', l = -(x / m) * l'. Corrections and improvements welcome. -- David J. Heisterberg djh@osc.edu And you all know The Ohio Supercomputer Center djh@ohstpy.bitnet security Is mortals' Columbus, Ohio 43212 ohstpy::djh chiefest enemy.
karl@haddock.ima.isc.com (Karl Heuer) (10/02/90)
In article <985@sunc.osc.edu> djh@xipe.osc.edu (David Heisterberg) writes: >In article <3417@gmdzi.gmd.de> wittig@gmdzi.gmd.de (Georg Wittig) writes: >>Is the following true? >> x % n = (x%(n+1) + floor(x/(n+1))) % n (n != 0;n != -1) > >It should hold for any n,m relatively prime. [Using m for n+1] Counterexample: (n=10, m=13, x=15): x % 10 = 5 != 3 = (x%13 + x/13) % 10 The correct generalization is x % n = (x%m + (x/m)*(m%n)) % n which reduces to the original identity when m%n = 1. Proof of generalization: this is just the identity x = (x/m * m + x%m) reduced modulo n, with m replaced by the equivalent m%n. (There's no need for m and n to be relatively prime, either.) Karl W. Z. Heuer (karl@kelp.ima.isc.com or ima!kelp!karl), The Walking Lint
pejn@wolfen.cc.uow.oz (Paul Nulsen) (10/02/90)
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? The answers are: yes; yes; yes and I suppose yes (all qualified a little). The proof follows from modular arithmetic. It is not difficult to show that the normal arithmetic operations (addition, subtraction and multiplication) are "preserved" under modular arithmetic, so that, for example, for integers a, b and non-zero n: ((a modulo n) * (b modulo n) modulo n) = (a * b) modulo n Now for any integer a a = (n + 1) * (a / (n + 1)) + a % (n + 1) so, provided that, (n + 1) modulo n = 1, we can just apply the modulo to both sides to get a modulo n = ((n + 1) * (a / (n + 1)) + a % (n + 1)) modulo n = (((n + 1) * (a / (n + 1))) modulo n + (a % (n + 1)) modulo n) modulo n = ((1 * (a / (n + 1))) modulo n + (a % (n + 1)) modulo n) modulo n = (a / (n + 1) + a % (n + 1)) modulo n (note that the division is not done in modular arithmetic). Usually, a modulo n = a % n, so that this is the result. I haven't tried to be too rigorous, but you can see where this result can fail in practice. Basically, you are safe if all the numbers are positive, and all bets are off if n is negative (usually (n + 1) modulo n != 1 if n is negative). Other cases will be machine dependent. As to related surprising results, number theory is full of them. A direct application of this result (n = 9) is the well known rule that the sum of the digits of a number divisible by 9 is divisible nine. Paul Nulsen pejn@wolfen.cc.uow.edu.au
risto@tuura.UUCP (Risto Lankinen) (10/02/90)
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 ***************************************
risto@tuura.UUCP (Risto Lankinen) (10/02/90)
Oops! *JUST* having sent the article claiming that Parity(x) would be equal to Mod(x,1) , I made a second thought. It is not so, since the result of the algorithm I showed will be '1' for any 'x!=0' because no two positive numbers yield zero when added one another. 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 ***************************************
karl@haddock.ima.isc.com (Karl Heuer) (10/09/90)
In article <121784@linus.mitre.org> bs@gauss.UUCP (Robert D. Silverman) writes: >Here's a simple, well known trick for computing x mod (2^n-1) when x > 0. >let x = a*2^n + b, that is partition x into lower and upper n bits... Note the unstated assumption that x is at most 2n bits wide. This wasn't true in the original context. It can be fixed by iterating the procedure--in fact this is where that mod came from in the first place: it replaces one or two folding operations in the modless form of the algorithm. (Presumably the original algorithm was being optimized for codespace instead of time, or was being done on a machine where mod was cheap.) Karl W. Z. Heuer (karl@kelp.ima.isc.com or ima!kelp!karl), The Walking Lint