X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/01d6ea25639436faca9b43ab4c739ec2f86a24c7..ab00f2199b5e43ebaf804194d54a87090dc32ca7:/prng_gpu.tex?ds=sidebyside

diff --git a/prng_gpu.tex b/prng_gpu.tex
index c505685..65c2f41 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -4,8 +4,30 @@
 \usepackage{fullpage}
 \usepackage{fancybox}
 \usepackage{amsmath}
+\usepackage{amscd}
 \usepackage{moreverb}
 \usepackage{commath}
+\usepackage[standard]{ntheorem}
+
+% Pour mathds : les ensembles IR, IN, etc.
+\usepackage{dsfont}
+
+% Pour avoir des intervalles d'entiers
+\usepackage{stmaryrd}
+
+\usepackage{graphicx}
+% Pour faire des sous-figures dans les figures
+\usepackage{subfigure}
+
+\newtheorem{notation}{Notation}
+
+\newcommand{\X}{\mathcal{X}}
+\newcommand{\Go}{G_{f_0}}
+\newcommand{\B}{\mathds{B}}
+\newcommand{\N}{\mathds{N}}
+\newcommand{\BN}{\mathds{B}^\mathsf{N}}
+\let\sur=\overline
+
 
 \title{Efficient generation of pseudo random numbers based on chaotic iterations on GPU}
 \begin{document}
@@ -25,6 +47,169 @@ Interet de générer des nombres alea sur GPU
 
 Présentation des itérations chaotiques
 
+
+
+\section{The phase space is an interval of the real line}
+
+\subsection{Toward a topological semiconjugacy}
+
+In what follows, our intention is to establish, by using a topological semiconjugacy, that chaotic iterations over $\mathcal{X}$ can be described as iterations on a real interval. To do so, we must firstly introduce some notations and terminologies. 
+
+Let $\mathcal{S}_\mathsf{N}$ be the set of sequences belonging into $\llbracket 1; \mathsf{N}\rrbracket$ and $\mathcal{X}_{\mathsf{N}} = \mathcal{S}_\mathsf{N} \times \B^\mathsf{N}$.
+
+
+\begin{definition}
+The function $\varphi: \mathcal{S}_{10} \times\mathds{B}^{10} \rightarrow \big[ 0, 2^{10} \big[$ is defined by:
+$$
+\begin{array}{cccl}
+\varphi: & \mathcal{X}_{10} = \mathcal{S}_{10} \times\mathds{B}^{10}& \longrightarrow & \big[ 0, 2^{10} \big[ \\
+ & (S,E) = \left((S^0, S^1, \hdots ); (E_0, \hdots, E_9)\right) & \longmapsto & \varphi \left((S,E)\right)
+\end{array}
+$$
+\noindent where $\varphi\left((S,E)\right)$ is the real number:
+\begin{itemize}
+\item whose integral part $e$ is $\displaystyle{\sum_{k=0}^9 2^{9-k} E_k}$, that is, the binary digits of $e$ are $E_0 ~ E_1 ~ \hdots ~ E_9$.
+\item whose decimal part $s$ is equal to $s = 0,S^0~ S^1~ S^2~ \hdots = \sum_{k=1}^{+\infty} 10^{-k} S^{k-1}.$ 
+\end{itemize}
+\end{definition}
+
+
+
+$\varphi$ realizes the association between a point of $\mathcal{X}_{10}$ and a real number into $\big[ 0, 2^{10} \big[$. We must now translate the chaotic iterations $\Go$ on this real interval. To do so, two intermediate functions over $\big[ 0, 2^{10} \big[$ must be introduced:
+
+
+\begin{definition}
+\label{def:e et s}
+Let $x \in \big[ 0, 2^{10} \big[$ and:
+\begin{itemize}
+\item $e_0, \hdots, e_9$ the binary digits of the integral part of $x$: $\displaystyle{\lfloor x \rfloor = \sum_{k=0}^{9} 2^{9-k} e_k}$.
+\item $(s^k)_{k\in \mathds{N}}$ the digits of $x$, where the chosen decimal decomposition of $x$ is the one that does not have an infinite number of 9: 
+$\displaystyle{x = \lfloor x \rfloor + \sum_{k=0}^{+\infty} s^k 10^{-k-1}}$.
+\end{itemize}
+$e$ and $s$ are thus defined as follows:
+$$
+\begin{array}{cccl}
+e: & \big[ 0, 2^{10} \big[ & \longrightarrow & \mathds{B}^{10} \\
+ & x & \longmapsto & (e_0, \hdots, e_9)
+\end{array}
+$$
+\noindent and
+$$
+\begin{array}{cccl}
+s: & \big[ 0, 2^{10} \big[ & \longrightarrow & \llbracket 0, 9 \rrbracket^{\mathds{N}} \\
+ & x & \longmapsto & (s^k)_{k \in \mathds{N}}
+\end{array}
+$$
+\end{definition}
+
+We are now able to define the function $g$, whose goal is to translate the chaotic iterations $\Go$ on an interval of $\mathds{R}$.
+
+\begin{definition}
+$g:\big[ 0, 2^{10} \big[ \longrightarrow \big[ 0, 2^{10} \big[$ is defined by:
+$$
+\begin{array}{cccl}
+g: & \big[ 0, 2^{10} \big[ & \longrightarrow & \big[ 0, 2^{10} \big[ \\
+& \\
+ & x & \longmapsto & g(x)
+\end{array}
+$$
+\noindent where g(x) is the real number of $\big[ 0, 2^{10} \big[$ defined bellow:
+\begin{itemize}
+\item its integral part has a binary decomposition equal to $e_0', \hdots, e_9'$, with:
+$$
+e_i' = \left\{
+\begin{array}{ll}
+e(x)_i & \textrm{ if } i \neq s^0\\
+e(x)_i + 1 \textrm{ (mod 2)} & \textrm{ if } i = s^0\\
+\end{array}
+\right.
+$$
+\item whose decimal part is $s(x)^1, s(x)^2, \hdots$
+\end{itemize}
+\end{definition}
+
+\bigskip
+
+
+In other words, if $x = \displaystyle{\sum_{k=0}^{9} 2^{9-k} e_k +  \sum_{k=0}^{+\infty} s^{k} ~10^{-k-1}}$, then: $$g(x) = \displaystyle{\sum_{k=0}^{9} 2^{9-k} (e_k + \delta(k,s^0) \textrm{ (mod 2)}) +  \sum_{k=0}^{+\infty} s^{k+1} 10^{-k-1}}.$$
+
+\subsection{Defining a metric on $\big[ 0, 2^{10} \big[$}
+
+Numerous metrics can be defined on the set $\big[ 0, 2^{10} \big[$, the most usual one being the Euclidian distance recalled bellow:
+
+\begin{notation}
+\index{distance!euclidienne}
+$\Delta$ is the Euclidian distance on $\big[ 0, 2^{10} \big[$, that is, $\Delta(x,y) = |y-x|^2$.
+\end{notation}
+
+\medskip
+
+This Euclidian distance does not reproduce exactly the notion of proximity induced by our first distance $d$ on $\X$. Indeed $d$ is finer than $\Delta$. This is the reason why we have to introduce the following metric:
+
+
+
+\begin{definition}
+Let $x,y \in \big[ 0, 2^{10} \big[$.
+$D$ denotes the function from $\big[ 0, 2^{10} \big[^2$ to $\mathds{R}^+$ defined by: $D(x,y) = D_e\left(e(x),e(y)\right) + D_s\left(s(x),s(y)\right)$, where:
+\begin{center}
+$\displaystyle{D_e(E,\check{E}) = \sum_{k=0}^\mathsf{9} \delta (E_k, \check{E}_k)}$, ~~and~ $\displaystyle{D_s(S,\check{S}) = \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
+\end{center}
+\end{definition}
+
+\begin{proposition}
+$D$ is a distance on $\big[ 0, 2^{10} \big[$.
+\end{proposition}
+
+\begin{proof}
+The three axioms defining a distance must be checked.
+\begin{itemize}
+\item $D \geqslant 0$, because everything is positive in its definition. If $D(x,y)=0$, then $D_e(x,y)=0$, so the integral parts of $x$ and $y$ are equal (they have the same binary decomposition). Additionally, $D_s(x,y) = 0$, then $\forall k \in \mathds{N}^*, s(x)^k = s(y)^k$. In other words, $x$ and $y$ have the same $k-$th decimal digit, $\forall k \in \mathds{N}^*$. And so $x=y$.
+\item $D(x,y)=D(y,x)$.
+\item Finally, the triangular inequality is obtained due to the fact that both $\delta$ and $\Delta(x,y)=|x-y|$ satisfy it.
+\end{itemize}
+\end{proof}
+
+
+The convergence of sequences according to $D$ is not the same than the usual convergence related to the Euclidian metric. For instance, if $x^n \to x$ according to $D$, then necessarily the integral part of each $x^n$ is equal to the integral part of $x$ (at least after a given threshold), and the decimal part of $x^n$ corresponds to the one of $x$ ``as far as required''.
+To illustrate this fact, a comparison between $D$ and the Euclidian distance is given Figure \ref{fig:comparaison de distances}. These illustrations show that $D$ is richer and more refined than the Euclidian distance, and thus is more precise.
+
+
+\begin{figure}[t]
+\begin{center}
+  \subfigure[Function $x \to dist(x;1,234) $ on the interval $(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien.pdf}}\quad
+  \subfigure[Function $x \to dist(x;3) $ on the interval $(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien2.pdf}}
+\end{center}
+\caption{Comparison between $D$ (in blue) and the Euclidian distane (in green).}
+\label{fig:comparaison de distances}
+\end{figure}
+
+
+
+
+\subsection{The semiconjugacy}
+
+It is now possible to define a topological semiconjugacy between $\mathcal{X}$ and an interval of $\mathds{R}$:
+
+\begin{theorem}
+Chaotic iterations on the phase space $\mathcal{X}$ are simple iterations on $\mathds{R}$, which is illustrated by the semiconjugacy of the diagram bellow:
+\begin{equation*}
+\begin{CD}
+\left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right) @>G_{f_0}>> \left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right)\\
+    @V{\varphi}VV                    @VV{\varphi}V\\
+\left( ~\big[ 0, 2^{10} \big[, D~\right)  @>>g> \left(~\big[ 0, 2^{10} \big[, D~\right)
+\end{CD}
+\end{equation*}
+\end{theorem}
+
+\begin{proof}
+$\varphi$ has been constructed in order to be continuous and onto.
+\end{proof}
+
+In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N} \big[$.
+
+
+
+
 \section{Efficient prng based on chaotic iterations}
 
 On parle du séquentiel avec des nombres 64 bits\\
@@ -35,7 +220,8 @@ In  order to  implement efficiently  a PRNG  based on  chaotic iterations  it is
 possible to improve  previous works [ref]. One solution  consists in considering
 that the  strategy used $S^i$  contains all the  bits for which the  negation is
 achieved out. Then instead of applying  the negation on these bits we can simply
-apply the xor operator between the current number and the strategy $S^i$.
+apply the  xor operator between  the current number  and the strategy  $S^i$. In
+order to obtain the strategy we also use a classical PRNG.
 
 \begin{figure}[htbp]
 \begin{center}
@@ -46,12 +232,12 @@ unsigned int CIprng() \{\\
   unsigned long t1 = xorshift();\\
   unsigned long t2 = xor128();\\
   unsigned long t3 = xorwow();\\
-  x = x\^\ (unsigned int)t;\\
-  x = x\^\ (unsigned int)(t2$>>$32);\\
-  x = x\^\ (unsigned int)(t3$>>$32);\\
-  x = x\^\ (unsigned int)t2;\\
-  x = x\^\ (unsigned int)(t$>>$32);\\
-  x = x\^\ (unsigned int)t3;\\
+  x = x\textasciicircum (unsigned int)t1;\\
+  x = x\textasciicircum (unsigned int)(t2$>>$32);\\
+  x = x\textasciicircum (unsigned int)(t3$>>$32);\\
+  x = x\textasciicircum (unsigned int)t2;\\
+  x = x\textasciicircum (unsigned int)(t1$>>$32);\\
+  x = x\textasciicircum (unsigned int)t3;\\
   return x;\\
 \}
 \end{minipage}
@@ -61,9 +247,15 @@ unsigned int CIprng() \{\\
 \label{algo:seqCIprng}
 \end{figure}
 
-In Figure~\ref{algo:seqCIprng} a sequential version of our chaotic iterations based PRNG is
-presented. This  version uses  three classical 64-bits  PRNG: the  xorshift, the
-xor128 and the xorwow. These three PRNGs are presented in~\cite{Marsaglia2003}.
+In Figure~\ref{algo:seqCIprng}  a sequential  version of our  chaotic iterations
+based PRNG  is presented.  This version  uses three classical 64  bits PRNG: the
+\texttt{xorshift},  the \texttt{xor128}  and the  \texttt{xorwow}.   These three
+PRNGs  are presented  in~\cite{Marsaglia2003}.   As each  PRNG  used works  with
+64-bits and as  our PRNG works with 32 bits, the  use of \texttt{(unsigned int)}
+selects the 32 least  significant bits whereas \texttt{(unsigned int)(t3$>>$32)}
+selects the 32  most significants bits of the  variable \texttt{t}. This version
+sucesses   the   BigCrush   of    the   TestU01   battery   [P.   L’ecuyer   and
+  R. Simard. Testu01].
 
 \section{Efficient prng based on chaotic iterations on GPU}
 
@@ -75,7 +267,6 @@ On passe le BigCrush\\
 On donne des temps de générations sur GPU/CPU\\
 On donne des temps de générations de nombre sur GPU puis on rappatrie sur CPU / CPU ? bof bof, on verra
 
-\section{Lyapunov}
 
 \section{Conclusion}
 \bibliographystyle{plain}