mersenneforum.org Roots of 1 mod 2^n
 Register FAQ Search Today's Posts Mark Forums Read

 2010-11-15, 05:59 #1 fenderbender     Jul 2007 17 Posts Roots of 1 mod 2^n I'm writing code which is using a "rolling hash" over a stream of numbers. This mostly consists of having a running total T which is updated with each new value in the stream as it comes in, something similar to: T=0; while (v= getNewValueFromStream() ) { T=12345*(T+v); } This simple math is all done mod 2^32 or 2^64, the implicit size of the integer T. So in practice, T is a linear sum of all the stream values. The weight of the last value is 12345, the weight of the second to last value is 12345^2, the weight of the Nth to last value is 12345^N. This constant C (12345 in this example) is something I can choose. I'd like to choose it randomly (at runtime) so different hash functions can be used for different instances of my algorithm. Obviously this constant C needs to be ODD. If it wasn't, the powers of 2 would accumulate and after 32 or 64 (or fewer) values, the value of C^N mod 2^32 would end up 0 and we'd be hashing just the last values in the whole stream. Now my question is what conditions on C will give C^N the longest period before it repeats back to 1? In math terms, for what conditions of C gives C^n != 1 mod 2^32 for n=1..N for the largest N? I think this has to do with the roots of 1 mod 2^N but it's not as easy a rule as I thought. For example, mod 2^32, I get the following periods: C=3 N=2^30 C=5 N=2^30 C=7 N=2^29 C=9 N=2^29 C=11 N=2^30 C=13 N=2^30 C=15 N=2^28 C=17 N=2^28 C=19 N=2^30 In the end I want tp pick large random values of C which have a full period as long as possible.. 2^30 in this case. So.. back to my question. What defines the length of this period, and how can I efficiently pick random C which have the longest possible period? Thanks!
 2010-11-15, 12:22 #2 Gammatester     Mar 2009 2×19 Posts This looks a bit like a Linear Congruential Generator, if you write the code as T = C*T + C*v mod m = C*T + V mod m, with m=2^32, V=C*v. If V is a constant increment, Knuth (Seminumerical algorithms Ch. 3.2) and others give conditions for maximal length LCGs: 1. V and m are relatively prime, 2. C - 1 is divisible by all prime factors of m = 2^32 3. C - 1 is a multiple of 4 if m is a multiple of 4. This would solve your problem for constant v. Your table shows that even for C-1 a multiple of 4 a maximum period is not reached. So I guess you cannot have a definite answer without knowing a good deal about the v values.
 2010-11-15, 12:41 #3 science_man_88     "Forget I exist" Jul 2009 Dumbassville 100000101100012 Posts if v stays the same maybe you're right for the power of 2 idea but if v increases by 1 each time I don't see your point. T=2*(T+v) v=1 T=2*(0+1) = 2 v=2 T=2*(2+2) = 8 v=3 T=2*(8+3) = 22 ..... so it's only if v stays the same that I can easily see it following the powers of 2.
 2010-11-15, 13:30 #4 Gammatester     Mar 2009 468 Posts The point is that you cannot say much a about maximum period length if you do not know/list the v values. With C=12345 there are some obvious results: v=0 will always give T=0, i.e. a minum length period. If v is always even, T will allways even etc. Fenderbender's literal C^N = 1 mod 2^32 question has another answer: C must be a primitive element mod 2^32 (i.e. C mod 8 = 3 or 5) and the maximum period is the Carmichael lambda(2^32) = 2^30. But this holds only if all v=0 and the starting value T is odd.
2010-11-15, 13:59   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by Gammatester The point is that you cannot say much a about maximum period length if you do not know/list the v values. With C=12345 there are some obvious results: v=0 will always give T=0, i.e. a minum length period. If v is always even, T will allways even etc. Fenderbender's literal C^N = 1 mod 2^32 question has another answer: C must be a primitive element mod 2^32 (i.e. C mod 8 = 3 or 5) and the maximum period is the Carmichael lambda(2^32) = 2^30. But this holds only if all v=0 and the starting value T is odd.
if v=1 and C is even ? then statistically I think it has a 50% at each time it passes 2^32 in length that suggest 2*2^32 are needed to ensure a repeat of 1 mod 2^32 if so the period is likely 2^33.

Last fiddled with by science_man_88 on 2010-11-15 at 13:59

2010-11-15, 14:04   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by fenderbender I'm writing code which is using a "rolling hash" over a stream of numbers. This mostly consists of having a running total T which is updated with each new value in the stream as it comes in, something similar to: T=0; while (v= getNewValueFromStream() ) { T=12345*(T+v); } This simple math is all done mod 2^32 or 2^64, the implicit size of the integer T. So in practice, T is a linear sum of all the stream values. The weight of the last value is 12345, the weight of the second to last value is 12345^2, the weight of the Nth to last value is 12345^N. This constant C (12345 in this example) is something I can choose. I'd like to choose it randomly (at runtime) so different hash functions can be used for different instances of my algorithm. Obviously this constant C needs to be ODD. If it wasn't, the powers of 2 would accumulate and after 32 or 64 (or fewer) values, the value of C^N mod 2^32 would end up 0 and we'd be hashing just the last values in the whole stream. Now my question is what conditions on C will give C^N the longest period before it repeats back to 1? In math terms, for what conditions of C gives C^n != 1 mod 2^32 for n=1..N for the largest N? I think this has to do with the roots of 1 mod 2^N but it's not as easy a rule as I thought. For example, mod 2^32, I get the following periods: C=3 N=2^30 C=5 N=2^30 C=7 N=2^29 C=9 N=2^29 C=11 N=2^30 C=13 N=2^30 C=15 N=2^28 C=17 N=2^28 C=19 N=2^30 In the end I want tp pick large random values of C which have a full period as long as possible.. 2^30 in this case. So.. back to my question. What defines the length of this period, and how can I efficiently pick random C which have the longest possible period? Thanks!
I notice you bring up all but v again is there a reason is it pseudo-randomly picked ? is so then this question is made harder as v is also unknown and has influence on the C value needed.

 2010-11-15, 14:11 #7 science_man_88     "Forget I exist" Jul 2009 Dumbassville 8,369 Posts effectively for N times through the loop you calculate T as (C^N*T) +(C^N*v) but 3 of these variables are undefined to me, and hence the fourth as it changes based on those 3.
2010-11-15, 17:19   #8
WMHalsdorf

Feb 2005
Bristol, CT

33·19 Posts

Quote:
 Originally Posted by fenderbender For example, mod 2^32, I get the following periods: C=3 N=2^30 C=5 N=2^30 C=7 N=2^29 C=9 N=2^29 C=11 N=2^30 C=13 N=2^30 C=15 N=2^28 C=17 N=2^28 C=19 N=2^30 In the end I want tp pick large random values of C which have a full period as long as possible.. 2^30 in this case. So.. back to my question. What defines the length of this period, and how can I efficiently pick random C which have the longest possible period? Thanks!
You have to test C-1 for powers of 2.
To have the longest period the highest power of 2 will have to be 1.

Last fiddled with by WMHalsdorf on 2010-11-15 at 17:41 Reason: Only need to test C-1

2010-11-15, 19:05   #9
fenderbender

Jul 2007

17 Posts

Quote:
 Originally Posted by science_man_88 I notice you bring up all but v again is there a reason is it pseudo-randomly picked ? is so then this question is made harder as v is also unknown and has influence on the C value needed.
Actually what I expect to do is pick a random odd value for C and test it for whatever conditions are necessary to insure the longest period.
From empirical testing, half of all odd C give the maximum period so I shouldn't have to reject too many.

My post is to figure out just what those conditions on C are!

I can actually measure the period for the 2^32 case by a simple loop. It's not practical to test the period for 2^64.. it's about a week of computation.

2010-11-15, 19:09   #10
fenderbender

Jul 2007

17 Posts

Quote:
 Originally Posted by WMHalsdorf You have to test C-1 for powers of 2. To have the longest period the highest power of 2 will have to be 1.
This isn't sufficient.. if you look at the table of values I posted it doesn't match your conditions. C=13 has a power of 2^2 in C-1 but has the longest period. C=15 has a power of only 2^1 in C-1 but has a shorter period.

2010-11-15, 19:19   #11
Gammatester

Mar 2009

2×19 Posts

Quote:
 Originally Posted by WMHalsdorf You have to test C-1 for powers of 2. To have the longest period the highest power of 2 will have to be 1.
This is obviously wrong as the simplified version C=7 for 2^5 shows:
7 17 23 1

The sequence for 5 is:
5 25 29 17 21 9 13 1

and for 19:
19 9 11 17 3 25 27 1

These two samples have maximum length of 2^(5-2) = 8. I have already given the general solution for 2^m, m>=4. Choose C with C mod 8 = 3 or 5. Then the (maximum) length of the sequence is 2^(m-2).

 Similar Threads Thread Thread Starter Forum Replies Last Post Dubslow Miscellaneous Math 8 2012-12-13 21:35 Peter Hackman Math 2 2007-10-24 06:41 grandpascorpion Puzzles 4 2006-10-01 13:57 Numbers Math 16 2005-09-21 23:41 Annunaki NFSNET Discussion 7 2003-07-29 16:01

All times are UTC. The time now is 19:53.

Tue Oct 20 19:53:26 UTC 2020 up 40 days, 17:04, 1 user, load averages: 2.08, 1.86, 1.77