X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/6e51d690ec930ddb226ef13eb704e9dec7d2ea9f..016edf5f7ca01fdf537b4abcb6de87d75c604510:/prng_gpu.tex?ds=sidebyside

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 985faee..57526f2 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -48,9 +48,10 @@ This is the abstract
 
 Interet des itérations chaotiques pour générer des nombre alea\\
 Interet de générer des nombres alea sur GPU
+\alert{RC, un petit state-of-the-art sur les PRNGs sur GPU ?}
 ...
 
-% >>>>>>>>>>>>>>>>>>>>>> Basic recalls <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
+
 \section{Basic Recalls}
 \label{section:BASIC RECALLS}
 This section is devoted to basic definitions and terminologies in the fields of topological chaos and chaotic iterations.
@@ -163,6 +164,39 @@ X^{k+1}=G_{f}(X^k).%
 
 With this formulation, a shift function appears as a component of chaotic iterations. The shift function is a famous example of a chaotic map~\cite{Devaney} but its presence is not sufficient enough to claim $G_f$ as chaotic. 
 
+To study this claim, a new distance between two points $X = (S,E), Y = (\check{S},\check{E})\in
+\mathcal{X}$ has been introduced in \cite{guyeux10} as follows:
+\begin{equation*}
+d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
+\end{equation*}
+\noindent where
+\begin{equation*}
+\left\{
+\begin{array}{lll}
+\displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
+}\delta (E_{k},\check{E}_{k})}, \\
+\displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
+\sum_{k=1}^{\infty }\dfrac{|S^k-\check{S}^k|}{10^{k}}}.%
+\end{array}%
+\right.
+\end{equation*}
+
+
+This new distance has been introduced to satisfy the following requirements.
+\begin{itemize}
+\item When the number of different cells between two systems is increasing, then their distance should increase too.
+\item In addition, if two systems present the same cells and their respective strategies start with the same terms, then the distance between these two points must be small because the evolution of the two systems will be the same for a while. Indeed, the two dynamical systems start with the same initial condition, use the same update function, and as strategies are the same for a while, then components that are updated are the same too.
+\end{itemize}
+The distance presented above follows these recommendations. Indeed, if the floor value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ differ in $n$ cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the differences between strategies $S$ and $\check{S}$. More precisely, this floating part is less than $10^{-k}$ if and only if the first $k$ terms of the two strategies are equal. Moreover, if the $k^{th}$ digit is nonzero, then the $k^{th}$ terms of the two strategies are different.
+
+Finally, it has been established in \cite{guyeux10} that,
+
+\begin{proposition}
+Let $f$ be a map from $\mathds{B}^n$ to itself. Then $G_{f}$ is continuous in the metric space $(\mathcal{X},d)$.
+\end{proposition}
+
+The chaotic property of $G_f$ has been firstly established for the vectorial Boolean negation \cite{guyeux10}. To obtain a characterization, we have secondly introduced the notion of asynchronous iteration graph recalled bellow.
+
 Let $f$ be a map from $\mathds{B}^n$ to itself. The
 {\emph{asynchronous iteration graph}} associated with $f$ is the
 directed graph $\Gamma(f)$ defined by: the set of vertices is
@@ -173,7 +207,7 @@ path from $x$ to $x'$ in $\Gamma(f)$ if and only if there exists a
 strategy $s$ such that the parallel iteration of $G_f$ from the
 initial point $(s,x)$ reaches the point $x'$.
 
-We have proven in \cite{FCT11} that,
+We have finally proven in \cite{FCT11} that,
 
 
 \begin{theorem}
@@ -182,8 +216,8 @@ Let $f:\mathds{B}^n\to\mathds{B}^n$. $G_f$ is chaotic  (according to  Devaney)
 if and only if $\Gamma(f)$ is strongly connected.
 \end{theorem}
 
-
-
+This result of chaos has lead us to study the possibility to build a pseudo-random number generator (PRNG) based on the chaotic iterations. 
+As $G_f$, defined on the domain   $\llbracket 1 ;  n \rrbracket^{\mathds{N}}  \times \mathds{B}^n$, is build from Boolean networks $f : \mathds{B}^n \rightarrow \mathds{B}^n$, we can preserve the theoretical properties on $G_f$ during implementations (due to the discrete nature of $f$). It is as if $\mathds{B}^n$ represents the memory of the computer whereas $\llbracket 1 ;  n \rrbracket^{\mathds{N}}$ is its input stream (the seeds, for instance).
 
 \section{Application to Pseudo-Randomness}
 
@@ -251,6 +285,11 @@ We have proven in \cite{FCT11} that,
 \end{theorem} 
 
 
+
+\alert{Mettre encore un peu de blabla sur le PRNG, puis enchaîner en disant que, ok, on peut préserver le chaos quand on passe sur machine, mais que le chaos dont il s'agit a été prouvé pour une distance bizarroïde sur un espace non moins hémoroïde, d'où ce qui suit}
+
+
+
 \section{The relativity of disorder}
 \label{sec:de la relativité du désordre}