From: couchot Date: Thu, 7 Apr 2016 14:48:53 +0000 (+0200) Subject: hamilton X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/commitdiff_plain/d68de43fbfbc44e3363780b39401bf1d2683f9d8?ds=sidebyside;hp=--cc hamilton --- d68de43fbfbc44e3363780b39401bf1d2683f9d8 diff --git a/biblio.bib b/biblio.bib index c368f01..0857ae7 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1029,3 +1029,54 @@ year = 2013, ee = {http://arxiv.org/abs/1112.5239} } + + +@article{DBLP:journals/combinatorics/BhatS96, + author = {Girish S. Bhat and + Carla D. Savage}, + title = {Balanced Gray Codes}, + journal = {Electr. J. Comb.}, + volume = {3}, + number = {1}, + year = {1996}, + url = {http://www.combinatorics.org/Volume_3/Abstracts/v3i1r25.html}, + timestamp = {Tue, 05 Oct 2004 14:51:02 +0200}, + biburl = {http://dblp.uni-trier.de/rec/bib/journals/combinatorics/BhatS96}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} + + +@Article{Bykov2016, +author="Bykov, I. S.", +title="On locally balanced gray codes", +journal="Journal of Applied and Industrial Mathematics", +year="2016", +volume="10", +number="1", +pages="78--85", +abstract="We consider locally balanced Gray codes.We say that a Gray code is locally balanced if every ``short'' subword in its transition sequence contains all letters of the alphabet |1, 2,..., n{\textasciitilde}. The minimal length of these subwords is the window width of the code. We show that for each n ≥ 3 there exists a Gray code with window width at most n + 3⌊log n⌋.", +issn="1990-4797", +doi="10.1134/S1990478916010099", +url="http://dx.doi.org/10.1134/S1990478916010099" +} + + +@article{Robinson:1981:CS, + author = {Robinson, John P. and Cohn, Martin}, + title = {Counting Sequences}, + journal = {IEEE Trans. Comput.}, + issue_date = {January 1981}, + volume = {30}, + number = {1}, + month = jan, + year = {1981}, + issn = {0018-9340}, + pages = {17--23}, + numpages = {7}, + url = {http://dl.acm.org/citation.cfm?id=1963620.1963622}, + acmid = {1963622}, + publisher = {IEEE Computer Society}, + address = {Washington, DC, USA}, + keywords = {circuit testing, counters, gray codes, hamming distance, transition counts, uniform distance}, +} + diff --git a/evalPRNG/compareFonctionMixingTime.py b/evalPRNG/compareFonctionMixingTime.py index 5ff8251..d5dc782 100644 --- a/evalPRNG/compareFonctionMixingTime.py +++ b/evalPRNG/compareFonctionMixingTime.py @@ -102,12 +102,12 @@ def MarkovMatrixSaut(fbin,n,p2n,lp2nm1): lf= [] #lf +=[ [13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]] #4 #lf += [[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]] #5 -lf += [[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, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]] #6 +#lf += [[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, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]] #6 #lf+= [[47, 58, 57, 44, 51, 42, 41, 60, 63, 22, 37, 53, 19, 54, 48, 32, 45, 14, 13, 46, 11, 43, 33, 8, 7, 36, 39, 4, 34, 50, 1, 40, 29, 62, 61, 30, 59, 27, 17, 56, 55, 20, 23, 52, 18, 2, 49, 24, 31, 10, 9, 28, 3, 26, 25, 12, 15, 38, 21, 5, 35, 6, 0, 16]] #lf += [[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, 96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22, 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66, 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, 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, 68, 7, 6, 65, 1]] #7 -#lf += [[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, 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, 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, 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, 148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122, 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, 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, 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, 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, 39, 134, 133, 5, 131, 34, 9, 128]]#8 pas totally +lf += [[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, 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, 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, 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, 148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122, 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, 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, 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, 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, 39, 134, 133, 5, 131, 34, 9, 128]]#8 pas totally lf +=[[223, 250, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227, 178, 240, 248, 237, 236, 173, 172, 171, 238, 201, 168, 229, 166, 228, 244, 235, 242, 241, 192, 215, 220, 205, 216, 218, 222, 153, 152, 151, 210, 212, 214, 219, 146, 217, 209, 239, 142, 141, 206, 195, 234, 193, 136, 231, 196, 199, 197, 194, 226, 225, 200, 63, 188, 253, 252, 59, 190, 189, 176, 191, 246, 245, 164, 243, 162, 161, 177, 143, 170, 45, 44, 43, 138, 185, 184, 135, 38, 167, 165, 179, 34, 129, 224, 31, 154, 221, 158, 147, 26, 25, 156, 159, 22, 213, 149, 211, 150, 144, 208, 207, 14, 13, 204, 203, 202, 169, 8, 133, 198, 132, 4, 139, 131, 1, 160, 255, 124, 109, 108, 122, 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, 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, 67, 73, 96, 55, 58, 57, 62, 51, 186, 41, 40, 119, 182, 181, 53, 35, 54, 48, 56, 175, 174, 61, 60, 11, 46, 9, 32, 37, 6, 36, 52, 163, 50, 49, 0, 23, 28, 157, 24, 155, 30, 29, 16, 21, 18, 20, 148, 27, 19, 145, 17, 47, 10, 15, 140, 3, 42, 137, 12, 39, 134, 7, 5, 2, 130, 33, 128]] #8 totally diff --git a/generating.tex b/generating.tex index 5b0d393..354058a 100644 --- a/generating.tex +++ b/generating.tex @@ -62,5 +62,6 @@ It has been shown in~\cite[Lemma 3]{bcgr11:ip} that $M$ is regular. There exists thus $b$ such there is an arc between any $x$ and $y$. \end{proof} -Details on the construction of hamiltonian paths in the -$\mathsf{N}$-cube may be found in~\cite[Section 4]{DBLP:conf/secrypt/CouchotHGWB14}. \ No newline at end of file +The next section presents how to build hamiltonian cycles in the +$\mathsf{N}$-cube with the objective to embed them into the +pseudorandom number generator. diff --git a/hamilton.tex b/hamilton.tex index 8f022c6..694bbcf 100644 --- a/hamilton.tex +++ b/hamilton.tex @@ -1,7 +1,7 @@ Many approaches have been developed to solve the problem of building -a Gray code in a $\mathsf{N}$ cube~\cite{}, according to properties +a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties the produced code has to verify. -For instance,~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} focus on +For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on balanced Gray codes. In the transition sequence of these codes, the number of transitions of each element must differ at most by 2. @@ -27,9 +27,130 @@ However, none of the two algorithms is compatible with the second one: balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely, locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016} are not globally balanced. -This section thus show how the non deterministic approach +This section thus shows how the non deterministic approach presented in~\cite{ZanSup04} has been automatized to provide balanced Hamiltonian paths such that, for each subpart, -the number of swiches of each element is as constant as possible. +the number of switches of each element is as uniform as possible. +\subsection{Analysis of the Robinson-Cohn extension algorithm} +As far as we know three works, +namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96}, +and~\cite{ZanSup04} have adressed the probem of providing an approach +to produce balanced gray code. +The authors of~\cite{Robinson:1981:CS} introduced an inductive approach +aiming at producing balanced Gray codes, provided the user gives +a special subsequence of the transition sequence at each induction step. +This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96} +where the authors have explicitely shown how to construct such a subsequence. +Finally the authors of~\cite{ZanSup04} have presented +the \emph{Robinson-Cohn extension} +algorithm. There rigourous presentation of this one +have mainly allowed them to prove two properties. +The former states that if +$\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced. +The latter states that for every $\mathsf{N}$ there +exists a Gray code such that all transition count numbers are +are 2-powers whose exponents are either equal +or differ from each other by 1. +However, the authors do not prove that the approach allows to build +(totally balanced) Gray code. +What follows shows that this fact is established and first recalls the approach. + +Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is +$S_{\mathsf{N}-2}$. What follows is the + \emph{Robinson-Cohn extension} method~\cite{ZanSup04} +which produces a $n$-bits Gray code. + +\begin{enumerate} +\item \label{item:nondet}Let $l$ be an even positive integer. Find +$u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$ +such that $S_{\mathsf{N}-2}$ is the concatenation of +$$ +s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, . . . , s_{i_l-1}, u_{l-2}, s_{i_l}, v +$$ +where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence). +\item Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ + by + $\mathsf{N} - 1, u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$ + respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that + $u^R$ is $u$ in reversed order. + The obtained sequence is further denoted as $U$. +\item Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first +two elements have been exchanged. +\item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$. +\end{enumerate} + +It has been proven in~\cite{ZanSup04} that +$S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code +if $S_{\mathsf{N}-2}$ is. +However, the step~(\ref{item:nondet}) is not a constructive +step that precises how to select the subsequences which ensures that +yielded Gray code is balanced. +Next section shows how to choose the sequence $l$ to have the balancy property. + +\subsection{Balanced Codes} +Let us first recall how to formalize the balancy property of a Gray code. +Let $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence +of a $\mathsf{N}$-bits cyclic Gray code. +The transition sequence +$S = s_1, s_2, \dots, s_{2^n}$, $s_i$, $1 \le i \le 2^\mathsf{N}$, +indicates which bit position changes between +codewords at index $i$ and $i+1$ modulo $2^\mathsf{N}$. +The \emph{transition count} function +$\textit{TC}_{\mathsf{N}} : \{1,\dots, \mathsf{N}\} \rightarrow \{0, \ldots, 2^{\mathsf{N}}\}$ +gives the number of times $i$ occurs in $S$, +\textit{i.e.}, the number of times +the bit $i$ has been switched in $L$. + +The Gray code is \emph{totally balanced} if $\textit{TC}_{\mathsf{N}}$ +is constant (and equal to $\frac{2^{\mathsf{N}}}{\mathsf{N}}$). +It is \emph{balanced} if for any two bit indices $i$ and $j$, +$|\textit{TC}_{\mathsf{N}}(i) - \textit{TC}_{\mathsf{N}}(j)| \le 2$. + + + +\begin{xpl} +Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to +the Hamiltonian cycle that has been removed in $f^*$. +Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is +$\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and $\textit{TC}_3(3)=4$. Such a Gray code is balanced. + +Let now +$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011, 0001, 0101,$ +$0100, 1100, 1101, 1001, 1011, 1010, 1000$ +be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$ $\textit{TC}_4$ is equal to 4 everywhere, this code +is thus totally balanced. + +On the contrary, for the standard $4$-bits Gray code +$L^{\textit{st}}=0000,0001,0011,0010,0110,0111,0101,0100,1100,$ +$1101,1111,1110,1010,1011,1001,1000$, +we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and +the code is neither balanced nor totally balanced. +\end{xpl} + + +\begin{thrm}\label{prop:balanced} +Let $\mathsf{N}$ in $\Nats$, and $a_{\mathsf{N}}$ be defined by +$a_{\mathsf{N}}= 2 \lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \rfloor$. +Then, there exists a sequence $l$ in +step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm +such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ +are $a_{\mathsf{N}}$ or $a_{\mathsf{N}}+2$ +for any $i$, $1 \le i \le \mathsf{N}$. + + + + +\end{thrm} + + + + +\begin{proof} + + + +\end{proof} + +\subsection{Toward a local uniform distribution of switches} diff --git a/main.aux b/main.aux index 9cfaa3d..6f13901 100644 --- a/main.aux +++ b/main.aux @@ -18,7 +18,7 @@ \citation{chgw14oip} \citation{chgw14oip} \citation{DBLP:conf/secrypt/CouchotHGWB14} -\@writefile{toc}{\contentsline {section}{\tocsection {}{2}{\uppercase {Preliminaries}}}{3}} +\@writefile{toc}{\contentsline {section}{\tocsection {}{2}{Preliminaries}}{3}} \newlabel{sec:preliminaries}{{2}{3}} \newlabel{eq:asyn}{{1}{3}} \citation{bcgr11:ip} @@ -51,33 +51,55 @@ \@writefile{toc}{\contentsline {section}{\tocsection {}{4}{Functions with Strongly Connected $\Gamma _{\{b\}}(f)$}}{10}} \newlabel{sec:SCCfunc}{{4}{10}} \citation{bcgr11:ip} -\citation{DBLP:conf/secrypt/CouchotHGWB14} -\@writefile{toc}{\contentsline {section}{\tocsection {}{5}{Stopping Time}}{11}} -\newlabel{sec:hypercube}{{5}{11}} +\citation{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016} +\citation{DBLP:journals/combinatorics/BhatS96,ZanSup04} +\citation{Bykov2016} +\citation{ZanSup04,DBLP:journals/combinatorics/BhatS96} +\citation{Bykov2016} +\citation{ZanSup04} +\@writefile{toc}{\contentsline {section}{\tocsection {}{5}{(Locally) Balanced Hamiltonian Cycle}}{11}} +\newlabel{sec:hamilton}{{5}{11}} +\citation{Robinson:1981:CS} +\citation{DBLP:journals/combinatorics/BhatS96} +\citation{ZanSup04} +\citation{Robinson:1981:CS} +\citation{DBLP:journals/combinatorics/BhatS96} +\citation{ZanSup04} +\citation{ZanSup04} +\citation{ZanSup04} +\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{5.1}{Analysis of the Robinson-Cohn extension algorithm}}{12}} +\newlabel{item:nondet}{{1}{12}} +\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{5.2}{Balanced Codes}}{13}} +\newlabel{prop:balanced}{{5.1}{13}} +\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{5.3}{Toward a local uniform distribution of switches}}{13}} +\@writefile{toc}{\contentsline {section}{\tocsection {}{6}{Stopping Time}}{13}} +\newlabel{sec:hypercube}{{6}{13}} \citation{LevinPeresWilmer2006} -\newlabel{eq:Markov:rairo}{{3}{13}} -\newlabel{lm:h}{{5.2}{13}} +\newlabel{eq:Markov:rairo}{{3}{15}} +\newlabel{lm:h}{{6.2}{15}} \citation{proba} -\newlabel{prop:stop}{{5.4}{14}} -\newlabel{prop:lambda}{{5.5}{14}} -\newlabel{lm:stopprime}{{5.6}{15}} -\@writefile{toc}{\contentsline {section}{\tocsection {}{6}{Experiments}}{15}} -\newlabel{sec:prng}{{6}{15}} -\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces Pseudo Code of the $\chi _{\textit {15Rairo}}$ PRNG\relax }}{16}} -\newlabel{CI Algorithm:2}{{2}{16}} -\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Functions with DSCC Matrix and smallest MT\relax }}{17}} -\newlabel{table:nc}{{1}{17}} -\@writefile{toc}{\contentsline {section}{\tocsection {}{7}{Conclusion}}{17}} +\newlabel{prop:stop}{{6.4}{16}} +\newlabel{prop:lambda}{{6.5}{16}} +\newlabel{lm:stopprime}{{6.6}{17}} +\@writefile{toc}{\contentsline {section}{\tocsection {}{7}{Experiments}}{17}} +\newlabel{sec:prng}{{7}{17}} +\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces Pseudo Code of the $\chi _{\textit {15Rairo}}$ PRNG\relax }}{18}} +\newlabel{CI Algorithm:2}{{2}{18}} +\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Functions with DSCC Matrix and smallest MT\relax }}{19}} +\newlabel{table:nc}{{1}{19}} +\@writefile{toc}{\contentsline {section}{\tocsection {}{8}{Conclusion}}{19}} \bibstyle{alpha} \bibdata{biblio} \bibcite{Banks92}{BBCS92} \bibcite{bcgr11:ip}{BCGR11} \bibcite{Nist10}{BR10} +\bibcite{DBLP:journals/combinatorics/BhatS96}{BS96} +\bibcite{Bykov2016}{Byk16} \bibcite{chgw14oip}{CHG{$^{+}$}14a} +\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces NIST SP 800-22 test results ($\mathbb {P}_T$)\relax }}{20}} +\newlabel{The passing rate}{{2}{20}} +\@writefile{toc}{\contentsline {section}{\tocsection {}{}{References}}{20}} \bibcite{DBLP:conf/secrypt/CouchotHGWB14}{CHG{$^{+}$}14b} -\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces NIST SP 800-22 test results ($\mathbb {P}_T$)\relax }}{18}} -\newlabel{The passing rate}{{2}{18}} -\@writefile{toc}{\contentsline {section}{\tocsection {}{}{References}}{18}} \bibcite{5376454}{CMZ09} \bibcite{Devaney}{Dev89} \bibcite{guyeuxTaiwan10}{GWB10} @@ -85,8 +107,10 @@ \bibcite{LEcuyerS07}{LS07} \bibcite{Marsaglia1996}{Mar96} \bibcite{proba}{MU05} +\bibcite{Robinson:1981:CS}{RC81} \bibcite{915385}{SK01} \bibcite{915396}{SPK01} +\bibcite{ZanSup04}{SZ04} \bibcite{wbg10ip}{WBGF10} \newlabel{tocindent-1}{0pt} \newlabel{tocindent0}{13.28564pt} diff --git a/main.bbl b/main.bbl index 6cb5b6b..e2aaabb 100644 --- a/main.bbl +++ b/main.bbl @@ -19,6 +19,17 @@ E.~Barker and A.~Roginsky. \newblock Draft {N}{I}{S}{T} special publication 800-131 recommendation for the transitioning of cryptographic algorithms and key sizes, 2010. +\bibitem[BS96]{DBLP:journals/combinatorics/BhatS96} +Girish~S. Bhat and Carla~D. Savage. +\newblock Balanced gray codes. +\newblock {\em Electr. J. Comb.}, 3(1), 1996. + +\bibitem[Byk16]{Bykov2016} +I.~S. Bykov. +\newblock On locally balanced gray codes. +\newblock {\em Journal of Applied and Industrial Mathematics}, 10(1):78--85, + 2016. + \bibitem[CHG{\etalchar{+}}14a]{chgw14oip} Jean-Fran\c{c}ois Couchot, Pierre-Cyrille H\'eam, Christophe Guyeux, Qianxue Wang, and Jacques Bahi. @@ -76,6 +87,11 @@ M.~Mitzenmacher and Eli Upfal. \newblock {\em Probability and Computing}. \newblock Cambridge University Press, 2005. +\bibitem[RC81]{Robinson:1981:CS} +John~P. Robinson and Martin Cohn. +\newblock Counting sequences. +\newblock {\em IEEE Trans. Comput.}, 30(1):17--23, January 1981. + \bibitem[SK01]{915385} T.~Stojanovski and L.~Kocarev. \newblock Chaos-based random number generators-part i: analysis [cryptography]. @@ -88,6 +104,12 @@ T.~Stojanovski, J.~Pihl, and L.~Kocarev. \newblock {\em Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on}, 48(3):382--385, Mar 2001. +\bibitem[SZ04]{ZanSup04} +IN~Suparta and AJ~van Zanten. +\newblock Totally balanced and exponentially balanced gray codes. +\newblock {\em Discrete Analysis and Operation Research (Russia)}, + 11(4):81--98, 2004. + \bibitem[WBGF10]{wbg10ip} Qianxue Wang, Jacques Bahi, Christophe Guyeux, and Xiaole Fang. \newblock Randomness quality of {CI} chaotic generators. application to diff --git a/main.blg b/main.blg index 86a026a..b2d7619 100644 --- a/main.blg +++ b/main.blg @@ -1,46 +1,48 @@ -This is BibTeX, Version 0.99d (TeX Live 2013/Debian) +This is BibTeX, Version 0.99d (TeX Live 2015/dev/Debian) Capacity: max_strings=35307, hash_size=35307, hash_prime=30011 The top-level auxiliary file: main.aux The style file: alpha.bst Database file #1: biblio.bib -You've used 15 entries, +Warning--I didn't find a database entry for "" +You've used 19 entries, 2543 wiz_defined-function locations, - 664 strings with 7466 characters, -and the built_in function-call counts, 7127 in all, are: -= -- 715 -> -- 366 -< -- 11 -+ -- 132 -- -- 129 -* -- 524 -:= -- 1142 -add.period$ -- 50 -call.type$ -- 15 -change.case$ -- 102 -chr.to.int$ -- 14 -cite$ -- 15 -duplicate$ -- 282 -empty$ -- 499 -format.name$ -- 144 -if$ -- 1499 + 695 strings with 8037 characters, +and the built_in function-call counts, 8579 in all, are: += -- 865 +> -- 431 +< -- 12 ++ -- 152 +- -- 149 +* -- 635 +:= -- 1386 +add.period$ -- 62 +call.type$ -- 19 +change.case$ -- 125 +chr.to.int$ -- 18 +cite$ -- 19 +duplicate$ -- 338 +empty$ -- 604 +format.name$ -- 169 +if$ -- 1790 int.to.chr$ -- 2 int.to.str$ -- 0 -missing$ -- 17 -newline$ -- 80 -num.names$ -- 47 -pop$ -- 107 +missing$ -- 21 +newline$ -- 100 +num.names$ -- 59 +pop$ -- 119 preamble$ -- 1 -purify$ -- 119 +purify$ -- 146 quote$ -- 0 -skip$ -- 248 +skip$ -- 299 stack$ -- 0 -substring$ -- 382 -swap$ -- 76 -text.length$ -- 11 -text.prefix$ -- 2 +substring$ -- 463 +swap$ -- 80 +text.length$ -- 12 +text.prefix$ -- 3 top$ -- 0 -type$ -- 108 +type$ -- 140 warning$ -- 0 -while$ -- 64 -width$ -- 17 -write$ -- 207 +while$ -- 80 +width$ -- 21 +write$ -- 259 +(There was 1 warning) diff --git a/main.log b/main.log index 9a092cc..749adc1 100644 --- a/main.log +++ b/main.log @@ -1,4 +1,4 @@ -This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.11.13) 1 APR 2016 11:05 +This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.11.13) 7 APR 2016 10:48 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -1301,8 +1301,32 @@ Underfull \hbox (badness 10000) in paragraph at lines 472--477 ; :::; a[]; :::; a[];$ [] -[9 <./graphe1.pdf> <./graphe2.pdf>]) (./generating.tex [10]) (./stopping.tex -[11] [12] [13] [14]) (./prng.tex [15] +[9 <./graphe1.pdf> <./graphe2.pdf>]) (./generating.tex [10]) (./hamilton.tex +[11] [12] +Overfull \hbox (104.68428pt too wide) in paragraph at lines 119--124 +[]\T1/cmr/m/it/10 Let now $\OML/cmm/m/it/10 L[] \OT1/cmr/m/n/10 = 0000\OML/cmm/ +m/it/10 ; \OT1/cmr/m/n/10 0010\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0110\OML/cmm/m +/it/10 ; \OT1/cmr/m/n/10 1110\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1111\OML/cmm/m/ +it/10 ; \OT1/cmr/m/n/10 0111\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0011\OML/cmm/m/i +t/10 ; \OT1/cmr/m/n/10 0001\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0101\OML/cmm/m/it +/10 ;$ $\OT1/cmr/m/n/10 0100\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1100\OML/cmm/m/i +t/10 ; \OT1/cmr/m/n/10 1101\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1001\OML/cmm/m/it +/10 ; \OT1/cmr/m/n/10 1011\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1010\OML/cmm/m/it/ +10 ; \OT1/cmr/m/n/10 1000$ + [] + + +Overfull \hbox (116.14502pt too wide) in paragraph at lines 125--130 +[]\T1/cmr/m/it/10 On the con-trary, for the stan-dard $\OT1/cmr/m/n/10 4$\T1/cm +r/m/it/10 -bits Gray code $\OML/cmm/m/it/10 L[] \OT1/cmr/m/n/10 = 0000\OML/cmm/ +m/it/10 ; \OT1/cmr/m/n/10 0001\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0011\OML/cmm/m +/it/10 ; \OT1/cmr/m/n/10 0010\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0110\OML/cmm/m/ +it/10 ; \OT1/cmr/m/n/10 0111\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0101\OML/cmm/m/i +t/10 ; \OT1/cmr/m/n/10 0100\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1100\OML/cmm/m/it +/10 ;$ + [] + +) (./stopping.tex [13] [14] [15] [16]) (./prng.tex [17] LaTeX Warning: Command \textcircled invalid in math mode on input line 64. @@ -1347,7 +1371,7 @@ LaTeX Warning: Command \textcircled invalid in math mode on input line 172. LaTeX Warning: Command \textcircled invalid in math mode on input line 172. -[16] +[18] LaTeX Warning: Command \textcircled invalid in math mode on input line 231. @@ -1386,21 +1410,21 @@ Overfull \hbox (4.26556pt too wide) in paragraph at lines 229--250 ) (./conclusion.tex Missing character: There is no p in font dsrom8! Missing character: There is no p in font dsrom8! - [17]) (./main.bbl [18] -Underfull \hbox (badness 10000) in paragraph at lines 70--73 + [19]) (./main.bbl [20] +Underfull \hbox (badness 10000) in paragraph at lines 81--84 []\T1/cmr/m/n/8 G. Marsaglia. Diehard: a bat-tery of tests of ran-dom-ness. [] -) [19] (./main.aux) ) +) [21] (./main.aux) ) (\end occurred inside a group at level 1) ### simple group (level 1) entered at line 10 ({) ### bottom level Here is how much of TeX's memory you used: - 22182 strings out of 494950 - 431307 string characters out of 6179039 + 22192 strings out of 494950 + 431459 string characters out of 6179039 561594 words of memory out of 5000000 - 24709 multiletter control sequences out of 15000+600000 + 24716 multiletter control sequences out of 15000+600000 28957 words of font info for 91 fonts, out of 8000000 for 9000 197 hyphenation exceptions out of 8191 54i,17n,75p,539b,695s stack positions out of 5000i,500n,10000p,200000b,80000s @@ -1445,10 +1469,10 @@ pe1/public/amsfonts/symbols/msbm10.pfb> -Output written on main.pdf (19 pages, 467540 bytes). +Output written on main.pdf (21 pages, 479708 bytes). PDF statistics: - 813 PDF objects out of 1000 (max. 8388607) - 210 compressed objects within 3 object streams + 826 PDF objects out of 1000 (max. 8388607) + 214 compressed objects within 3 object streams 0 named destinations out of 1000 (max. 500000) 28 words of extra memory for PDF output out of 10000 (max. 10000000) diff --git a/main.pdf b/main.pdf index aff26ba..6d1894c 100644 Binary files a/main.pdf and b/main.pdf differ diff --git a/main.tex b/main.tex index 465fbf5..773caee 100644 --- a/main.tex +++ b/main.tex @@ -108,7 +108,7 @@ the classical statistical tests. \section{Introduction} \input{intro} - \section{\uppercase{Preliminaries}}\label{sec:preliminaries} +\section{Preliminaries}\label{sec:preliminaries} \input{preliminaries} \section{Proof Of Chaos}\label{sec:proofOfChaos} @@ -117,6 +117,10 @@ the classical statistical tests. \section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc} \input{generating} +\section{(Locally) Balanced Hamiltonian Cycle}\label{sec:hamilton} +\input{hamilton} + + \section{Stopping Time}\label{sec:hypercube} \input{stopping}