6 : MacWilliams M

Size: px

Start display at page:

Download "6 : 28 6.1...................... 28 6.2.......................... 30 6.3.......................... 31 6.4 MacWilliams........................ 32 6.5 M"

1 LCG GFSR TGFSR Mersenne Twister

5 Mersenne Twister.......................... 13 4 14 4.1............................ 14 4.2............................. 16 4.3..................... 17 5 23 5.

2 6 : MacWilliams MacWilliams v k

5.1...................... 33 6.5.2................. 37 7 40 7.1 v k................ 40 7.2........................ 43 1 1.

3 1.2 ( ) 1943 [4] Lehmer ( ) M, a, c x j+1 := ax j + c mod M (1) x 0 mod M M (Linear Congruential Generator, LCG) 1.2. M =7,a =3,c =0 x 0 =4 x j 4, 5, 1, 3, 2, 6, 4, 5, c =0,x 0 =0 x j 0 3

4 1. 4/7 M M 1.4. M =2 n, a = 1, c = M M =2 31 1, a = 16807, c =0 0 M 1 M LCG M 0,...,M 1 1 M 1 6 0,1,2,3,4,5 1 M, a, c, x 0 M M LCG LCG 1 M M 8 F 2 := {0, 1} 1+1=0 ( 4.1 ) F m 2 m m m A x j+1 := Ax j 4

..,M 1 1 M 1 6 0,1,2,3,4,5 1 M, a, c, x 0 M M 1 1.

5 A LCG 1.5. LCG( 1.1) M 1. (c, M) =1(c M ) 2. M a 1 3. M 4 a S, O f : S S s 0 S o : S O S S f S f o 100 s i+1 = f(s i ) s 0,s 1,s 2,... o(s 0 ),o(s 1 ),o(s 2 ),... 5

6 2.2. S := Z/M, f(x) :=10x mod M, o(x) := [10x/M] s 0 /M Z/M := {0, 1,...,M 1} M Z/M S #(S) 2.4. x 1,x 2,... ( ) p N n N x n+p = x n (2) (2) p (period) (2) p x 1,x 2,... n 0 N x n0,x n0 +1,x n0 +2,... n 0 x 1,...,x n0 1 x n0,x n0 +1,x n0 +2,.... ( 2.3 ) s 0,s 1,... S n #(S),p 1 s n = s n p n o(s n ) o(s n ) s n

7 2.6. 2, π 2.7. #(S) s i S 5. S {s i } i=0,1,2,... f 2.8. LCG( 1.1 ) M 6. (1) M a 1 mod M M 1 a M 1 M (Z/M) M CPU {0, 1} 32 := {(x 31,x 30,...,x 0 ) x i =0 1} w W := {0, 1} w CPU W W ( ) w =6 7

(1) M a 1 mod M M 1 a M 1 M (Z/M) M 1 3 3.

8 AND (C &) & = OR (C ) = EXOR (C ˆ) 1+1= = F 2 := {0, 1} 1+1=0 2 W F 2 w F w 2 EXOR 3.2 LCG 1.1 LCG x j+1 := ax j + c mod M 1990 ANSI-C rand LCG a = , c = 12345, M =2 31 M C static unsigned long x=3; /* initial seed */ unsigned long rand(void) { x = x * ; x &= 0x7fffffff; /* mod 2^31 */ return x; } 8

1 LCG x j+1 := ax j + c mod M 1990 ANSI-C rand LCG a = 1103515245, c = 12345, M =2 31 M C static

9 C mod m 2 m xyz : ANSI C rand() 2: GFSR 1 =w F 2 w F w 2 m>0 n> x j+n := x j+m + x j (j =0, 1,...) (3) Generalized Feedbacked Shiftregister (GFSR) x j+3 := x j+1 + x j (j =0, 1,...) 9

3 GFSR 1 =w F 2 w F w 2 m>0 n> x j+n := x j+m + x j (j =0,

10 n 1 (n, m) (3) n n 3.2. W g : W n W x 0,...,x n 1 W x j+n = g(x j+n 1,...,x j ) W W n 3.3. n S := W n, f(x j+n 1,...,x j ) = (g(x j+n 1,...,x j ),x j+n 1,...,x j+1 ) f : S S n n (3) x 0 x 1 x 2 x n := x 0 + x m x 1 x 2 x n x n+1 := x 1 + x m+1 x 2 x n x n+1 x n+2 := x 2 + x m+2. x m. x m. x m. x m x m+1 x m+1 x m+1 x m x n 1 x n 1 x n 1 x n 1 C n = 1279, m = gfsr() init gfsr() [3, page 31 36] 1279/32 = /32 10

11 #define N 1279 #define M 418 #define W 32 /* W should be power of 2 */ static unsigned long state[n]; static int state_i; void init_gfsr(unsigned long s) { int i, j, k; static unsigned long x[n]; s &= 0xffffffffUL; for (i=0; i<n; i++) { x[i] = s>>31; s = UL * s + 1UL; s &= 0xffffffffUL; } for (k=0,i=0; i<n; i++) { state[i] = 0UL; for (j=0; j<w; j++) { state[i] <<= 1; state[i] = x[k]; x[k] ^= x[(k+m)%n]; k++; if (k==n) k = 0; } } } state_i = 0; unsigned long gfsr(void) { int i; unsigned long *p0, *p1; if (state_i >= N) { state_i = 0; p0 = state; p1 = state + M; for (i=0; i<(n-m); i++) *p0++ ^= *p1++; p1 = state; for (; i<n; i++) *p0++ ^= *p1++; } } return state[state_i++]; 11

$for (j=0; j<w; j++) { state[i] <<= 1; state[i] = x[k]; x[k] ^= x[(k+m)%n]; k++; if (k==n) k = 0; } } } state_i = 0; unsigned long gfsr(void) { int i; unsigned long *p0,$

12 3.4 TGFSR Twisted GFSR [7][8] GFSR x j+n := x j+m + x j A (j =0, 1,...) A F 2 w A a 0 a 1 a w 1 a { shiftright(x) (x 0 ) xa = shiftright(x)+a (x 1 ) shiftright 2 nw 1 n =25,w =32 TT800 /* A C-program for TT800 : July 8th 1996 Version */ /* by M. Matsumoto, matumoto@math.keio.ac.jp */ /* genrand() generate one pseudorandom number with double precision */ /* which is uniformly distributed on [0,1]-interval */ /* for each call. One may choose any initial 25 seeds */ /* except all zeros. */ /* See: ACM Transactions on Modelling and Computer Simulation, */ /* Vol. 4, No. 3, 1994, pages */ #include <stdio.h> #define N 25 #define M 7 12

c /* A C-program for TT800 : July 8th 1996 Version */ /* by M. Matsumoto, email: matumoto@math.keio.ac.

13 double genrand() { unsigned long y; static int k = 0; static unsigned long x[n]={ /* initial 25 seeds, change as you wish */ 0x95f24dab, 0x0b685215, 0xe76ccae7, 0xaf3ec239, 0x715fad23, 0x24a590ad, 0x69e4b5ef, 0xbf456141, 0x96bc1b7b, 0xa7bdf825, 0xc1de75b7, 0x8858a9c9, 0x2da87693, 0xb657f9dd, 0xffdc8a9f, 0x8121da71, 0x8b823ecb, 0x885d05f5, 0x4e20cd47, 0x5a9ad5d9, 0x512c0c03, 0xea857ccd, 0x4cc1d30f, 0x8891a8a1, 0xa6b7aadb }; static unsigned long mag01[2]={ 0x0, 0x8ebfd028 /* this is magic vector a, don t change */ }; if (k==n) { /* generate N words at one time */ int kk; for (kk=0;kk<n-m;kk++) { x[kk] = x[kk+m] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2]; } for (; kk<n;kk++) { x[kk] = x[kk+(m-n)] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2]; } k=0; } y = x[k]; y ^= (y << 7) & 0x2b5b2500; /* s and b, magic vectors */ y ^= (y << 15) & 0xdb8b0000; /* t and c, magic vectors */ y &= 0xffffffff; /* you may delete this line if word size = 32 */ y ^= (y >> 16); /* added to the 1994 version */ k++; return( (double) y / (unsigned long) 0xffffffff); } /* this main() output first 50 generated numbers */ main() { int j; for (j=0; j<50; j++) { printf("%5f ", genrand()); if (j%8==7) printf("\n"); } printf("\n"); } 3.5 Mersenne Twister Mersenne Twister TGFSR [9] x j+n := x j+m + x j+1 B + x j C (j =0, 1,...) 13

$(kk=0;kk<n-m;kk++) { x[kk] = x[kk+m] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2]; } for (; kk<n;kk++) { x[kk] = x[kk+(m-n)] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2]; } k=0; } y = x[k]; y ^= (y << 7) & 0x2b5b2500; /*$

14 x j+n = x j+m +(x j w r, x j+1 r )A A w x j r C S nw r 2 nw r 1 r f ϕ f ( 5.3 ) C mt19937ar.c m-mat/mt.html 4 GFSR, TGFSR, MT W = F w 2 n Z M Z/M (2.1) Q Z/M M 4.3. S + G1 (x + y)+z = x +(y + z) 14

ac.jp/ m-mat/mt.html 4 GFSR, TGFSR, MT W = F w 2 n 4.1 4.1. 2 0 4.

15 (S, +) S 0 G2 x +0=x, 0+x = x (S, +, 0) S x x G3 x +( x) =0, ( x)+x =0 (S, +, 0, ()) G4 x + y = y + x (S, +, 0, ()) S S 1 (S,, 1) G1,G2,G R1 a (b + c) =a b + a c R2 (a + b) c = a c + b c (S, +, 0, (),, 1) S 0 x S x 0 y S xy = yx =1 S 4.4. V K (V,+, 0) K V V, (a, v) a v a, b K v 1,v 2 V M1 a (v 1 + v 2 )=a v 1 + a v 2 M2 (a + b) v = a v + b v 15

16 M3 (ab) v = a (b v), 1 v = v 4.5. K n K n a K K 4.6. K V, W f : V W K f(v 1 + v 2 )=f(v 1 )+f(v 2 ), f(a v) =a f(v) V = K n W V S K f : S S K x j+1 = f(x j ) 1 S S K S = K d,f(x) =F x F K d TGFSR TGFSR n x j+n := x j+m + x j A (j =0, 1,...) x j w 1 f :(x n 1, x n 2,...,x 1, x 0 ) (x m + x 0 A, x n 1,...,x 2, x 1 ) 16

2 S K f : S S K x j+1 = f(x j ) 1 S S K S = K d,f(x) =F x F K d TGFSR TGFSR n x

17 x j f : F nw 2 F nw 2 (x n 1, x n 2,...,x 1, x 0 ) f nw I w I w I w B =... A nw 8. Mersenne Twister x j+n = x j+m +(x j w r, x j+1 r )A 1 I w f :(x n 1, x n 2,...,x 1, {x 0 w r }) (x n, x n 2,...,x 2, {x 1 w r }) f : F nw r 2 F nw r x 0 K d, x j+1 = Bx j (4) B d K B x 0 B p x 0 = x 0 p 1 B p+k x 0 = B k x 0 k 0 p 1 17

..,x 1, {x 0 w r }) (x n, x n 2,...,x 2, {x 1 w r }) f : F nw r 2 F nw r 2 1 4.

18 4.7. K B d d x 0 K d x j+1 = Bx j #(K) d 1 #(K) d 1 x 0 0 x j 0 B 0 #(K) d K d #(K) d 0 K d B0 =0 B #(K) d K d B j x #(K) d 1 0 #(K) d 1 B ( 5.1) B p x = x p B p p = p 4.8. d B d x {g(t) K[t] g(b)x =0} K[t] K[t] ( 1) 0 x B annihilator ϕ B,x (t) g(b)x =0 ϕ B,x (t) g(t). 18

3 K d #(K) d 0 K d B0 =0 B #(K) d K d B j x 0 0 0 #(K) d 1 0 #(K) d 1 B (

19 4.9. K K K[t] K[t] K R I R R I x, y I x + y I, x I,r R rx I R R I I = {ra r R} a (a) annihilator x,bx,b 2 x,... F d 2 d B j x j d 0 a 0,a 1,...,a j K a 0 x + a 1 Bx + a 2 B 2 x + + a j B j x =0 j 1 a j 0 a j B j 1 ϕ(t) :=a 0 + a 1 t + a 2 t t j ϕ(b)x =0 ϕ(t) g(b)x =0 g(t) 0 h(t) h(b)x = 0 h x,bx,b 2 x,..., ϕ(t) {g(t) K[t] g(b)x =0} annihilator ϕ B,x (t) ϕ(t) =ϕ B,x (t) annihilator 19

20 4.10. B K d x K d x,bx,b 2 x,... x,bx,b 2 x,...,b j x a 0 x + a 1 Bx + + a j 1 B j 1 x + B j x =0 a i K B x annihilator ϕ B,x (t) ϕ B,x (t) =t j + a j 1 t j a 1 t + a 0 d (B p I)x =0 p ϕ B,x t p 1 p K[t]/ϕ B,x ϕ B,x ϕ B,x p t (K[t]/ϕ B,x ) K t (K[t]/ϕ B,x ) t ϕ B,x K x K d B M d (K) t ϕ B,x t (K[t]/ϕ B,x ) 20

21 #(K) d 1 deg ϕ B,x = d (K[t]/ϕ B,x ) #(K) d 1 t. d := deg ϕ B,x #((K[t]/ϕ B,x ) ) #(K) d 1 #(K) d 1 t K ϕ(t) K[t]/ϕ(t) t #(K) deg ϕ(t) K ϕ(t) K[t]/ϕ(t) t #(K) deg ϕ(t) ϕ(t) ϕ(t) t (K[t]/ϕ(t)) ϕ B,x d (d B ) t K[t]/ϕ B,x 1 1 t/ (K[t]/ϕ B,x ) ϕ(t) =t m ψ(t) t ψ(t) t K[t]/ϕ(t) = K[t]/t m K[t]/ψ(t) 21

22 t ψ(t) p t (K[t]/ψ(t)) ϕ(t) t m (t p 1) m m, p p m, p K d B ϕ B (t) {g(t) K[t] g(b) =0} g(b) =0 ϕ B (t) g(t) K d B χ B (t) χ B (t) = det(ti d B) K[t] d ϕ B,x (t) ϕ B (t) χ B (t).. ϕ B (B)x =0 χ B (B) =0 Cayley-Hamilton K B K d x K d {0} 1. x B #(K) d 1 2. ϕ B,x (t) d 3. χ B (t) : 4.19 ϕ B,x χ B (t) d d 3 2: ( 4.14) ϕ B,x =1 χ B (t) =1 I d x =0 x =0 ϕ B,x (t) =χ B (t)

23 Cayley-Hamilton Cayley-Hamilton (Cayley-Hamilton K: ) A K n χ A (A) =0. ti A M n (K[t]) Q(t) t Q(t) =Q n 1 t n Q 0 (Q i M n (K)) (ti A)Q(t) =Q(t)(tI A) = det(ti A)I = χ A (t)i M n (K[t]) (5) AQ(t) =Q(t)A t i A Q i Q i A (5) t A 0=χ A (A) (ti A)Q(t) =(tq n 1 t n tq 0 ) (AQ n 1 t n AQ 0 )=χ A (t)i Q n 1,Q n 2 AQ n 1,...,Q 0 AQ 1, AQ 0 χ A (t) I X M n (K) (Q n 1 X n + + Q 0 X) (AQ n 1 X n AQ 0 )=χ A (X)I X = A A Q i K d d B #(K) d 1 B χ B 23

24 B 5.1. d d ϕ(#(k) d 1)/d ( ϕ ) 5.2. d d B. ( 3.4 ) p m p m F p m F p m F p n m n K = F p m d K d L = F p md L α α ϕ α (t) K[t]/ϕ α (t) = L, t α α #(L )=#(K) d 1 t ϕ α (t) L d d :1 d d :1 L/K ϕ(#(k) d 1) d

25 5.2 K S = K d, f : S S B #(K) d 1 B 0 W = F w 2 K d {0} n x j+n = g(x j+n 1,...,x j ) 1 S = W n = F nw nw 1 ( 13 g ) g 1 (x j+n 1,...,x j ) (g(x j+n 1,...,x j ), x j+n 1,...,x j+1 ) (x j+n,...,x j+1 ) n w n (multi-set ) {(x j+n 1,...,x j ) j =0, 1,...,2 nw 2} 2 nw 0 window property n 0 1 n GFSR nw 2 n 1 TGFSR Mersenne Twister {(x j+n 1,...,x j w r )} 25

26 13. n, w x j+n = g(x j+n 1,...,x j ) 2 nw 1 g 14. Mersenne Twister window property 5.3 F 2 1. B 2. (1) B 5.3. G g G r 1. g r = e, 2. r p g r/p e. 1 g r r r p r/p 2 g n n n log 2 (n) g n n a 2 a 1 a 0 1. x 1 2. x g a 2 x 3. x x 2 26

27 4. x g a 1 x 5. x x 2 6. x g a 0 x x g n 2 log 2 (n) a i =0 5.3 r r g e, g r = e r 5.4. G g G, g e, g r = e r g r 5.5. G G p G p G 5.6. K q q m 1 m. ϕ(t) m K[t]/ϕ(t) (K[t]/ϕ(t)) q m 1 1 q m 1 t 4.13 ϕ(t) q m 1 q 1 q =2 q 2 m =1 ϕ(t) 1 2 m 1 m m 5.7. m φ(t) F 2 m φ(t) F 2 [t]/φ(t) t 2 t t (2m) = t. t 2 m 1 a {n N t n a = a} n s s n s r a = t n a = t r t qs a = t r a r <s s r =0 27

28 a = t, n =2 m 1 s n =2 m m 1 t l t l =0, 1,...,2 m 2 0 F 2 [t]/φ(t) 0 t 1 t t 2 m 1 φ(t) 5.8. φ(t) =t 7 + t = 127 t 27 mod φ(t) t t 2 t 4 t 8 = t 2 + t t 4 + t 2 t 8 + t 4 = t 4 + t 2 + t t 8 + t 4 + t 2 = t 4 + t t 8 + t 2 = t 7 t φ(t) 5.9. q>2 (q m 1)/(q 1) 6 : k t ( ) k /2 k t n n k ( ) k >n 3 GFSR 6.1 {0, 1} M M 0-1 G : S {0, 1} M (S: ) 28

29 (M = 10): G(s 0 ) = ( ), G(s 1 ) = ( ),. S {0, 1} M 2 m 1 k 1 M := m + k x {0, 1} M = {0, 1} m {0, 1} k, wt o (x) := x m 1 wt f (x) := x k 1 (wt weight o observed f future) x 0 s m 0 t k wt o (x) =s wt f (x) =t p k,m (t s) := Prob(w f (x) =t w o (x) =s) m s k t ( ) k p k,m (t s) = /2 k t 2 Mersenne Twister [ ] 29

30 p k,m (t s) F 2 - MacWilliams ( 6.4) 6.2 random() C ( 90 ) ( ) x i+31 = x i+28 + x i mod 2 32 (i =1, 2,...) + 2 EXOR x i+31 = x i+28 + x i mod 2 (i =1, 2,...) F 2 ran array() Knuth 97 [4] x i+100 := x i+63 + x i mod 2 30 (i =1, 2,...) Lüscher x i+100 := x i+63 + x i mod 2 (i =1, 2,...) F p k,m (0 t) prob random weight 30

31 random() 1 p 8,31 (0 s) (10 s 22) 31 s 8 1/256= ran_array prob weight ran array() 1 p 8,100 (0 s) (40 s 60) 100 s 8 1/256= {0, 1} M = {0, 1} m {0, 1} k G(S) {0, 1} M x G(S) G [ ] 15. p k,m (t s) := Prob(w f (x) =t w o (x) =s) 31

32 A ij := #{x G(S) wt o (x) =i, wt f (x) =j} (0 i m, 0 j k) p k,m (t s) =A st /(A s0 + A s1 + + A sk ). A ij G(S) 2 A ij 1. G(S) F M 2 F 2 - ( F 2 2. M = k + m G(S) F M MacWilliams C F m+k 2 (G(S) ) A ij := #{x C wt o (x) =i, wt f (x) =j}(0 i m, 0 j k) A ij dim C NP- (A, Vardy 1997) M dim C MacWilliams C C F M 2 C := {y F M 2 < x, y >= 0 for all x C}. < (x 1,...,x M ), (y 1,...,y M ) >:= M x i y i. i=1 C W C (x, y, X, Y ):= 0 i m,0 j k A ijx m i y i X k j Y j, 32

33 6.1. ( MacWilliams ) W C (x, y, X, Y )= 1 W #(C ) C (x + y, x y, X + Y,X Y ). dim C (= M dim C) W C (x, y, X, Y ) A ij p k,m (t s) dim C 8 dim C 521 G(S) 3 5 MacWilliams [10] 6.5 MacWilliams V := F M 2, W := FM 2 e : V W {±1}, (v, w) e(v w) :=( 1) <v,w> < v,w> R f f : W R, f : V R f(w) := f(v)e(v w) (±1 R e(v w) R ) 33 v V

34 6.2. V = W = F 2 R = Q[x, y], f : V R f(0) = x, f(1) = y f(0) = v=0,1 f(v)e(v 0) = f(0) + f(1) = x + y, f(1) = v=0,1 f(v)e(v 1) = f(0) f(1) = x y C V C W C := {w W <v,w>= 0 for all v C} 6.3. (Poisson ) v C f(v) = 1 #C w C f(w). f(w) = f(v)e(v w) w C w C v V = f(v)( e(v w)) v V w C = f(v)#(c ) v C #(C ) 6.4. w C e(v w) = { 0 v/ C #(C ) v C. e(v w) =1 v/ C C F 2, w < v,w> 0 F e(v w) 0 34

35 16. f : G 1 G 2 x G 1 f(x) f x +Kerf R f : V R Q[x 1,x 2,...,x M,y 1,y 2,...,y M ] f(v 1,...,v M ):=f 1 (v 1 )f 2 (v 2 ) f M (v M ) v i F 2 f i : F 2 R ( 6.2 ) f i (0) = x i,f i (1) = y i W C (x 1,y 1,...,x M,y M ):= v C f(v) C M 6.5. W x 1 = x 2 = = x m := x, y 1 = y 2 = = y m := y, x m+1 = x m+2 = = x m+k = X, y m+1 = y m+2 = = y m+k = Y (6) W C (x, y, X, Y ). W f 1 (v 1 )f 2 (v 2 ) f M (v M ) x m i y i X k j Y j v 1,...,v m i 1 v m+1,...,v m+k j 1 wt o (v) =i, wt f (v) =j v W v C A ij Aij x m i y i X k j Y j = W C (x, y, X, Y ) 35

36 Poisson 6.3 W := v C f(v) = 1 #C w C f(w) w C f(w) W C (x + y, x y, X + Y,X Y ) MacWilliams f : V R V = V 1 V 2 f f 1 : V 1 R f 2 : V 2 R f(v 1 v 2 )=f 1 (v 1 )f 2 (v 2 ) 6.6. f(w 1 w 2 )= f 1 (w 1 ) f 2 (w 2 ) f i : W i R W = W 1 W 2 = V2 V1 17. f f(v 1,...,v M )=f 1 (v 1 )f 2 (v 2 ) f(v M ) V = F 2 F 2 F 2 = V 1 V M ( V i i ) W = W 1 W 2 W M 6.2 f i (0) = f i (0)e(0 0) + f i (1)e(1 0) = x i + y i f i (1) = f i (0)e(0 1) + f i (1)e(1 1) = x i y i f i (w i ) f i (w i ) x i x i + y i, y i x i y i 36

37 f(w 1,...,w M )= f 1 (w 1 ) f M (w M ) = f 1 (w 1 ) f M (w M ) x i x i + y i y i x i y i f(w) w C = w C (f(w) ) = W C (x 1 + y 1,x 1 y 1,...,x M + y M,x M y M ) 6.7. ( MacWilliams ) W C (x 1,y 1,...,x M,y M )= 1 W #(C ) C (x 1 + y 1,x 1 y 1,...,x M + y M,x M y M ). (6) MacWilliams x 1 = = x M = x, y 1 = = y M = y MacWilliams MacWilliams MacWilliams [6, P.147, Theorem 14] MacWilliams [6, P.158, Eq.(52)] f 1 f : R/Z C f f(x) = n exp(2πinx) n a 6.9. f f(x) =f(x) a n = a n f(x) =C + n Æ(s n cos nx + t n sin nx) 37

38 a n a n = Ê/ a n Ê/ e 2πimx e 2πinx dx = f(x)e 2πinx dx { 0 (m n) 1 (m = n) a : Z C, a(n) :=a n f : R/Z C a : Z C a(n) = f(x)e 2πinx dx Ê/ f(x) = n a(n)e 2πinx C 1 1 e : R/Z Z C 1, (x, n) e(x n) := exp(2πinx) well-defined 1. e x 0 R/Z e(x 0 ) :Z C 1, n e(x 0 n) n 0 e( n 0 ):R/Z C 1, x e(x n 0 ) 2. R/Z Hom(Z, C 1 ), x 0 e(x 0 ) 38

39 3. Z Hom(R/Z, C 1 ), n 0 e( n 0 ) V,W e ( V = R/Z, W = Z ) G Ĝ := Hom(G, C 1 ) (Pontryagin ) G G Ĝ R/Z, Z Z/M, Z/M, e(n m) := exp(2πinm/m) F M 2, FM 2,e(v w) := exp(2πi<v,w>/2) = ( 1)<v,w> ( ) Haar R/Z Z V,W,e f : V C f : W C, f(w) := f(v)e(v w)dv V f dv V Haar V = F M f V = R/Z W = Z f : V C f(n) = f(x)e(x n)dx = a( n) Ê/ 39

40 V = Z W = R/Z a : V C â(x) = n a(n)e(x n) Poisson C V (Poisson ) f(v)dv C = f(w)dw C. C C ( [13, Theorem 5.5.2] ) 6.3 R/Z Z Poisson random() ran array() M [11] f(x) =f( x) v k 7.1. v k k v 2 kv v = w k ( 5.2 ) 40

41 w 2 w [0, 1) k 2 v 7.2. kv kv G : S F kv 2 S F 2 G (0 ) v k G 19. v k k(v) k(v)v dim S v =1, 2,...,w k(v) = dim S/v TGFSR, MT dim S = nw, nw r v =1 k(1) = dim S v =2 k(2) = n < nw/2 3 n TGFSR, MT (tempering) w T x xt y x +(x ) & y x +(x ) 41

42 Defects of MSB MT(MT521) tempering v =1,..., k(v) Table II. Parameters and k-distribution of Mersenne Twisters Generator The order of equidistribution ID Parameters k(1) k(2) k(3) k(4) k(5) k(6) k(7) k(8) k(9) k(10) k(11) k(12) (the number of k(13) k(14) k(15) k(16) k(17) k(18) terms in the k(19) k(20) k(21) k(22) k(23) k(24) characteristic k(25) k(26) k(27) k(28) k(29) k(30) polynomial) k(31) k(32) Upper bounds nw r for v (w, n, r) = (32, 351, 19) v MT11213A (w, n, m, r) = (32, 351, 175, 19) a = E4BD75F u = s = 7,b = 655E (177) t = 15,c = FFD l = MT11213B (w, n, m, r) = (32, 351, 175, 19) a = CCAB8EE u = s = 7,b = 31B6AB (151) t = 15,c = FFE l = Upper bounds nw r for v (w, n, r) = (32, 624, 31) v MT19937 (w, n, m, r) = (32, 624, 397, 31) a = 9908B0DF u = s = 7, b = 9D2C (135) t = 15, c = EFC l = TT800 (w, n, m, r) = (32, 25, 7, 0) a = 8EBFD u : not exist s = 7, b = 2B5B (93) t = 15, c = DB8B l = ran array Knuth s new recommendation Here we list the trivial upper bounds tempering k(v) try-anderror 42

43 19937 ([1]) 7.2 F 2 s S v k(v) (x 10,x 20,...,x v0 ), (x 11,x 21,...,x v1 ),... A := F 2 [[t]] w(s) :=( x 1i t i, x 2i t i,..., x vi t i, ) i=0 S i=0 w : S A v i=0 F := F 2 ((t)) F A i= m a i t i := 2 m (a m 0) F v sup (x 1,...,x v ) := max { x i } i=1,2,...,v A v x + y max x, y v e i := (0,...,0, 1/t, 0,...,0) F 2 (i 1/t) F v F v = A v + F 2 [t 1 ] <e 1,e 2,...,e v > e i F 2 [t 1 ]- 43

44 s 0 S {e 1,e 2,...,e v,w(s 0 )} F 2 [t 1 ] L F v w(s) =L A v. s 0 m s m w(s m )=t m w(s 0 ) w(s m ) L. w(s m ) A v m w(s m ) w(s) {0} F 2 L := w(s)+f 2 [t 1 ] <e 1,e 2,...,e v > t 1 ( <> F 2 [t 1 ] ) F 2 [t 1 ] w(s 0 ) w(s) L L A v F v L F 2 [t 1 ] B 7.4. L 2 k(v) 7.5. F 2 [t 1 ] L F v L r F v L r r L 7.6. k L 2 k 1. 2 k 1 kv k A v x L x 2 k 1 x x A v x L A v, x x 2 k 1. 44

45 x k x x w(s) kv k kv L A v 2 k 1 A v F 2 F v = A v + F 2 [t 1 ] <e 1,e 2,...,e v > L F 2 [t 1 ] <e 1,e 2,...,e v > L 2 k 1. ( 7.4 ) 2 k L 2 k 1 2 k B L 2 k 1 B L F B F v x F v x = i a i b i, a i F, B = {b 1,...,b v } a i F 2 [t 1 ] α i a i α i 1/2 x i α i b i = i (a i α i )b i 1/2 B 2 k 1 2 k L F v e i =(0,...,0, 1/t, 0,...,0) t k+1 e i l i 2 k (7) l i L l i =2 k l 1,...,l v (7) t k+1 e i l i mod t k+1, 45

46 mod t k+1 l i (0, 0,...,0,t k, 0,...,0) l i a i l i =0, a i F i t a i A 1 a 1 mod t k+1 (t k, 0,...,0) 0 2 k L v B L L x B F 2 [t 1 ] B F x B F 2 [t 1 ] x x B ta x =0 0 B ta x B x Lenstra[5] [1] R. Couture, P. L Ecuyer, and S. Tezuka, On the distribution of k- dimensional vectors for simple and combined Tausworthe sequences, Math. Comp. 60 (1993), [2] Luc Deveroye, Nonuniform random variate generation. Springer-Verlag, [3],,, [4] Knuth, D. E. The Art of Computer Programming. Vol. 2. Seminumerical Algorithms 3rd Ed. Addison-Wesley, [5] Lenstra, A. K. Factoring multivariate polynomials over finite fields. J. Comput. System Sci. 30, [6] F.J. MacWilliams and N.J.A. Sloane, The theory of error correcting code. North-Holland,

47 [7] Matsumoto, M. and Kurita, Y. Twisted GFSR Generators, ACM Transactions on Modeling and Computer Simulation 2 (1992), [8] Matsumoto, M. and Kurita, Y. Twisted GFSR Generators II, ACM Transactions on Modeling and Computer Simulation 4 (1994), [9] Matsumoto, M. and Nishimura, T. Mersenne Twister: a 623- dimensionally equidistributed uniform pseudo-random number generator ACM Trans. on Modeling and Computer Simulation 8 (1998), [10] M. Matsumoto and T. Nishimura A Nonempirical Test on the Weight of Pseudorandom Number Generators in: Monte Carlo and Quasi- Monte Carlo methods 2000, Springer-Verlag [11] M. Matsumoto and T. Nishimura Sum-discrepancy test on pseudorandom number generators Mathematics and Computers in Simulation, Vol. 62 (2003), pp [12] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods. SIAM, [13] Reiter, S. and Stegeman, J.D.: Classical harmonic analysis and locally compact groups. Oxford Science Publications, Oxford,

6 : MacWilliams M

6 : MacWilliams M 22 12 8 1 2 1.1............................ 2 1.2.......................... 3 1.3............................. 3 1.4.......................... 5 2 5 2.1.............. 6 2.2........................ 6 3