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 8 3.1........................... 8 3.2 LCG................................. 9 3.3 GFSR................................ 10 3.4 TGFSR............................... 12 3.5 Mersenne Twister.......................... 14 4 15 4.1............................ 15 4.2............................. 17 4.3..................... 18 5 25 5.1.......................... 25 5.2.......................... 27 5.3....................... 28 1
6 : 31 6.1...................... 31 6.2.......................... 32 6.3.......................... 34 6.4 MacWilliams........................ 35 6.5 MacWilliams..................... 36 6.5.1...................... 36 6.5.2................. 40 7 43 7.1 v k................ 43 7.2........................ 46 1 1.1 1 1. 2. 1 2
1.2 ( ) 1943 [4] Lehmer 60 1.3 1.1. ( ) M, a, c x j+1 := ax j + c mod M (1) x 0 mod M M (Linear Congruential Generator, LCG) 3
1.2. M = 7, a = 3, c = 0 x 0 = 4 x j 4, 5, 1, 3, 2, 6, 4, 5,... 1.3. c = 0,x 0 = 0 x j 0 1. 4/7 M M 1.4. M = 2 n, a = 1, c = M 2. 1.4 3. 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 M 6 1 M, a, c, x 0 M M 1 x 0 1.5. 4
1.4 LCG 80 1. 2 32 2. LCG M M M 2 8 F 2 := {0, 1} 1 + 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 1 4 4. 2 5
2.1 2.1. 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 ),... 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 2.2 6
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 5 2.5. 2.6. 2, π 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 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 &) 1 1 001101&010111 = 000101 OR (C ) 1 1 001101 010111 = 011111 EXOR (C ˆ) 1 + 1 = 0 001101 010111 = 011010 3.1. F 2 := {0, 1} 1 + 1 = 0 2 W F 2 w F w 2 EXOR 8
3.2 LCG 1.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 unsigned long x=3; /* initial seed */ unsigned long rand(void) { x = x * 1103515245 + 12345; x &= 0x7fffffff; /* mod 2^31 */ return x; } C 2 32 32 mod 2 32 1 2 8. m 2 m 3 1. 3 xyz 2. 2 31 3. 0.015 1 9
1: ANSI C rand() 2: 97 3.3 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,...) 001011100101110010111 7 2 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
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+1.... x n 1 x n 1 x n 1 x n 1 C n = 1279, m = 418 2 1279 1 gfsr() 0 2 32 1 init gfsr() [3, page 31 36] 1279/32 = 39 2 1279 /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 = 1664525UL * s + 1UL; 11
} 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
A F 2 w A 1 1... 1 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 http://random.mat.sbg.ac.at/ftp/pub/data/tt800.c /* A C-program for TT800 : July 8th 1996 Version */ /* by M. Matsumoto, email: 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 254-266. */ #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
} }; 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
2 nw r 1 r f ϕ f ( 5.3 ) C mt19937ar.c http://www.math.sci.hiroshima-u.ac.jp/ m-mat/mt.html 4 GFSR, TGFSR, MT W = F w 2 n 4.1 ( ) 2 0 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
G3 x + ( x) = 0, ( x) + x = 0 (S, +, 0, ()) G4 x + y = y + x (S, +, 0, ()) S S 1 (S,, 1) G1,G2,G4 + 0 1 + R1 a (b + c) = a b + a c R2 (a + b) c = a c + b c (S, +, 0, (),, 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,..., N 1} N N N p F p := Z/p p = 2 F 2 4.4. S V S S (V, +, 0) S V V, (a, v) a v a, b S v 1, v 2 V 16
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 + 4.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 w 0,1 w F w 2 : x xb 17
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 2 1 4.3 1 x 0 K d, x j+1 = Bx j (4) B d 18
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 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 1. 2.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 ( 5.1) B p x = x p B p p = 2 19937 1 p 19
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) 10. 4.8 K[t] K[t] (5) annihilator x, Bx, B 2 x,... 20
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 2 + + 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 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 1 + + a 1 t + a 0 d (B p I)x = 0 21
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 4.11. K x K d B M d (K) t ϕ B,x t (K[t]/ϕ B,x ) 4.12. 4.11 #(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
K ϕ(t) K[t]/ϕ(t) t #(K) deg ϕ(t) 1 4.13. K ϕ(t) K[t]/ϕ(t) t #(K) deg ϕ(t) 1 4.14. ϕ(t) ϕ(t) t (K[t]/ϕ(t)) 11. 4.12 4.15. 4.12 ϕ B,x d (d B ) 4.16. 4.12 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 12. 23
4.17. K d B ϕ B (t) {g(t) K[t] g(b) = 0} g(b) = 0 ϕ B (t) g(t). 4.18. K d B χ B (t) χ B (t) = det(ti d B) K[t] d 4.19. ϕ B,x (t) ϕ B (t) χ B (t).. ϕ B (B)x = 0 χ B (B) = 0 Cayley-Hamilton 4.20. K B K d x K d {0} 1. x B #(K) d 1 2. ϕ B,x (t) d 3. χ B (t). 1 2 4.15 2 3: 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) 3 2 24
Cayley-Hamilton Cayley-Hamilton 4.21. (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 1 + + 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 1 + + tq 0 ) (AQ n 1 t n 1 + + 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 1 + + AQ 0 ) = χ A (X)I X = A A Q i 5 5.1 K d d B #(K) d 1 25
B χ B B 5.1. d d ϕ(#(k) d 1)/d ( ϕ ) 5.2. d d B. ( 3.4 ) 13. 5.1 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
d : 1 d d : 1 L/K ϕ(#(k) d 1) d 14. 5.1 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 2 1 2 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
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
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 = 0 5.4. 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 2 1.5 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 = 0 5.4 r r g e, g r = e r 29
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 2 + + 1) 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 1 5.3 a = t = g, n = 2 m 1 n s n = 2 m 1 1 1 2 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 + 1 2 7 1 = 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.10. q > 2 (q m 1)/(q 1) 30
6 : 1 0-1 - 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 ) = (0011001110), G(s 1 ) = (1101100111),. S {0, 1} M 2 2 Mersenne Twister [ ] 31
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
+ 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 2 6.4 p k,m (0 t) 0.015 random prob. 0.0125 0.01 0.0075 0.005 0.0025 0 10 12 14 16 18 20 weight random() 1 p 8,31 (0 s) (10 s 22) 31 s 8 1/256=0.00390625 33
0.0048 ran_array 0.0046 0.0044 prob. 0.0042 0.004 0.0038 0.0036 40 45 50 55 60 weight ran array() 1 p 8,100 (0 s) (40 s 60) 100 s 8 1/256=0.00390625 6.3 {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
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 2 6.4 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
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 6.5.1 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
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 2 0 1 e(v w) 0 37
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
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
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 20. 6.8. x 1 = = x M = x, y 1 = = y M = y MacWilliams MacWilliams MacWilliams [7, P.147, Theorem 14] MacWilliams [7, P.158, Eq.(52)] 6.5.2 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
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
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 ) 6.10. (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> ( 6.5.1 ) 6.11. 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 2 6.5.1 f V = R/Z W = Z f : V C f(n) = f(x)e(x n)dx = a( n) R/Z 42
V = Z W = R/Z a : V C â(x) = n Z a(n)e(x n) Poisson C V 6.12. (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) 7 7.1. K?? S, O K f : S S, o : S O K K F 2 43
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
y x + (x ) Defects of MSB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 500 400 300 200 100 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 2 16 MT(MT521) tempering v = 1,..., 32 2 16 k(v) 45
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 11213 5606 3737 2803 2242 1868 nw r for 1601 1401 1245 1121 1019 934 v (w, n, r) = (32, 351, 19) 862 800 747 700 659 622 1 v 32 590 560 533 509 487 467 448 431 415 400 386 373 361 350 MT11213A (w, n, m, r) = (32, 351, 175, 19) 11213 5606 3560 2803 2111 1756 a = E4BD75F5 1405 1401 1055 1053 709 704 u = 11 703 702 701 700 356 352 s = 7,b = 655E5280 351 351 351 350 350 350 (177) t = 15,c = FFD58000 350 350 350 350 350 350 l = 17 350 350 MT11213B (w, n, m, r) = (32, 351, 175, 19) 11213 5606 3565 2803 2113 1759 a = CCAB8EE7 1408 1401 1056 1053 715 704 u = 11 702 702 701 700 355 352 s = 7,b = 31B6AB00 351 351 351 351 350 350 (151) t = 15,c = FFE50000 350 350 350 350 350 350 l = 17 350 350 Upper bounds 19937 9968 6645 4984 3987 3322 nw r for 2848 2492 2215 1993 1812 1661 v (w, n, r) = (32, 624, 31) 1533 1424 1329 1246 1172 1107 1 v 32 1049 996 949 906 866 830 797 766 738 712 687 664 643 623 MT19937 (w, n, m, r) = (32, 624, 397, 31) 19937 9968 6240 4984 3738 3115 a = 9908B0DF 2493 2492 1869 1869 1248 1246 u = 11 1246 1246 1246 1246 623 623 s = 7, b = 9D2C5680 623 623 623 623 623 623 (135) t = 15, c = EFC60000 623 623 623 623 623 623 l = 18 623 623 TT800 (w, n, m, r) = (32, 25, 7, 0) 800 400 250 200 150 125 a = 8EBFD028 100 100 75 75 50 50 u : not exist 50 50 50 50 25 25 s = 7, b = 2B5B2500 25 25 25 25 25 25 (93) t = 15, c = DB8B0000 25 25 25 25 25 25 l =16 25 25 ran array Knuth s new recommendation. 129 64 43 32 25 21 18 16 14 12 11 10 Here we list the trivial 9 9 8 8 7 7 upper bounds. 6 6 6 5 5 5 5 4 4 4 4 4 tempering k(v) try-anderror 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 i=0 46 i=0
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 ]- 7.4. 0 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
F v L F 2 [t 1 ] B 7.5. L 2 k(v)+1 7.6. 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
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
[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), 749 761. [2] Luc Deveroye, Nonuniform random variate generation. Springer-Verlag, 1986. [3],,, 1989. [4] Knuth, D. E. The Art of Computer Programming. Vol. 2. Seminumerical Algorithms 3rd Ed. Addison-Wesley, 1997. [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, 2007. [6] Lenstra, A. K. Factoring multivariate polynomials over finite fields. J. Comput. System Sci. 30, 235-248. [7] F.J. MacWilliams and N.J.A. Sloane, The theory of error correcting code. North-Holland, 1977. [8] Matsumoto, M. and Kurita, Y. Twisted GFSR Generators, ACM Transactions on Modeling and Computer Simulation 2 (1992), 179 194. [9] Matsumoto, M. and Kurita, Y. Twisted GFSR Generators II, ACM Transactions on Modeling and Computer Simulation 4 (1994), 254 266. [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), 3 30. [11] M. Matsumoto and T. Nishimura A Nonempirical Test on the Weight of Pseudorandom Number Generators 381 395 in: Monte Carlo and Quasi- Monte Carlo methods 2000, Springer-Verlag 2002. [12] M. Matsumoto and T. Nishimura Sum-discrepancy test on pseudorandom number generators Mathematics and Computers in Simulation, Vol. 62 (2003), pp 431-442. 50
[13] H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods. SIAM, 1992. [14] Reiter, S. and Stegeman, J.D.: Classical harmonic analysis and locally compact groups. Oxford Science Publications, Oxford, 2000. 51