From 5ac19ee235bd1e798057121a7142819923af901d Mon Sep 17 00:00:00 2001 From: Christophe Guyeux Date: Wed, 7 Sep 2011 14:30:36 +0200 Subject: [PATCH] pouet --- prng_gpu.tex | 186 ++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 185 insertions(+), 1 deletion(-) diff --git a/prng_gpu.tex b/prng_gpu.tex index f048253..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\\ @@ -82,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} -- 2.39.5