Re: [math-fun] Add 1 and reverse
Actually, I'd suggest tabulating C so that the "Add C and reverse" operation yields large period mod 2^m (C likely will depend upon m) That way you'd get useful random number generator components, at least on future machines featuring a fast reverse operation.
On 9/29/15, Warren D Smith <warren.wds@gmail.com> wrote:
Actually, I'd suggest tabulating C so that the "Add C and reverse" operation yields large period mod 2^m (C likely will depend upon m)
That way you'd get useful random number generator components, at least on future machines featuring a fast reverse operation.
--especially useful: large PRIME periods.
For (fixed width) add1 & reverse, most of the graph should consist of long strings. Imagine the number split into left & right halves. The left half propagates carries backwards, to the right; and the add1 is done on the leftmost bit. The add1 step counts in the two halves independently, until a carry propagates across the middle. Then it gets interesting. Odd & even lengths may have different behaviors, since the odd lengths have a center bit shared between the two halves. [hidden corollary: L=1 :-)] Rich ------ Quoting Warren D Smith <warren.wds@gmail.com>:
On 9/29/15, Warren D Smith <warren.wds@gmail.com> wrote:
Actually, I'd suggest tabulating C so that the "Add C and reverse" operation yields large period mod 2^m (C likely will depend upon m)
That way you'd get useful random number generator components, at least on future machines featuring a fast reverse operation.
--especially useful: large PRIME periods.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Indeed, the X := reverse( A*X + B ) operation (everything mod 2^w) strikes me as, quite possibly, a pretty good random generator, if the constants A and B are chosen correctly. A should be odd. (If A=even then the map is a 2-to-1-fold, or more-fold, uninvertible map and hence large periods cannot be expected.) With A=1, here are some max-period examples found by random trial. It empirically looks as though max possible period 2^w is achievable exactly when w is odd, (except also when w=2), and the C that accomplishes this empirically always is odd. [Which I now have forced in my search program so it can be twice as fast. It makes a lot of intuitive sense to me that odd C should be preferable, but I have no proof.] The values of C and the periods are in hexadecimal: Seeking C so that X := reverse(X+C) has large period mod 2^w. w=1 C=1 period=2 (max possible, trials=1) w=3 C=7 period=8 (max possible, trials=1) w=5 C=3 period=20 (max possible, trials=1) w=7 C=1 period=80 (max possible, trials=2) w=9 C=1DB period=200 (max possible, trials=3) w=11 C=2D7 period=800 (max possible, trials=31) w=13 C=1D73 period=2000 (max possible, trials=38) w=15 C=31A7 period=8000 (max possible, trials=65) w=17 C=21A3 period=20000 (max possible, trials=205) w=19 C=1F64B period=80000 (max possible, trials=2691) w=21 C=62D8D period=200000 (max possible, trials=292) w=23 C=7D9DDB period=800000 (max possible, trials=2105) w=25 C=1E40F47 period=2000000 (max possible, trials=2443) Theorem: if C works to yield max-period, then (-C) also works. Proof: Consider time-reversal. For general A and B, with A=odd, but B having unrestricted parity, it appears that max-period 2^w is achievable for every w>0, although examples are quite hard to find. Here are some max-period cases (again A,B,period in hexadecimal): Seeking A,B so that X := reverse(A*X+B) has large period mod 2^w. w=1 A=1 B=1 period=2 (max possible, trials=3) w=2 A=3 B=1 period=4 (max possible, trials=1) w=3 A=1 B=1 period=8 (max possible, trials=9) w=4 A=B B=8 period=10 (max possible, trials=16) w=5 A=1 B=1F period=20 (max possible, trials=12) w=6 A=3B B=14 period=40 (max possible, trials=64) w=7 A=23 B=68 period=80 (max possible, trials=38) w=8 A=55 B=75 period=100 (max possible, trials=433) w=9 A=1F7 B=DA period=200 (max possible, trials=154) w=10 A=381 B=15F period=400 (max possible, trials=605) w=11 A=223 B=34A period=800 (max possible, trials=1079) w=12 A=147 B=4D8 period=1000 (max possible, trials=12774) w=13 A=1183 B=129A period=2000 (max possible, trials=550) w=14 A=3897 B=274C period=4000 (max possible, trials=10047) w=15 A=7C0D B=3C9 period=8000 (max possible, trials=33331) w=16 A=4803 B=43F6 period=10000 (max possible, trials=29402) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
OK, the Mitchell/Smith/McCaughan theorem now shows when w=odd that X := reverse(X+1) (all mod 2^w) has period=2^w, and when w=even we get period=2*2^(w/2)-1. Empirically it seems like if w=odd then X := reverse(X+C), everything mod 2^w achieves period=2^w when the constant C is chosen randomly, with chance of the order of 2^(-0.49*w). The Theorem shows this chance is positive. Presumably the empirically fit value 0.49 really is 0.5? If w=even, then apparently period=2^w is unachievable even with the best choice of C; but by good choice of C, substantially greater period than by using C=1 is usually achievable (C and period in hexadecimal): w=2 C=3 period=3 w=4 C=9 period=B w=8 C=81 period=8F w=10 C=201 period=21F w=12 C=801 period=83F w=14 C=2001 period=207F w=16 C=8001 period=80FF and there seems to be a pattern here, doesn't there? Namely, when w=even and positive, C=1+2^(w-1) (which incidentally is palindromic) apparently causes period=2^(w-1)+2^(w/2)-1 which apparently is max possible. Meanwhile, when A and B are chosen randomly with A=odd, X := reverse(A*X+B), everything mod 2^w apparently achieves max period 2^w for each w>0, with positive chance of order 2^(-0.97*w), where I presume really 0.97 is 1? (We've only proven the chance positive when w=odd; but I also have example A,B for each w=1,2,3,...,20.)
For X := reverse(A*X+B), everything mod 2^w you get the same period from (A,B) as you get from (Ainverse, -B*Ainverse). Proof: consider time-reversal. And note Ainverse (mod 2^w) exists iff A is odd.
On 30/09/2015 15:29, Warren D Smith wrote:
OK, the Mitchell/Smith/McCaughan theorem now shows when w=odd that X := reverse(X+1) (all mod 2^w) has period=2^w, and when w=even we get period=2*2^(w/2)-1.
Careful! In the even case there are lots of orbits with different periods. That particular period is only for the orbit containing 0. (This has no impact, I think, on your very interesting conjectures about the generalized iteration.) -- g
Here are max-period examples for X := reverse(X+C) mod 2^w found by random trial (C & period in hexadecimal): w=3 C=7 period=8 (max possible, trials=1) w=5 C=3 period=20 (max possible, trials=1) w=5 C=5 period=20 (max possible, trials=4) w=5 C=1D period=20 (max possible, trials=2) w=7 C=5B period=80 (max possible, trials=1) w=7 C=7 period=80 (max possible, trials=3) w=7 C=79 period=80 (max possible, trials=4) w=9 C=17 period=200 (max possible, trials=2) w=9 C=10B period=200 (max possible, trials=4) w=9 C=1DB period=200 (max possible, trials=3) w=9 C=75 period=200 (max possible, trials=6) w=11 C=77B period=800 (max possible, trials=28) w=11 C=2D7 period=800 (max possible, trials=31) w=11 C=245 period=800 (max possible, trials=39) w=11 C=7D period=800 (max possible, trials=8) w=13 C=323 period=2000 (max possible, trials=74) w=13 C=1631 period=2000 (max possible, trials=39) w=13 C=1D73 period=2000 (max possible, trials=38) w=13 C=49 period=2000 (max possible, trials=55) w=15 C=65 period=8000 (max possible, trials=299) w=15 C=30A3 period=8000 (max possible, trials=30) w=15 C=31A7 period=8000 (max possible, trials=65) w=15 C=513 period=8000 (max possible, trials=77) w=17 C=6F1D period=20000 (max possible, trials=94) w=17 C=21A3 period=20000 (max possible, trials=205) w=19 C=1F64B period=80000 (max possible, trials=2691) w=21 C=62D8D period=200000 (max possible, trials=292) w=23 C=7D9DDB period=800000 (max possible, trials=2105) w=25 C=1E40F47 period=2000000 (max possible, trials=2443) w=27 C=69833D7 period=8000000 (max possible, trials=1678) w=29 C=14149C61 period=20000000 (max possible, trials=2461) w=31 C=45C4ABF7 period=80000000 (max possible, trials=3984)
Here are example A,B so that X := reverse( A*X + B ) mod 2^w has period=2^w (periods, A, B all in hexadecimal): w=1 A=1 B=1 period=2 (max possible, trials=3) w=2 A=3 B=1 period=4 (max possible, trials=1) w=3 A=5 B=3 period=8 (max possible, trials=9) w=3 A=5 B=1 period=8 (max possible, trials=5) w=4 A=B B=8 period=10 (max possible, trials=16) w=4 A=3 B=8 period=10 (max possible, trials=75) w=5 A=11 B=1B period=20 (max possible, trials=1) w=5 A=11 B=15 period=20 (max possible, trials=7) w=6 A=3B B=14 period=40 (max possible, trials=64) w=6 A=3D B=25 period=40 (max possible, trials=194) w=7 A=B B=8 period=80 (max possible, trials=97) w=7 A=23 B=68 period=80 (max possible, trials=38) w=8 A=D7 B=3A period=100 (max possible, trials=126) w=8 A=55 B=75 period=100 (max possible, trials=433) w=9 A=1F7 B=DA period=200 (max possible, trials=154) w=9 A=1DB B=66 period=200 (max possible, trials=94) w=10 A=381 B=15F period=400 (max possible, trials=605) w=10 A=32F B=86 period=400 (max possible, trials=344) w=11 A=223 B=34A period=800 (max possible, trials=1079) w=12 A=147 B=4D8 period=1000 (max possible, trials=12774) w=13 A=1183 B=129A period=2000 (max possible, trials=550) w=14 A=3897 B=274C period=4000 (max possible, trials=10047) w=15 A=7C0D B=3C9 period=8000 (max possible, trials=33331) w=16 A=4803 B=43F6 period=10000 (max possible, trials=29402) w=17 A=BCDB B=19DB8 period=20000 (max possible, trials=2615) w=18 A=5307 B=A926 period=40000 (max possible, trials=700002) w=19 A=3467F B=6C5E0 period=80000 (max possible, trials=823613) w=20 A=96F5D B=12BB1 period=100000 (max possible, trials=611378) for w=21, the only example I know is A=B=1 (and trivial modifications) proved here earlier by Mitchell/McCaughan. But A=1178A1, B=17671E yields period=1FFFFF which is only 1 short. (Puzzle: find the unique fixpoint X.) There also are other interesting binary iterations mod 2^w about which we can ask similar questions. For example, Y := A*X; X := Y XOR (Y >> B); where >> is the shift right operator, 0<B<w, and A is odd. For a simpler example, simple enough to prove theorems about, Y := C +- X; X := Y XOR (Y>>B); Their generalization is Y := C + A*X; X := Y XOR (Y>>B);
participants (3)
-
Gareth McCaughan -
rcs＠xmission.com -
Warren D Smith