6 : MacWilliams M

Size: px

Start display at page:

Download "6 : MacWilliams M"

しおりらぶり
7 years ago
Views:

1 LCG GFSR TGFSR Mersenne Twister

4 TGFSR............................... 12 3.5 Mersenne Twister.......................... 14 4 15 4.1............................ 15 4.2............................. 17 4.

2 6 : MacWilliams MacWilliams v k

5.1...................... 36 6.5.2................. 40 7 43 7.1 v k................ 43 7.2........................ 46 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) 3

4 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 /7 M M 1.4. M = 2 n, a = 1, c = M M = , a = 16807, c = 0 0 M 1 M LCG M 0,..., M 1 1 M 1 6 0,1,2,3,4,5 M 6 1 M, a, c, x 0 M M 1 x

1.4 3. M = 2 31 1, a = 16807, c = 0 0 M 1 M LCG M 0,.

5 1.4 LCG LCG M M M 2 8 F 2 := {0, 1} = 0 ( 4.1 ) F m 2 m m m A x j+1 := Ax j A??? LCG 1.6. LCG( 1.1) M 1. (c, M) = 1 (c M ) 2. M a 1 3. M 4 a

6 S, O f : S S s 0 S o : S O S S f S f o 100 s 0 s i+1 = f(s i ) s 0, s 1, s 2,... o(s 0 ), o(s 1 ), o(s 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 2.2 6

7 2.3. S #(S) 2.4. x 1, x 2,... ( ) 1 p N n N x n+p = x n (2) (2) 1 p (period) 5. (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,... N := #(S) s 1, s 2,..., s N+1 1 p < n N + 1 s n = s n p f n o(s n ) o(s n ) s n , π 2.7. #(S) s i S 6. S {s i } i=0,1,2,... f 2.8. LCG( 1.1 ) M 7. (1) M a 1 mod M M 1 a M 1 M (Z/M) M 1 7

3 ) s 0, s 1,... N := #(S) s 1, s 2,..., s N+1 1 p < n N + 1 s n = s n p f n o(s n ) o(s n ) s n 5 2.

8 3 3.1 CPU {0, 1} 32 := {(x 31, x 30,..., x 0 ) x i = 0 1} w W := {0, 1} w CPU W CPU W ( ) w = 6 AND (C &) & = OR (C ) = EXOR (C ˆ) = = F 2 := {0, 1} = 0 2 W F 2 w F w 2 EXOR 8

&) 1 1 001101&010111 = 000101 OR (C ) 1 1 001101 010111 = 011111

9 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; } C mod m 2 m xyz

$long rand(void) { x = x * 1103515245 + 12345; x &= 0x7fffffff; /* mod 2^31$

10 1: ANSI C rand() 2: GFSR 1 =w F 2 w F w 2 n > m > 0 x j+n := x j+m + x j (j = 0, 1,...) (3) Generalized Feedbacked Shiftregister (GFSR) GFSR x j+3 := x j+1 + x j (j = 0, 1,...) 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 10

11 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 #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; 11

$#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$

12 } 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++]; 3.4 TGFSR Twisted GFSR [8][9] GFSR x j+n := x j+m + x j A (j = 0, 1,...) 12

$(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;$

13 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 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 13

jp */ /* genrand() generate one pseudorandom number with double precision */ /* which is uniformly distributed on [0,1]-interval */ /* for each call.

14 } }; 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 [10] x j+n := x j+m + x j+1 B + x j C (j = 0, 1,...) x j+n = x j+m + (x j w r, x j+1 r )A A w x j r C S nw r 14

$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.$

15 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 4.1 ( ) Z M Z/M ( 2.2) Q Z/M M 4.2. S + G1 (x + y) + z = x + (y + z) (S, +) S 0 G2 x + 0 = x, 0 + x = x (S, +, 0) S x x 15

html 4 GFSR, TGFSR, MT W = F w 2 n 4.1 ( ) 2 0 4.1. Z M Z/M ( 2.

16 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 x S x 0 y S xy = yx = 1 S S S S 4.3. N Z/N := {0, 1, 2,..., N 1} N N N p F p := Z/p p = 2 F S V S S (V, +, 0) S V V, (a, v) a v a, b S v 1, v 2 V 16

(),, 1) S 0 1 0 x S x 0 y S xy = yx = 1 S S S S 4.3. N Z/N := {0, 1, 2,.

17 M1 a (v 1 + v 2 ) = a v 1 + a v 2 M2 (a + b) v = a v + b v M3 (ab) v = a (b v), 1 v = v S K K- K 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 w 0,1 w F w 2 : x xb 17

18 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 ) 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 9. 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 1,..., 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 18

19 K B x 0 B p x 0 = x 0 p 1 B p+k x 0 = B k x 0 k 0 p 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 19

20 4.8. d B d x {g(t) K[t] g(b)x = 0} K[t] K[t] 0 ( 1 ) x B annihilator ϕ B,x (t) g(b)x = 0 ϕ B,x (t) g(t). (5) 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 a, b R ab = 0 a b R R I I = {ra r R} R a (a) K[t] K[t] (5) annihilator x, Bx, B 2 x,... 20

21 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 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 21

22 p (5) p ϕ B,x t p 1 K[t]/ϕ B,x ϕ B,x ϕ B,x p t deg(ϕ B,x ) ϕ B,x K deg(ϕ B,x ) (K[t]/ϕ B,x ) K[t]/ϕ B,x K 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 ) #(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 22

23 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 t ψ(t) p K[t]/ϕ(t) = K[t]/t m K[t]/ψ(t) t (K[t]/ψ(t)) ϕ(t) t m (t p 1) m m, p p m, p

24 4.17. 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)

25 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]) (6) AQ(t) = Q(t)A t i A Q i Q i A (6) 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 25

26 B χ B 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 26

27 d : 1 d d : 1 L/K ϕ(#(k) d 1) d 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 ( 15 g ) (x j+n 1,..., x j ) (x j+n,..., x j+1 ) 2 nw 1 n w ( 4.7) n ( multi-set ) {(x j+n 1,..., x j ) j = 0, 1,..., 2 nw 2} 2 nw 0 window property n 27

28 0 1 n GFSR nw 2 n 1 TGFSR Mersenne Twister {(x j+n 1,..., x j+1, x j w r )} 15. n, w x j+n = g(x j+n 1,..., x j ) 2 nw 1 g 16. Mersenne Twister window property 5.3 F 2 1. B 2. (1) B 5.3. G t, a G {n N {0} t n a = a} s N {0} 0 28

29 t 0 a := a. 0 s = 0 s n s r a = t n a = t r t qs a = t r a r < s s r = G e g G r 1. g r = e, 2. r p g r/p e. 5.3 t = g, a = e g n = e n s g n = e s n 1 s r r/s 1 p 2 r = s 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 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 = r r g e, g r = e r 29

30 5.5. G g G, g e, g r = e r g r 5.6. G G p G p G 5.7. 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 m 1 + q m ) q = 2 q 3 m = 1 ϕ(t) 1 2 m 1 m m 5.8. m φ(t) F 2 m φ(t) F 2 [t]/φ(t) t 2 t t (2m) = t. t 2 m a = t = g, n = 2 m 1 n 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.9. φ(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) q > 2 (q m 1)/(q 1) 30

31 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: ) (M = 10): G(s 0 ) = ( ), G(s 1 ) = ( ),. S {0, 1} M 2 2 Mersenne Twister [ ] 31

32 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) 0,1 m s k t p k,m (t s) = p k,m (t s) ( k t ) /2 k F 2 - MacWilliams ( 6.4) 6.2 random() C 90 ( ) x i+31 = x i+28 + x i mod 2 32 (i = 1, 2,...) 32

33 + 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) random prob weight random() 1 p 8,31 (0 s) (10 s 22) 31 s 8 1/256=

34 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(S) G(S) G [ ] 17. p k,m (t s) := Prob(w f (x) = t w o (x) = s) A ij := #{x G(S) wt o (x) = i, wt f (x) = j} (0 i m, 0 j k) 34

35 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 ij > 0 i + j NP- A, Vardy 1997 reference???) 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, 6.1. ( MacWilliams ) W C (x, y, X, Y ) = 1 W #(C ) C (x + y, x y, X + Y, X Y ). 35

36 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 [5] MacWilliams 1 [11] 6.5 MacWilliams V := F M 2, W := F M 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 ) v V 36

37 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 37

38 18. 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 (7) 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 ) 38

39 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 19. 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 39

40 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 ). (7) MacWilliams x 1 = = x M = x, y 1 = = y M = y MacWilliams MacWilliams MacWilliams [7, P.147, Theorem 14] MacWilliams [7, P.158, Eq.(52)] f 1 f : R/Z C f f(x) = a n exp(2πinx) n Z 6.9. f f(x) = f(x) a n = a n f(x) = C + n N(s n cos nx + t n sin nx) 40

41 a n a n = R/Z a n R/Z 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 R/Z f(x) = n Z 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 ) 41

42 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, F M 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) R/Z 42

43 V = Z W = R/Z a : V C â(x) = n Z a(n)e(x n) Poisson C V (Poisson ) f(v)dv C = f(w)dw C. C C ( [14, Theorem 5.5.2] ) 6.3 R/Z Z Poisson random() ran array() M [12] f(x) = f( x) K?? S, O K f : S S, o : S O K K F 2 43

44 7.1 v k 7.2. v k k v 2 kv v = w k ( 5.2 ) w 2 w [0, 1) k 2 v 7.3. kv kv G : S F kv 2 F 2 G F 2 (0 ) v k G 21. 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 ) & 44

45 y x + (x ) Defects of MSB MT(MT521) tempering v = 1,..., k(v) 45

46 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 ([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 i=0 46 i=0

47 S w : S A v F := F 2 ((t)) F A a i t i := 2 m (a m 0) i= m 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 ] 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 47

48 F v L F 2 [t 1 ] B 7.5. L 2 k(v) F 2 [t 1 ] L F v L r F v L r r L 7.7. k L 2 k. 2 k kv k =t k 1 A v x L x 2 k x x A v x L A v, x x 2 k. x k x x w(s) kv k kv L A v 2 k 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. ( 7.4 ) 2 k+1 L 2 k 2 k+1 B L 2 k B L F B F v x F v x = i a i b i, a i F, B = {b 1,..., b v } 48

49 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 2 k+1 L F v e i = (0,..., 0, 1/t, 0,..., 0) t k e i l i 2 k (8) l i L t k e i = 2 k+1 l i = 2 k+1 l 1,..., l v (8) t k e i l i mod t k, mod t k l i (0, 0,..., 0, t k 1, 0,..., 0) l i a i l i = 0, a i F i t a i A 1 a 1 mod t k (t k 1,,..., ) 0 2 k+1 L v B ( w(s) w(s) ϕ(t) 1 A v ϕ(t) 0 2 deg(ϕ(t)) 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[6] 49

50 [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] Haramoto, H., Matsumoto, M., Nishimura, T. Computing conditional probabilities for F 2 -linear pseudorandom bit generator by splitting Mac- Williams identity, International Journal of Pure and Applied Mathematics, Vol.38 No.1, [6] Lenstra, A. K. Factoring multivariate polynomials over finite fields. J. Comput. System Sci. 30, [7] F.J. MacWilliams and N.J.A. Sloane, The theory of error correcting code. North-Holland, [8] Matsumoto, M. and Kurita, Y. Twisted GFSR Generators, ACM Transactions on Modeling and Computer Simulation 2 (1992), [9] Matsumoto, M. and Kurita, Y. Twisted GFSR Generators II, ACM Transactions on Modeling and Computer Simulation 4 (1994), [10] 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), [11] 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 [12] M. Matsumoto and T. Nishimura Sum-discrepancy test on pseudorandom number generators Mathematics and Computers in Simulation, Vol. 62 (2003), pp

51 [13] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods. SIAM, [14] Reiter, S. and Stegeman, J.D.: Classical harmonic analysis and locally compact groups. Oxford Science Publications, Oxford,

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

6 : 28 6.1...................... 28 6.2.......................... 30 6.3.......................... 31 6.4 MacWilliams........................ 32 6.5 M 16 11 26 1 2 1.1............................ 2 1.2.......................... 3 1.3............................. 3 1.4.......................... 4 2 5 2.1.............. 5 2.2........................ 6 3