mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-11-15, 05:59   #1
fenderbender
 
fenderbender's Avatar
 
Jul 2007

17 Posts
Default 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!
fenderbender is offline   Reply With Quote
Old 2010-11-15, 12:22   #2
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2×19 Posts
Default

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.
Gammatester is offline   Reply With Quote
Old 2010-11-15, 12:41   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000101100012 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Old 2010-11-15, 13:30   #4
Gammatester
 
Gammatester's Avatar
 
Mar 2009

468 Posts
Default

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.
Gammatester is offline   Reply With Quote
Old 2010-11-15, 13:59   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by Gammatester View Post
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
science_man_88 is offline   Reply With Quote
Old 2010-11-15, 14:04   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by fenderbender View Post
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.
science_man_88 is offline   Reply With Quote
Old 2010-11-15, 14:11   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Old 2010-11-15, 17:19   #8
WMHalsdorf
 
WMHalsdorf's Avatar
 
Feb 2005
Bristol, CT

33·19 Posts
Default

Quote:
Originally Posted by fenderbender View Post
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
WMHalsdorf is offline   Reply With Quote
Old 2010-11-15, 19:05   #9
fenderbender
 
fenderbender's Avatar
 
Jul 2007

17 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
fenderbender is offline   Reply With Quote
Old 2010-11-15, 19:09   #10
fenderbender
 
fenderbender's Avatar
 
Jul 2007

17 Posts
Default

Quote:
Originally Posted by WMHalsdorf View Post
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.
fenderbender is offline   Reply With Quote
Old 2010-11-15, 19:19   #11
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2×19 Posts
Default

Quote:
Originally Posted by WMHalsdorf View Post
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).
Gammatester is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Extracting k-th roots mod m Dubslow Miscellaneous Math 8 2012-12-13 21:35
primtive roots mod p^2 Peter Hackman Math 2 2007-10-24 06:41
Perfect roots grandpascorpion Puzzles 4 2006-10-01 13:57
Primitive Roots Numbers Math 16 2005-09-21 23:41
What is the roots of NFS algorithm? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.