Fin des travaux pour aujourd'hui

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 5a3324b58e99e2d82aaef87e590f0a21e58e8806..6776b9a5c191ba049212fc27d31b5a5201164efb 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -129,13 +129,13 @@ Boolean  \emph{state}. Having $\mathsf{N}$ Boolean values for these
  cells  leads to the definition of a particular \emph{state  of the
 system}. A sequence which  elements belong to $\llbracket 1;\mathsf{N}
 \rrbracket $ is called a \emph{strategy}. The set of all strategies is
  cells  leads to the definition of a particular \emph{state  of the
 system}. A sequence which  elements belong to $\llbracket 1;\mathsf{N}
 \rrbracket $ is called a \emph{strategy}. The set of all strategies is

-denoted by $\mathbb{S}.$
+denoted by $\llbracket 1, \mathsf{N} \rrbracket^\mathds{N}.$

 
 \begin{definition}
 \label{Def:chaotic iterations}
 The      set       $\mathds{B}$      denoting      $\{0,1\}$,      let
 $f:\mathds{B}^{\mathsf{N}}\longrightarrow  \mathds{B}^{\mathsf{N}}$ be
 
 \begin{definition}
 \label{Def:chaotic iterations}
 The      set       $\mathds{B}$      denoting      $\{0,1\}$,      let
 $f:\mathds{B}^{\mathsf{N}}\longrightarrow  \mathds{B}^{\mathsf{N}}$ be

-a  function  and  $S\in  \mathbb{S}$  be  a  strategy.  The  so-called
+a  function  and  $S\in  \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}$  be  a  strategy.  The  so-called

 \emph{chaotic      iterations}     are     defined      by     $x^0\in
 \mathds{B}^{\mathsf{N}}$ and
 \begin{equation}
 \emph{chaotic      iterations}     are     defined      by     $x^0\in
 \mathds{B}^{\mathsf{N}}$ and
 \begin{equation}


@@ -182,9 +182,9 @@ Consider the phase space:
 G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf}
 \end{equation}
 \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma
 G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf}
 \end{equation}
 \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma

-(S^{n})_{n\in \mathds{N}}\in \mathbb{S}\longrightarrow (S^{n+1})_{n\in
-\mathds{N}}\in \mathbb{S}$ and $i$ is the \emph{initial function} 
-$i:(S^{n})_{n\in \mathds{N}} \in \mathbb{S}\longrightarrow S^{0}\in \llbracket
+(S^{n})_{n\in \mathds{N}}\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}\longrightarrow (S^{n+1})_{n\in
+\mathds{N}}\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}$ and $i$ is the \emph{initial function} 
+$i:(S^{n})_{n\in \mathds{N}} \in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}\longrightarrow S^{0}\in \llbracket

 1;\mathsf{N}\rrbracket$. Then the chaotic iterations defined in
 (\ref{sec:chaotic iterations}) can be described by the following iterations:
 \begin{equation}
 1;\mathsf{N}\rrbracket$. Then the chaotic iterations defined in
 (\ref{sec:chaotic iterations}) can be described by the following iterations:
 \begin{equation}


@@ -233,7 +233,7 @@ 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}$
 \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
+differ in $n$ cells ($d_e$ is indeed the Hamming distance). 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
 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


@@ -419,6 +419,7 @@ the general form:
   x_i^{n-1} &  \text{ if  } i \notin \mathcal{S}^n \\
   \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n.
 \end{array}\right.
   x_i^{n-1} &  \text{ if  } i \notin \mathcal{S}^n \\
   \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n.
 \end{array}\right.

+\label{general CIs}

 \end{equation}
 
 In other words, at the $n^{th}$ iteration, only the cells whose id is
 \end{equation}
 
 In other words, at the $n^{th}$ iteration, only the cells whose id is


@@ -431,7 +432,7 @@ is required in order to study the topological behavior of the system.
 Let us introduce the following function:
 \begin{equation}
 \begin{array}{cccc}
 Let us introduce the following function:
 \begin{equation}
 \begin{array}{cccc}

- \delta: & \llbracket 1; \mathsf{N} \rrbracket \times \mathcal{P}\left(\llbracket 1; \mathsf{N} \rrbracket\right) & \longrightarrow & \mathds{B}\\
+ \chi: & \llbracket 1; \mathsf{N} \rrbracket \times \mathcal{P}\left(\llbracket 1; \mathsf{N} \rrbracket\right) & \longrightarrow & \mathds{B}\\

          & (i,X) & \longmapsto  & \left\{ \begin{array}{ll} 0 & \textrm{if }i \notin X, \\ 1 & \textrm{if }i \in X,  \end{array}\right.
 \end{array} 
 \end{equation}
          & (i,X) & \longmapsto  & \left\{ \begin{array}{ll} 0 & \textrm{if }i \notin X, \\ 1 & \textrm{if }i \in X,  \end{array}\right.
 \end{array} 
 \end{equation}


@@ -440,16 +441,17 @@ where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $
 Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function:
 \begin{equation}
 \begin{array}{lrll}
 Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function:
 \begin{equation}
 \begin{array}{lrll}

-F_{f}: & \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} &
+F_{f}: & \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} &

 \longrightarrow & \mathds{B}^{\mathsf{N}} \\
 \longrightarrow & \mathds{B}^{\mathsf{N}} \\

-& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+f(E)_{k}.\overline{\delta
-(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
+& (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi
+(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%

 \end{array}%
 \end{equation}%
 \end{array}%
 \end{equation}%

-\noindent where + and . are the Boolean addition and product operations.
+where + and . are the Boolean addition and product operations, and $\overline{x}$ 
+is the negation of the Boolean $x$.

 Consider the phase space:
 \begin{equation}
 Consider the phase space:
 \begin{equation}

-\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times
+\mathcal{X} = \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N} \times

 \mathds{B}^\mathsf{N},
 \end{equation}
 \noindent and the map defined on $\mathcal{X}$:
 \mathds{B}^\mathsf{N},
 \end{equation}
 \noindent and the map defined on $\mathcal{X}$:


@@ -457,11 +459,11 @@ Consider the phase space:
 G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf}
 \end{equation}
 \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma
 G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf}
 \end{equation}
 \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma

-(S^{n})_{n\in \mathds{N}}\in \mathbb{S}\longrightarrow (S^{n+1})_{n\in
-\mathds{N}}\in \mathbb{S}$ and $i$ is the \emph{initial function} 
-$i:(S^{n})_{n\in \mathds{N}} \in \mathbb{S}\longrightarrow S^{0}\in \llbracket
-1;\mathsf{N}\rrbracket$. Then the chaotic iterations defined in
-(\ref{sec:chaotic iterations}) can be described by the following iterations:
+(S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in
+\mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}$ and $i$ is the \emph{initial function} 
+$i:(S^{n})_{n\in \mathds{N}} \in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow S^{0}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)$. 
+Then the general chaotic iterations defined in Equation \ref{general CIs} can 
+be described by the following discrete dynamical system:

 \begin{equation}
 \left\{
 \begin{array}{l}
 \begin{equation}
 \left\{
 \begin{array}{l}


@@ -471,14 +473,12 @@ X^{k+1}=G_{f}(X^k).%
 \right.
 \end{equation}%
 
 \right.
 \end{equation}%
 

-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. 
+Another time, a shift function appears as a component of these general chaotic 
+iterations. 

 
 

-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:
+To study the Devaney's chaos property, a distance between two points 
+$X = (S,E), Y = (\check{S},\check{E})$ of $\mathcal{X}$ must be introduced.
+We will reffer it by:

 \begin{equation}
 d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
 \end{equation}
 \begin{equation}
 d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
 \end{equation}


@@ -487,12 +487,16 @@ d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
 \left\{
 \begin{array}{lll}
 \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
 \left\{
 \begin{array}{lll}
 \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%

-}\delta (E_{k},\check{E}_{k})}, \\
+}\delta (E_{k},\check{E}_{k})}\textrm{ is another time the Hamming distance}, \\

 \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
 \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%

-\sum_{k=1}^{\infty }\dfrac{|S^k-\check{S}^k|}{10^{k}}}.%
+\sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.%

 \end{array}%
 \right.
 \end{equation}
 \end{array}%
 \right.
 \end{equation}

+where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as
+$A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$.
+
+

 
 
 \section{Efficient PRNG based on Chaotic Iterations}
 
 
 \section{Efficient PRNG based on Chaotic Iterations}