bla bla:

[16dcc.git] / prng.tex

diff --git a/prng.tex b/prng.tex
index 6af2803ad6918b63ebfd02793a74d5e87399ab41..4ad9989ba178e8587800b6e3dc0f85ff136d8b13 100644 (file)
--- a/prng.tex
+++ b/prng.tex
@@ -1,7 +1,7 @@
-Let us finally present the pseudorandom number generator $\chi_{\textit{15Rairo}}$,
+Let us finally present the pseudorandom number generator $\chi_{\textit{16HamG}}$,

 which is based on random walks in $\Gamma_{\{b\}}(f)$. 
 More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow 
 which is based on random walks in $\Gamma_{\{b\}}(f)$. 
 More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow 

-\Bool^\mathsf{N}$,
+\Bool^{\mathsf{N}}$,

 a PRNG \textit{Random},
 an integer $b$ that corresponds to an iteration number (\textit{i.e.}, the length of the walk), and 
 an initial configuration $x^0$. 
 a PRNG \textit{Random},
 an integer $b$ that corresponds to an iteration number (\textit{i.e.}, the length of the walk), and 
 an initial configuration $x^0$. 


@@ -16,19 +16,19 @@ This PRNG is formalized in Algorithm~\ref{CI Algorithm:2}.
 
 \begin{algorithm}[ht]
 %\begin{scriptsize}
 
 \begin{algorithm}[ht]
 %\begin{scriptsize}

-\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)}
-\KwOut{a configuration $x$ ($n$ bits)}
+\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a configuration $x$ ($\mathsf{N}$ bits)}

 $x\leftarrow x^0$\;
 \For{$i=0,\dots,b-1$}
 {
 \If{$\textit{Random}(1) \neq 0$}{
 $x\leftarrow x^0$\;
 \For{$i=0,\dots,b-1$}
 {
 \If{$\textit{Random}(1) \neq 0$}{

-$s\leftarrow{\textit{Random}(n)}$\;
-$x\leftarrow{F_f(s,x)}$\;
+$s^0\leftarrow{\textit{Random}(\mathsf{N})}$\;
+$x\leftarrow{F_f(x,s^0)}$\;

 }
 }
 return $x$\;
 %\end{scriptsize}
 }
 }
 return $x$\;
 %\end{scriptsize}

-\caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG}
+\caption{Pseudo Code of the $\chi_{\textit{16HamG}}$ PRNG}

 \label{CI Algorithm:2}
 \end{algorithm}
 
 \label{CI Algorithm:2}
 \end{algorithm}
 


@@ -47,14 +47,14 @@ Sect.~\ref{sec:hypercube}.
 
 Notice that the chaos property of $G_f$ given in Sect.\ref{sec:proofOfChaos}
 only requires that the graph $\Gamma_{\{b\}}(f)$ is strongly connected.
 
 Notice that the chaos property of $G_f$ given in Sect.\ref{sec:proofOfChaos}
 only requires that the graph $\Gamma_{\{b\}}(f)$ is strongly connected.

-Since the $\chi_{\textit{15Rairo}}$ algorithm 
+Since the $\chi_{\textit{16HamG}}$ algorithm 

 only adds probability constraints on existing edges, 
 it preserves this property. 
 
 
 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated 
 the functions according to the method 
 only adds probability constraints on existing edges, 
 it preserves this property. 
 
 
 For each number $\mathsf{N}=4,5,6,7,8$ of bits, we have generated 
 the functions according to the method 

-given in Sect.~\ref{sec:SCCfunc}. 
+given in Sect.~\ref{sec:hamilton}.

 % MENTION FILTRAGE POSSIBLE LORS DE CONSTRUCTION... (SCV) 
 For each $\mathsf{N}$, we have then restricted this evaluation to the function 
 whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo})) 
 % MENTION FILTRAGE POSSIBLE LORS DE CONSTRUCTION... (SCV) 
 For each $\mathsf{N}$, we have then restricted this evaluation to the function 
 whose Markov Matrix (issued from Eq.~(\ref{eq:Markov:rairo})) 


@@ -69,137 +69,158 @@ In other words,  the image of $3~(0011)$ by $\textcircled{a}$ is $14~(1110)$:
 it is obtained as  the  binary  value  of  the  fourth element  in  
 the  second  list (namely~14).  
 
 it is obtained as  the  binary  value  of  the  fourth element  in  
 the  second  list (namely~14).  
 

-In this table the column 
-that is labeled with $b$ (respectively by $E[\tau]$)
+In this table the column that is labeled with $b$ %(respectively by $E[\tau]$)

 gives the practical mixing time 
 gives the practical mixing time 

-where the deviation to the standard distribution is lesser than $10^{-6}$
-(resp. the theoretical upper bound of stopping time as described in 
-Sect.~\ref{sec:hypercube}).
+where the deviation to the standard distribution is lesser than $10^{-6}$.
+%(resp. the theoretical upper bound of stopping time as described in Sect.~\ref{sec:hypercube}).

 
 
 
 \begin{table*}[t]
 \begin{center}
 \begin{scriptsize}
 
 
 
 \begin{table*}[t]
 \begin{center}
 \begin{scriptsize}

-\begin{tabular}{|c|c|c|c|c|}
+\begin{tabular}{|c|c|c|c|}

 \hline
 Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$ 
 \hline
 Function $f$ & $f(x)$, for $x$ in $(0,1,2,\hdots,2^n-1)$ & $\mathsf{N}$ & $b$ 

-&$E[\tau]$\\ 
+\\ 

 \hline
 %%%%% n= 4
 \hline
 %%%%% n= 4

-$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64&154\\
+$\textcircled{a}$&[13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]&4&64\\

 \hline
 %%%%% n= 5
 $\textcircled{b}$& 
 \hline
 %%%%% n= 5
 $\textcircled{b}$& 

-[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 & 236\\
+[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, & 5 & 78 \\

 &
  31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]
 &
  31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]

-&&&\\
+&&\\

 %%%%% n= 6
 \hline
 &
 [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,
 %%%%% n= 6
 \hline
 &
 [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49,

-&&&\\
+&&\\

 &
  15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,
 &
  15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63,

-&&&\\
+&&\\

 $\textcircled{c}$&
  26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 
 $\textcircled{c}$&
  26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 

-&6&88&335\\
+&6&88\\

 &
 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]
 &
 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]

-&&&\\
+&&\\

 %%%%% n= 7
 \hline
 &
 %%%%% n= 7
 \hline
 &

+[111, 124, 93, 120, 122, 90, 113, 88, 115, 126, 125, 84, 123, 98, 
+&&\\
+&112, 96, 109, 106, 77, 110, 99, 74, 104, 72, 71, 100, 117, 116, 
+&&\\
+&103, 102, 65, 97, 31, 86, 95, 28, 27, 91, 121, 92, 119, 118, 69, 
+&&\\
+&68, 87, 114, 89, 81, 15, 76, 79, 108, 107, 10, 105, 8, 7, 6, 101, 
+&&\\
+$\textcircled{d}$&70, 75, 82, 64, 0, 127, 54, 53, 62, 51, 59, 56, 60, 39, 52, 37, 
+&&\\
+&36, 55, 58, 57, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 33, 
+&&\\
+&38, 43, 50, 32, 48, 29, 94, 61, 24, 26, 18, 17, 25, 19, 30, 85, 
+&&\\
+&22, 83, 2, 16, 80, 13, 78, 9, 14, 3, 11, 73, 12, 23, 4, 21, 20, 
+&&\\
+&67, 66, 5, 1]
+
+
+
+
+
+
+

 [111, 94, 93, 116, 122, 90, 125, 88, 115, 126, 119, 84, 123, 98,
 [111, 94, 93, 116, 122, 90, 125, 88, 115, 126, 119, 84, 123, 98,

-&&&\\
+&&\\

 &
  81, 120, 109, 106, 105, 110, 99, 107, 104, 72, 71, 118,  117, 
 &
  81, 120, 109, 106, 105, 110, 99, 107, 104, 72, 71, 118,  117, 

- &&&\\
+ &&\\

 &
 96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22, 
 &
 96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22, 

-&&&\\
-$\textcircled{d}$& 
+&&\\

 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66,
 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66,

-&7 & 99&450\\
+&7 & 99\\

 
 & 
  101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38,
 
 & 
  101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38,

-&&&\\
+&&\\

 &
  37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 
 &
  37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 

-&&&\\
+&&\\

 &
 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, 26, 18, 89, 25, 87, 30, 
 &
 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, 26, 18, 89, 25, 87, 30, 

-&&&\\
+&&\\

 &
 23, 4, 27, 2, 16, 80, 31, 78, 15, 14, 3, 11, 8, 12, 5, 70, 21, 
 &
 23, 4, 27, 2, 16, 80, 31, 78, 15, 14, 3, 11, 8, 12, 5, 70, 21, 

-&&&\\
+&&\\

 &
 68, 7, 6, 65, 1]
 &
 68, 7, 6, 65, 1]

-&&&\\
+&&\\

 
 
 %%%%%n=8
 \hline
 &
 [223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227, 
 
 
 %%%%%n=8
 \hline
 &
 [223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227, 

-&&&\\
+&&\\

 &
 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, 229, 166, 
 &
 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, 229, 166, 

-&&&\\
+&&\\

 &
 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, 218, 222, 221, 
 &
 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, 218, 222, 221, 

-&&&\\
+&&\\

 &
 208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 202, 207, 140, 
 &
 208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 202, 207, 140, 

-&&&\\
+&&\\

 &
 139, 234, 193, 204, 135, 196, 199, 132, 194, 130, 225, 200, 159, 
 &
 139, 234, 193, 204, 135, 196, 199, 132, 194, 130, 225, 200, 159, 

-&&&\\
+&&\\

 &
 62, 185, 252, 59, 250, 169, 56, 191, 246, 245, 52, 243, 50, 176, 
 &
 62, 185, 252, 59, 250, 169, 56, 191, 246, 245, 52, 243, 50, 176, 

-&&&\\
+&&\\

 &
 48, 173, 238, 189, 44, 235, 42, 137, 184, 231, 38, 37, 228, 35,
 &
 48, 173, 238, 189, 44, 235, 42, 137, 184, 231, 38, 37, 228, 35,

-&&&\\
+&&\\

 &
 226, 177, 224, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146,
 &
 226, 177, 224, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146,

-&&&\\
+&&\\

 &
 148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129,
 &
 148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129,

-&&&\\
+&&\\

 $\textcircled{e}$&
 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122,
 $\textcircled{e}$&
 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122,

-&8&110&582\\
+&8&110\\

 &
  126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106,
 &
  126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106,

-&&&\\
+&&\\

 &
  111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65, 
 &
  111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65, 

-&&&\\
+&&\\

 &
 104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86,
 &
 104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86,

-&&&\\
+&&\\

 &
 80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75,
 &
 80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75,

-&&&\\
+&&\\

 &
 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, 40, 119, 182, 181, 
 &
 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, 40, 119, 182, 181, 

-&&&\\
+&&\\

 &
 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, 46, 57, 32, 167, 6,
 &
 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, 46, 57, 32, 167, 6,

-&&&\\
+&&\\

 &
  36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19, 27, 17, 28, 31, 
 &
  36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19, 27, 17, 28, 31, 

-&&&\\
+&&\\

 &
 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, 138, 41, 12, 
 &
 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, 138, 41, 12, 

-&&&\\
+&&\\

 &
 39, 134, 133, 5, 131, 34, 9, 128]
 &
 39, 134, 133, 5, 131, 34, 9, 128]

-&&&\\
+&&\\

 \hline
 \end{tabular}
 \end{scriptsize}
 \hline
 \end{tabular}
 \end{scriptsize}