From: guyeux Date: Sun, 30 Oct 2011 08:28:57 +0000 (+0100) Subject: Fin des travaux pour aujourd'hui X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/556196c81dc8aac11552b716e1352116dfeeae01?ds=inline;hp=8657185ec89ecf42d39c56a9a57ec20e61e20299 Fin des travaux pour aujourd'hui --- diff --git a/prng_gpu.tex b/prng_gpu.tex index 5a3324b..6776b9a 100644 --- 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 -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 -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} @@ -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 -(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} @@ -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}$ -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 @@ -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. +\label{general CIs} \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} - \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} @@ -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} -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}} \\ -& (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}% -\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} -\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}$: @@ -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 -(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} @@ -471,14 +473,12 @@ X^{k+1}=G_{f}(X^k).% \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} @@ -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}% -}\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}}% -\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} +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}