X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/12410996f49b94978103d0ba32d17f85c89fa51a..a97a587bc408ff330d3c6292bcf7d0c488ecae16:/prng_gpu.tex?ds=sidebyside diff --git a/prng_gpu.tex b/prng_gpu.tex index 082c379..d95e87f 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -7,6 +7,8 @@ \usepackage{amscd} \usepackage{moreverb} \usepackage{commath} +\usepackage{algorithm2e} +\usepackage{listings} \usepackage[standard]{ntheorem} % Pour mathds : les ensembles IR, IN, etc. @@ -32,23 +34,956 @@ \newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}} -\title{Efficient generation of pseudo random numbers based on chaotic iterations on GPU} +\title{Efficient Generation of Pseudo-Random Numbers based on Chaotic Iterations +on GPU} \begin{document} + +\author{Jacques M. Bahi, Rapha\"{e}l Couturier, and Christophe +Guyeux\thanks{Authors in alphabetic order}} + \maketitle \begin{abstract} -This is the abstract + \end{abstract} \section{Introduction} -Interet des itérations chaotiques pour générer des nombre alea\\ -Interet de générer des nombres alea sur GPU -... +Random numbers are used in many scientific applications and simulations. On +finite state machines, as computers, it is not possible to generate random +numbers but only pseudo-random numbers. In practice, a good pseudo-random number +generator (PRNG) needs to verify some features to be used by scientists. It is +important to be able to generate pseudo-random numbers efficiently, the +generation needs to be reproducible and a PRNG needs to satisfy many usual +statistical properties. Finally, from our point a view, it is essential to prove +that a PRNG is chaotic. Concerning the statistical tests, TestU01 is the +best-known public-domain statistical testing package. So we use it for all our +PRNGs, especially the {\it BigCrush} which provides the largest serie of tests. +Concerning the chaotic properties, Devaney~\cite{Devaney} proposed a common +mathematical formulation of chaotic dynamical systems. + +In a previous work~\cite{bgw09:ip} we have proposed a new familly of chaotic +PRNG based on chaotic iterations (IC). We have proven that these PRNGs are +chaotic in the Devaney's sense. In this paper we propose a faster version which +is also proven to be chaotic. + +Although graphics processing units (GPU) was initially designed to accelerate +the manipulation of images, they are nowadays commonly used in many scientific +applications. Therefore, it is important to be able to generate pseudo-random +numbers inside a GPU when a scientific application runs in a GPU. That is why we +also provide an efficient PRNG for GPU respecting based on IC. Such devices +allows us to generated almost 20 billions of random numbers per second. + +In order to establish that our PRNGs are chaotic according to the Devaney's +formulation, we extend what we have proposed in~\cite{guyeux10}. Moreover, we define a new distance to measure the disorder in the chaos and we prove some interesting properties with this distance. + +The rest of this paper is organised as follows. In Section~\ref{section:related + works} we review some GPU implementions of PRNG. Section~\ref{section:BASIC RECALLS} gives some basic recalls on Devanay's formation of chaos and +chaotic iterations. In Section~\ref{sec:pseudo-random} the proof of chaos of our +PRNGs is studied. Section~\ref{sec:efficient prng} presents an efficient +implementation of our chaotic PRNG on a CPU. Section~\ref{sec:efficient prng + gpu} describes the GPU implementation of our chaotic PRNG. In +Section~\ref{sec:experiments} some experimentations are presented. +Section~\ref{sec:de la relativité du désordre} describes the relativity of +disorder. In Section~\ref{sec: chaos order topology} the proof that chaotic +iterations can be described by iterations on a real interval is established. Finally, we give a conclusion and some perspectives. + + + + +\section{Related works on GPU based PRNGs} +\label{section:related works} +In the litterature many authors have work on defining GPU based PRNGs. We do not +want to be exhaustive and we just give the most significant works from our point +of view. When authors mention the number of random numbers generated per second +we mention it. We consider that a million numbers per second corresponds to +1MSample/s and than a billion numbers per second corresponds to 1GSample/s. + +In \cite{Pang:2008:cec}, the authors define a PRNG based on cellular automata +which does not require high precision integer arithmetics nor bitwise +operations. There is no mention of statistical tests nor proof that this PRNG is +chaotic. Concerning the speed of generation, they can generate about +3.2MSample/s on a GeForce 7800 GTX GPU (which is quite old now). + +In \cite{ZRKB10}, the authors propose different versions of efficient GPU PRNGs +based on Lagged Fibonacci, Hybrid Taus or Hybrid Taus. They have used these +PRNGs for Langevin simulations of biomolecules fully implemented on +GPU. Performance of the GPU versions are far better than those obtained with a +CPU and these PRNGs succeed to pass the {\it BigCrush} test of TestU01. There is +no mention that their PRNGs have chaos mathematical properties. + + +Authors of~\cite{conf/fpga/ThomasHL09} have studied the implementation of some +PRNGs on diferrent computing architectures: CPU, field-programmable gate array +(FPGA), GPU and massively parallel processor. This study is interesting because +it shows the performance of the same PRNGs on different architeture. For +example, the FPGA is globally the fastest architecture and it is also the +efficient one because it provides the fastest number of generated random numbers +per joule. Concerning the GPU, authors can generate betweend 11 and 16GSample/s +with a GTX 280 GPU. The drawback of this work is that those PRNGs only succeed +the {\it Crush} test which is easier than the {\it Big Crush} test. +\newline +\newline +To the best of our knowledge no GPU implementation have been proven to have chaotic properties. + +\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. +\subsection{Devaney's Chaotic Dynamical Systems} + +In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$ +denotes the $i^{th}$ component of a vector $V$. $f^{k}=f\circ ...\circ f$ +is for the $k^{th}$ composition of a function $f$. Finally, the following +notation is used: $\llbracket1;N\rrbracket=\{1,2,\hdots,N\}$. + + +Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f : +\mathcal{X} \rightarrow \mathcal{X}$. + +\begin{definition} +$f$ is said to be \emph{topologically transitive} if, for any pair of open sets +$U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq +\varnothing$. +\end{definition} + +\begin{definition} +An element $x$ is a \emph{periodic point} for $f$ of period $n\in \mathds{N}^*$ +if $f^{n}(x)=x$.% The set of periodic points of $f$ is denoted $Per(f).$ +\end{definition} + +\begin{definition} +$f$ is said to be \emph{regular} on $(\mathcal{X}, \tau)$ if the set of periodic +points for $f$ is dense in $\mathcal{X}$: for any point $x$ in $\mathcal{X}$, +any neighborhood of $x$ contains at least one periodic point (without +necessarily the same period). +\end{definition} + + +\begin{definition}[Devaney's formulation of chaos~\cite{Devaney}] +$f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and +topologically transitive. +\end{definition} + +The chaos property is strongly linked to the notion of ``sensitivity'', defined +on a metric space $(\mathcal{X},d)$ by: + +\begin{definition} +\label{sensitivity} $f$ has \emph{sensitive dependence on initial conditions} +if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any +neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that +$d\left(f^{n}(x), f^{n}(y)\right) >\delta $. + +$\delta$ is called the \emph{constant of sensitivity} of $f$. +\end{definition} + +Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is +chaotic and $(\mathcal{X}, d)$ is a metric space, then $f$ has the property of +sensitive dependence on initial conditions (this property was formerly an +element of the definition of chaos). To sum up, quoting Devaney +in~\cite{Devaney}, a chaotic dynamical system ``is unpredictable because of the +sensitive dependence on initial conditions. It cannot be broken down or +simplified into two subsystems which do not interact because of topological +transitivity. And in the midst of this random behavior, we nevertheless have an +element of regularity''. Fundamentally different behaviors are consequently +possible and occur in an unpredictable way. + + + +\subsection{Chaotic Iterations} +\label{sec:chaotic iterations} + + +Let us consider a \emph{system} with a finite number $\mathsf{N} \in +\mathds{N}^*$ of elements (or \emph{cells}), so that each cell has a +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 $\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 \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} +\forall n\in \mathds{N}^{\ast }, \forall i\in +\llbracket1;\mathsf{N}\rrbracket ,x_i^n=\left\{ +\begin{array}{ll} + x_i^{n-1} & \text{ if }S^n\neq i \\ + \left(f(x^{n-1})\right)_{S^n} & \text{ if }S^n=i. +\end{array}\right. +\end{equation} +\end{definition} + +In other words, at the $n^{th}$ iteration, only the $S^{n}-$th cell is +\textquotedblleft iterated\textquotedblright . Note that in a more +general formulation, $S^n$ can be a subset of components and +$\left(f(x^{n-1})\right)_{S^{n}}$ can be replaced by +$\left(f(x^{k})\right)_{S^{n}}$, where $k0$. \medskip +\begin{itemize} +\item If $\varepsilon \geqslant 1$, we see that distance +between $\left( G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is +strictly less than 1 after the $max(n_{0},n_{1})^{th}$ term (same state). +\medskip +\item If $\varepsilon <1$, then $\exists k\in \mathds{N},10^{-k}\geqslant +\varepsilon > 10^{-(k+1)}$. But $d_{s}(S^n,S)$ converges to 0, so +\begin{equation*} +\exists n_{2}\in \mathds{N},\forall n\geqslant +n_{2},d_{s}(S^n,S)<10^{-(k+2)}, +\end{equation*}% +thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal. +\end{itemize} +\noindent As a consequence, the $k+1$ first entries of the strategies of $% +G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of +the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $% +10^{-(k+1)}\leqslant \varepsilon $.\bigskip \newline +In conclusion, +$$ +\forall \varepsilon >0,\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}% +,\forall n\geqslant N_{0}, + d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right) +\leqslant \varepsilon . +$$ +$G_{f}$ is consequently continuous. +\end{proof} + + +It is now possible to study the topological behavior of the general chaotic +iterations. We will prove that, + +\begin{theorem} +\label{t:chaos des general} + The general chaotic iterations defined on Equation~\ref{general CIs} satisfy +the Devaney's property of chaos. +\end{theorem} + +Let us firstly prove the following lemma. + +\begin{lemma}[Strong transitivity] +\label{strongTrans} + For all couples $X,Y \in \mathcal{X}$ and any neighborhood $V$ of $X$, we can +find $n \in \mathds{N}^*$ and $X' \in V$ such that $G^n(X')=Y$. +\end{lemma} + +\begin{proof} + Let $X=(S,E)$, $\varepsilon>0$, and $k_0 = \lfloor log_{10}(\varepsilon)+1 \rfloor$. +Any point $X'=(S',E')$ such that $E'=E$ and $\forall k \leqslant k_0, S'^k=S^k$, +are in the open ball $\mathcal{B}\left(X,\varepsilon\right)$. Let us define +$\check{X} = \left(\check{S},\check{E}\right)$, where $\check{X}= G^{k_0}(X)$. +We denote by $s\subset \llbracket 1; \mathsf{N} \rrbracket$ the set of coordinates +that are different between $\check{E}$ and the state of $Y$. Thus each point $X'$ of +the form $(S',E')$ where $E'=E$ and $S'$ starts with +$(S^0, S^1, \hdots, S^{k_0},s,\hdots)$, verifies the following properties: +\begin{itemize} + \item $X'$ is in $\mathcal{B}\left(X,\varepsilon\right)$, + \item the state of $G_f^{k_0+1}(X')$ is the state of $Y$. +\end{itemize} +Finally the point $\left(\left(S^0, S^1, \hdots, S^{k_0},s,s^0, s^1, \hdots\right); E\right)$, +where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties +claimed in the lemma. +\end{proof} + +We can now prove the Theorem~\ref{t:chaos des general}... + +\begin{proof}[Theorem~\ref{t:chaos des general}] +Firstly, strong transitivity implies transitivity. + +Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To +prove that $G_f$ is regular, it is sufficient to prove that +there exists a strategy $\tilde S$ such that the distance between +$(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that +$(\tilde S,E)$ is a periodic point. + +Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the +configuration that we obtain from $(S,E)$ after $t_1$ iterations of +$G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$ +and $t_2\in\mathds{N}$ such +that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$. + +Consider the strategy $\tilde S$ that alternates the first $t_1$ terms +of $S$ and the first $t_2$ terms of $S'$: $$\tilde +S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It +is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after +$t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic +point. Since $\tilde S_t=S_t$ for $t>$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} +%% } +%% \end{center} +%% \caption{sequential Chaotic Iteration PRNG} +%% \label{algo:seqCIprng} +%% \end{figure} + + + +\lstset{language=C,caption={C code of the sequential chaotic iterations based +PRNG},label=algo:seqCIprng} +\begin{lstlisting} +unsigned int CIprng() { + static unsigned int x = 123123123; + unsigned long t1 = xorshift(); + unsigned long t2 = xor128(); + unsigned long t3 = xorwow(); + x = x^(unsigned int)t1; + x = x^(unsigned int)(t2>>32); + x = x^(unsigned int)(t3>>32); + x = x^(unsigned int)t2; + x = x^(unsigned int)(t1>>32); + x = x^(unsigned int)t3; + return x; +} +\end{lstlisting} + + + + + +In listing~\ref{algo:seqCIprng} a sequential version of our chaotic iterations +based PRNG is presented. The xor operator is represented by \textasciicircum. +This function uses three classical 64-bits PRNG: the \texttt{xorshift}, the +\texttt{xor128} and the \texttt{xorwow}. In the following, we call them +xor-like PRNGSs. These three PRNGs are presented in~\cite{Marsaglia2003}. As +each xor-like 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}. So to produce a random number realizes 6 xor operations +with 6 32-bits numbers produced by 3 64-bits PRNG. This version successes the +BigCrush of the TestU01 battery~\cite{LEcuyerS07}. + +\section{Efficient PRNGs based on chaotic iterations on GPU} +\label{sec:efficient prng gpu} + +In order to benefit from computing power of GPU, a program needs to define +independent blocks of threads which can be computed simultaneously. In general, +the larger the number of threads is, the more local memory is used and the less +branching instructions are used (if, while, ...), the better performance is +obtained on GPU. So with algorithm \ref{algo:seqCIprng} presented in the +previous section, it is possible to build a similar program which computes PRNG +on GPU. In the CUDA~\cite{Nvid10} environment, threads have a local +identificator, called \texttt{ThreadIdx} relative to the block containing them. + + +\subsection{Naive version for GPU} + +From the CPU version, it is possible to obtain a quite similar version for GPU. +The principe consists in assigning the computation of a PRNG as in sequential to +each thread of the GPU. Of course, it is essential that the three xor-like +PRNGs used for our computation have different parameters. So we chose them +randomly with another PRNG. As the initialisation is performed by the CPU, we +have chosen to use the ISAAC PRNG~\ref{Jenkins96} to initalize all the +parameters for the GPU version of our PRNG. The implementation of the three +xor-like PRNGs is straightforward as soon as their parameters have been +allocated in the GPU memory. Each xor-like PRNGs used works with an internal +number $x$ which keeps the last generated random numbers. Other internal +variables are also used by the xor-like PRNGs. More precisely, the +implementation of the xor128, the xorshift and the xorwow respectively require +4, 5 and 6 unsigned long as internal variables. + +\begin{algorithm} + +\KwIn{InternalVarXorLikeArray: array with internal variables of the 3 xor-like +PRNGs in global memory\; +NumThreads: Number of threads\;} +\KwOut{NewNb: array containing random numbers in global memory} +\If{threadIdx is concerned by the computation} { + retrieve data from InternalVarXorLikeArray[threadIdx] in local variables\; + \For{i=1 to n} { + compute a new PRNG as in Listing\ref{algo:seqCIprng}\; + store the new PRNG in NewNb[NumThreads*threadIdx+i]\; + } + store internal variables in InternalVarXorLikeArray[threadIdx]\; +} + +\caption{main kernel for the chaotic iterations based PRNG GPU naive version} +\label{algo:gpu_kernel} +\end{algorithm} + +Algorithm~\ref{algo:gpu_kernel} presents a naive implementation of PRNG using +GPU. According to the available memory in the GPU and the number of threads +used simultenaously, the number of random numbers that a thread can generate +inside a kernel is limited, i.e. the variable \texttt{n} in +algorithm~\ref{algo:gpu_kernel}. For example, if $100,000$ threads are used and +if $n=100$\footnote{in fact, we need to add the initial seed (a 32-bits number)} +then the memory required to store internals variables of xor-like +PRNGs\footnote{we multiply this number by $2$ in order to count 32-bits numbers} +and random number of our PRNG is equals to $100,000\times ((4+5+6)\times +2+(1+100))=1,310,000$ 32-bits numbers, i.e. about $52$Mb. + +All the tests performed to pass the BigCrush of TestU01 succeeded. Different +number of threads, called \texttt{NumThreads} in our algorithm, have been tested +upto $10$ millions. + +\begin{remark} +Algorithm~\ref{algo:gpu_kernel} has the advantage to manipulate independent +PRNGs, so this version is easily usable on a cluster of computer. The only thing +to ensure is to use a single ISAAC PRNG. For this, a simple solution consists in +using a master node for the initialization which computes the initial parameters +for all the differents nodes involves in the computation. +\end{remark} + +\subsection{Improved version for GPU} + +As GPU cards using CUDA have shared memory between threads of the same block, it +is possible to use this feature in order to simplify the previous algorithm, +i.e., using less than 3 xor-like PRNGs. The solution consists in computing only +one xor-like PRNG by thread, saving it into shared memory and using the results +of some other threads in the same block of threads. In order to define which +thread uses the result of which other one, we can use a permutation array which +contains the indexes of all threads and for which a permutation has been +performed. In Algorithm~\ref{algo:gpu_kernel2}, 2 permutations arrays are used. +The variable \texttt{offset} is computed using the value of +\texttt{permutation\_size}. Then we can compute \texttt{o1} and \texttt{o2} +which represent the indexes of the other threads for which the results are used +by the current thread. In the algorithm, we consider that a 64-bits xor-like +PRNG is used, that is why both 32-bits parts are used. + +This version also succeeds to the {\it BigCrush} batteries of tests. + +\begin{algorithm} + +\KwIn{InternalVarXorLikeArray: array with internal variables of 1 xor-like PRNGs +in global memory\; +NumThreads: Number of threads\; +tab1, tab2: Arrays containing permutations of size permutation\_size\;} + +\KwOut{NewNb: array containing random numbers in global memory} +\If{threadId is concerned} { + retrieve data from InternalVarXorLikeArray[threadId] in local variables including shared memory\; + offset = threadIdx\%permutation\_size\; + o1 = threadIdx-offset+tab1[offset]\; + o2 = threadIdx-offset+tab2[offset]\; + \For{i=1 to n} { + t=xor-like()\; + t=t$\oplus$shmem[o1]$\oplus$shmem[o2]\; + shared\_mem[threadId]=t\; + x = x $\oplus$ t\; + + store the new PRNG in NewNb[NumThreads*threadId+i]\; + } + store internal variables in InternalVarXorLikeArray[threadId]\; +} + +\caption{main kernel for the chaotic iterations based PRNG GPU efficient +version} +\label{algo:gpu_kernel2} +\end{algorithm} + +\subsection{Theoretical Evaluation of the Improved Version} + +A run of Algorithm~\ref{algo:gpu_kernel2} consists in three operations having +the form of Equation~\ref{equation Oplus}, which is equivalent to the iterative +system of Eq.~\ref{eq:generalIC}. That is, three iterations of the general chaotic +iterations are realized between two stored values of the PRNG. +To be certain that we are in the framework of Theorem~\ref{t:chaos des general}, +we must guarantee that this dynamical system iterates on the space +$\mathcal{X} = \mathcal{P}\left(\llbracket 1, \mathsf{N} \rrbracket\right)^\mathds{N}\times\mathds{B}^\mathsf{N}$. +The left term $x$ obviously belongs into $\mathds{B}^ \mathsf{N}$. +To prevent from any flaws of chaotic properties, we must check that each right +term, corresponding to terms of the strategies, can possibly be equal to any +integer of $\llbracket 1, \mathsf{N} \rrbracket$. + +Such a result is obvious for the two first lines, as for the xor-like(), all the +integers belonging into its interval of definition can occur at each iteration. +It can be easily stated for the two last lines by an immediate mathematical +induction. + +Thus Algorithm~\ref{algo:gpu_kernel2} is a concrete realization of the general +chaotic iterations presented previously, and for this reason, it satisfies the +Devaney's formulation of a chaotic behavior. + +\section{Experiments} +\label{sec:experiments} + +Different experiments have been performed in order to measure the generation +speed. We have used a computer equiped with Tesla C1060 NVidia GPU card and an +Intel Xeon E5530 cadenced at 2.40 GHz for our experiments and we have used +another one equipped with a less performant CPU and a GeForce GTX 280. Both +cards have 240 cores. + +In Figure~\ref{fig:time_gpu} we compare the number of random numbers generated +per second. The xor-like prng is a xor64 described in~\cite{Marsaglia2003}. In +order to obtain the optimal performance we remove the storage of random numbers +in the GPU memory. This step is time consumming and slows down the random number +generation. Moreover, if you are interested by applications that consome random +numbers directly when they are generated, their storage is completely +useless. In this figure we can see that when the number of threads is greater +than approximately 30,000 upto 5 millions the number of random numbers generated +per second is almost constant. With the naive version, it is between 2.5 and +3GSample/s. With the optimized version, it is approximately equals to +20GSample/s. Finally we can remark that both GPU cards are quite similar. In +practice, the Tesla C1060 has more memory than the GTX 280 and this memory +should be of better quality. + +\begin{figure}[htbp] +\begin{center} + \includegraphics[scale=.7]{curve_time_gpu.pdf} +\end{center} +\caption{Number of random numbers generated per second} +\label{fig:time_gpu} +\end{figure} + -\section{Chaotic iterations} +In comparison, Listing~\ref{algo:seqCIprng} allows us to generate about +138MSample/s with only one core of the Xeon E5530. -Présentation des itérations chaotiques @@ -56,50 +991,77 @@ Présentation des itérations chaotiques \section{The relativity of disorder} \label{sec:de la relativité du désordre} +In the next two sections, we investigate the impact of the choices that have +lead to the definitions of measures in Sections \ref{sec:chaotic iterations} and \ref{deuxième def}. + \subsection{Impact of the topology's finenesse} Let us firstly introduce the following notations. \begin{notation} -$\mathcal{X}_\tau$ will denote the topological space $\left(\mathcal{X},\tau\right)$, whereas $\mathcal{V}_\tau (x)$ will be the set of all the neighborhoods of $x$ when considering the topology $\tau$ (or simply $\mathcal{V} (x)$, if there is no ambiguity). +$\mathcal{X}_\tau$ will denote the topological space +$\left(\mathcal{X},\tau\right)$, whereas $\mathcal{V}_\tau (x)$ will be the set +of all the neighborhoods of $x$ when considering the topology $\tau$ (or simply +$\mathcal{V} (x)$, if there is no ambiguity). \end{notation} \begin{theorem} \label{Th:chaos et finesse} -Let $\mathcal{X}$ a set and $\tau, \tau'$ two topologies on $\mathcal{X}$ s.t. $\tau'$ is finer than $\tau$. Let $f:\mathcal{X} \to \mathcal{X}$, continuous both for $\tau$ and $\tau'$. +Let $\mathcal{X}$ a set and $\tau, \tau'$ two topologies on $\mathcal{X}$ s.t. +$\tau'$ is finer than $\tau$. Let $f:\mathcal{X} \to \mathcal{X}$, continuous +both for $\tau$ and $\tau'$. -If $(\mathcal{X}_{\tau'},f)$ is chaotic according to Devaney, then $(\mathcal{X}_\tau,f)$ is chaotic too. +If $(\mathcal{X}_{\tau'},f)$ is chaotic according to Devaney, then +$(\mathcal{X}_\tau,f)$ is chaotic too. \end{theorem} \begin{proof} Let us firstly establish the transitivity of $(\mathcal{X}_\tau,f)$. -Let $\omega_1, \omega_2$ two open sets of $\tau$. Then $\omega_1, \omega_2 \in \tau'$, becaus $\tau'$ is finer than $\tau$. As $f$ is $\tau'-$transitive, we can deduce that $\exists n \in \mathds{N}, \omega_1 \cap f^{(n)}(\omega_2) = \varnothing$. Consequently, $f$ is $\tau-$transitive. +Let $\omega_1, \omega_2$ two open sets of $\tau$. Then $\omega_1, \omega_2 \in +\tau'$, becaus $\tau'$ is finer than $\tau$. As $f$ is $\tau'-$transitive, we +can deduce that $\exists n \in \mathds{N}, \omega_1 \cap f^{(n)}(\omega_2) = +\varnothing$. Consequently, $f$ is $\tau-$transitive. -Let us now consider the regularity of $(\mathcal{X}_\tau,f)$, \emph{i.e.}, for all $x \in \mathcal{X}$, and for all $\tau-$neighborhood $V$ of $x$, there is a periodic point for $f$ into $V$. +Let us now consider the regularity of $(\mathcal{X}_\tau,f)$, \emph{i.e.}, for +all $x \in \mathcal{X}$, and for all $\tau-$neighborhood $V$ of $x$, there is a +periodic point for $f$ into $V$. -Let $x \in \mathcal{X}$ and $V \in \mathcal{V}_\tau (x)$ a $\tau-$neighborhood of $x$. By definition, $\exists \omega \in \tau, x \in \omega \subset V$. +Let $x \in \mathcal{X}$ and $V \in \mathcal{V}_\tau (x)$ a $\tau-$neighborhood +of $x$. By definition, $\exists \omega \in \tau, x \in \omega \subset V$. -But $\tau \subset \tau'$, so $\omega \in \tau'$, and then $V \in \mathcal{V}_{\tau'} (x)$. As $(\mathcal{X}_{\tau'},f)$ is regular, there is a periodic point for $f$ into $V$, and the regularity of $(\mathcal{X}_\tau,f)$ is proven. +But $\tau \subset \tau'$, so $\omega \in \tau'$, and then $V \in +\mathcal{V}_{\tau'} (x)$. As $(\mathcal{X}_{\tau'},f)$ is regular, there is a +periodic point for $f$ into $V$, and the regularity of $(\mathcal{X}_\tau,f)$ is +proven. \end{proof} \subsection{A given system can always be claimed as chaotic} -Let $f$ an iteration function on $\mathcal{X}$ having at least a fixed point. Then this function is chaotic (in a certain way): +Let $f$ an iteration function on $\mathcal{X}$ having at least a fixed point. +Then this function is chaotic (in a certain way): \begin{theorem} -Let $\mathcal{X}$ a nonempty set and $f: \mathcal{X} \to \X$ a function having at least a fixed point. -Then $f$ is $\tau_0-$chaotic, where $\tau_0$ is the trivial (indiscrete) topology on $\X$. +Let $\mathcal{X}$ a nonempty set and $f: \mathcal{X} \to \X$ a function having +at least a fixed point. +Then $f$ is $\tau_0-$chaotic, where $\tau_0$ is the trivial (indiscrete) +topology on $\X$. \end{theorem} \begin{proof} -$f$ is transitive when $\forall \omega, \omega' \in \tau_0 \setminus \{\varnothing\}, \exists n \in \mathds{N}, f^{(n)}(\omega) \cap \omega' \neq \varnothing$. -As $\tau_0 = \left\{ \varnothing, \X \right\}$, this is equivalent to look for an integer $n$ s.t. $f^{(n)}\left( \X \right) \cap \X \neq \varnothing$. For instance, $n=0$ is appropriate. - -Let us now consider $x \in \X$ and $V \in \mathcal{V}_{\tau_0} (x)$. Then $V = \mathcal{X}$, so $V$ has at least a fixed point for $f$. Consequently $f$ is regular, and the result is established. +$f$ is transitive when $\forall \omega, \omega' \in \tau_0 \setminus +\{\varnothing\}, \exists n \in \mathds{N}, f^{(n)}(\omega) \cap \omega' \neq +\varnothing$. +As $\tau_0 = \left\{ \varnothing, \X \right\}$, this is equivalent to look for +an integer $n$ s.t. $f^{(n)}\left( \X \right) \cap \X \neq \varnothing$. For +instance, $n=0$ is appropriate. + +Let us now consider $x \in \X$ and $V \in \mathcal{V}_{\tau_0} (x)$. Then $V = +\mathcal{X}$, so $V$ has at least a fixed point for $f$. Consequently $f$ is +regular, and the result is established. \end{proof} @@ -109,17 +1071,26 @@ Let us now consider $x \in \X$ and $V \in \mathcal{V}_{\tau_0} (x)$. Then $V = \ \begin{theorem} Let $\mathcal{X}$ be a set and $f: \mathcal{X} \to \X$. -If $\X$ is infinite, then $\left( \X_{\tau_\infty}, f\right)$ is not chaotic (for the Devaney's formulation), where $\tau_\infty$ is the discrete topology. +If $\X$ is infinite, then $\left( \X_{\tau_\infty}, f\right)$ is not chaotic +(for the Devaney's formulation), where $\tau_\infty$ is the discrete topology. \end{theorem} \begin{proof} -Let us prove it by contradiction, assuming that $\left(\X_{\tau_\infty}, f\right)$ is both transitive and regular. +Let us prove it by contradiction, assuming that $\left(\X_{\tau_\infty}, +f\right)$ is both transitive and regular. -Let $x \in \X$ and $\{x\}$ one of its neighborhood. This neighborhood must contain a periodic point for $f$, if we want that $\left(\X_{\tau_\infty}, f\right)$ is regular. Then $x$ must be a periodic point of $f$. +Let $x \in \X$ and $\{x\}$ one of its neighborhood. This neighborhood must +contain a periodic point for $f$, if we want that $\left(\X_{\tau_\infty}, +f\right)$ is regular. Then $x$ must be a periodic point of $f$. -Let $I_x = \left\{ f^{(n)}(x), n \in \mathds{N}\right\}$. This set is finite because $x$ is periodic, and $\mathcal{X}$ is infinite, then $\exists y \in \mathcal{X}, y \notin I_x$. +Let $I_x = \left\{ f^{(n)}(x), n \in \mathds{N}\right\}$. This set is finite +because $x$ is periodic, and $\mathcal{X}$ is infinite, then $\exists y \in +\mathcal{X}, y \notin I_x$. -As $\left(\X_{\tau_\infty}, f\right)$ must be transitive, for all open nonempty sets $A$ and $B$, an integer $n$ must satisfy $f^{(n)}(A) \cap B \neq \varnothing$. However $\{x\}$ and $\{y\}$ are open sets and $y \notin I_x \Rightarrow \forall n, f^{(n)}\left( \{x\} \right) \cap \{y\} = \varnothing$. +As $\left(\X_{\tau_\infty}, f\right)$ must be transitive, for all open nonempty +sets $A$ and $B$, an integer $n$ must satisfy $f^{(n)}(A) \cap B \neq +\varnothing$. However $\{x\}$ and $\{y\}$ are open sets and $y \notin I_x +\Rightarrow \forall n, f^{(n)}\left( \{x\} \right) \cap \{y\} = \varnothing$. \end{proof} @@ -128,82 +1099,99 @@ As $\left(\X_{\tau_\infty}, f\right)$ must be transitive, for all open nonempty \section{Chaos on the order topology} - +\label{sec: chaos order topology} \subsection{The phase space is an interval of the real line} \subsubsection{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. +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}$. +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) +The function $\varphi: \mathcal{S}_{10} \times\mathds{B}^{10} \rightarrow \big[ +0, 2^{10} \big[$ is defined by: +\begin{equation} + \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: +\end{equation} +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}.$ +\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: +$\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: +\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{equation} \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}} \\ +\end{equation} +and +\begin{equation} + \begin{array}{cccc} +s: & \big[ 0, 2^{10} \big[ & \longrightarrow & \llbracket 0, 9 +\rrbracket^{\mathds{N}} \\ & x & \longmapsto & (s^k)_{k \in \mathds{N}} \end{array} -$$ +\end{equation} \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}$. +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} +\begin{equation} +\begin{array}{cccc} 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: +\end{equation} +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: -$$ +\item its integral part has a binary decomposition equal to $e_0', \hdots, +e_9'$, with: + \begin{equation} 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. -$$ +\end{equation} \item whose decimal part is $s(x)^1, s(x)^2, \hdots$ \end{itemize} \end{definition} @@ -211,28 +1199,43 @@ $$ \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}}.$$ +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: +\begin{equation} +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}}. +\end{equation} + \subsubsection{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: +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$. +$\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: +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: +$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}}$. +$\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} @@ -243,21 +1246,35 @@ $D$ is a distance on $\big[ 0, 2^{10} \big[$. \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 \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. +\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. +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}} + \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} @@ -268,15 +1285,19 @@ To illustrate this fact, a comparison between $D$ and the Euclidian distance is \subsubsection{The semiconjugacy} -It is now possible to define a topological semiconjugacy between $\mathcal{X}$ and an interval of $\mathds{R}$: +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: +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)\\ +\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) +\left( ~\big[ 0, 2^{10} \big[, D~\right) @>>g> \left(~\big[ 0, 2^{10} \big[, +D~\right) \end{CD} \end{equation*} \end{theorem} @@ -285,7 +1306,8 @@ Chaotic iterations on the phase space $\mathcal{X}$ are simple iterations on $\m $\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[$. +In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N} +\big[$. @@ -297,10 +1319,14 @@ In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N} \ \begin{figure}[t] \begin{center} - \subfigure[ICs on the interval $(0,9;1)$.]{\includegraphics[scale=.35]{ICs09a1.pdf}}\quad - \subfigure[ICs on the interval $(0,7;1)$.]{\includegraphics[scale=.35]{ICs07a95.pdf}}\\ - \subfigure[ICs on the interval $(0,5;1)$.]{\includegraphics[scale=.35]{ICs05a1.pdf}}\quad - \subfigure[ICs on the interval $(0;1)$]{\includegraphics[scale=.35]{ICs0a1.pdf}} + \subfigure[ICs on the interval +$(0,9;1)$.]{\includegraphics[scale=.35]{ICs09a1.pdf}}\quad + \subfigure[ICs on the interval +$(0,7;1)$.]{\includegraphics[scale=.35]{ICs07a95.pdf}}\\ + \subfigure[ICs on the interval +$(0,5;1)$.]{\includegraphics[scale=.35]{ICs05a1.pdf}}\quad + \subfigure[ICs on the interval +$(0;1)$]{\includegraphics[scale=.35]{ICs0a1.pdf}} \end{center} \caption{Representation of the chaotic iterations.} \label{fig:ICs} @@ -311,8 +1337,10 @@ In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N} \ \begin{figure}[t] \begin{center} - \subfigure[ICs on the interval $(510;514)$.]{\includegraphics[scale=.35]{ICs510a514.pdf}}\quad - \subfigure[ICs on the interval $(1000;1008)$]{\includegraphics[scale=.35]{ICs1000a1008.pdf}} + \subfigure[ICs on the interval +$(510;514)$.]{\includegraphics[scale=.35]{ICs510a514.pdf}}\quad + \subfigure[ICs on the interval +$(1000;1008)$]{\includegraphics[scale=.35]{ICs1000a1008.pdf}} \end{center} \caption{ICs on small intervals.} \label{fig:ICs2} @@ -320,49 +1348,78 @@ In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N} \ \begin{figure}[t] \begin{center} - \subfigure[ICs on the interval $(0;16)$.]{\includegraphics[scale=.3]{ICs0a16.pdf}}\quad - \subfigure[ICs on the interval $(40;70)$.]{\includegraphics[scale=.45]{ICs40a70.pdf}}\quad + \subfigure[ICs on the interval +$(0;16)$.]{\includegraphics[scale=.3]{ICs0a16.pdf}}\quad + \subfigure[ICs on the interval +$(40;70)$.]{\includegraphics[scale=.45]{ICs40a70.pdf}}\quad \end{center} \caption{General aspect of the chaotic iterations.} \label{fig:ICs3} \end{figure} -We have written a Python program to represent the chaotic iterations with the vectorial negation on the real line $\mathds{R}$. Various representations of these CIs are given in Figures \ref{fig:ICs}, \ref{fig:ICs2} and \ref{fig:ICs3}. It can be remarked that the function $g$ is a piecewise linear function: it is linear on each interval having the form $\left[ \dfrac{n}{10}, \dfrac{n+1}{10}\right[$, $n \in \llbracket 0;2^{10}\times 10 \rrbracket$ and its slope is equal to 10. Let us justify these claims: +We have written a Python program to represent the chaotic iterations with the +vectorial negation on the real line $\mathds{R}$. Various representations of +these CIs are given in Figures \ref{fig:ICs}, \ref{fig:ICs2} and \ref{fig:ICs3}. +It can be remarked that the function $g$ is a piecewise linear function: it is +linear on each interval having the form $\left[ \dfrac{n}{10}, +\dfrac{n+1}{10}\right[$, $n \in \llbracket 0;2^{10}\times 10 \rrbracket$ and its +slope is equal to 10. Let us justify these claims: \begin{proposition} \label{Prop:derivabilite des ICs} -Chaotic iterations $g$ defined on $\mathds{R}$ have derivatives of all orders on $\big[ 0, 2^{10} \big[$, except on the 10241 points in $I$ defined by $\left\{ \dfrac{n}{10} ~\big/~ n \in \llbracket 0;2^{10}\times 10\rrbracket \right\}$. - -Furthermore, on each interval of the form $\left[ \dfrac{n}{10}, \dfrac{n+1}{10}\right[$, with $n \in \llbracket 0;2^{10}\times 10 \rrbracket$, $g$ is a linear function, having a slope equal to 10: $\forall x \notin I, g'(x)=10$. +Chaotic iterations $g$ defined on $\mathds{R}$ have derivatives of all orders on +$\big[ 0, 2^{10} \big[$, except on the 10241 points in $I$ defined by $\left\{ +\dfrac{n}{10} ~\big/~ n \in \llbracket 0;2^{10}\times 10\rrbracket \right\}$. + +Furthermore, on each interval of the form $\left[ \dfrac{n}{10}, +\dfrac{n+1}{10}\right[$, with $n \in \llbracket 0;2^{10}\times 10 \rrbracket$, +$g$ is a linear function, having a slope equal to 10: $\forall x \notin I, +g'(x)=10$. \end{proposition} \begin{proof} -Let $I_n = \left[ \dfrac{n}{10}, \dfrac{n+1}{10}\right[$, with $n \in \llbracket 0;2^{10}\times 10 \rrbracket$. All the points of $I_n$ have the same integral prat $e$ and the same decimal part $s^0$: on the set $I_n$, functions $e(x)$ and $x \mapsto s(x)^0$ of Definition \ref{def:e et s} only depend on $n$. So all the images $g(x)$ of these points $x$: +Let $I_n = \left[ \dfrac{n}{10}, \dfrac{n+1}{10}\right[$, with $n \in \llbracket +0;2^{10}\times 10 \rrbracket$. All the points of $I_n$ have the same integral +prat $e$ and the same decimal part $s^0$: on the set $I_n$, functions $e(x)$ +and $x \mapsto s(x)^0$ of Definition \ref{def:e et s} only depend on $n$. So all +the images $g(x)$ of these points $x$: \begin{itemize} -\item Have the same integral part, which is $e$, except probably the bit number $s^0$. In other words, this integer has approximately the same binary decomposition than $e$, the sole exception being the digit $s^0$ (this number is then either $e+2^{10-s^0}$ or $e-2^{10-s^0}$, depending on the parity of $s^0$, \emph{i.e.}, it is equal to $e+(-1)^{s^0}\times 2^{10-s^0}$). -\item A shift to the left has been applied to the decimal part $y$, losing by doing so the common first digit $s^0$. In other words, $y$ has been mapped into $10\times y - s^0$. +\item Have the same integral part, which is $e$, except probably the bit number +$s^0$. In other words, this integer has approximately the same binary +decomposition than $e$, the sole exception being the digit $s^0$ (this number is +then either $e+2^{10-s^0}$ or $e-2^{10-s^0}$, depending on the parity of $s^0$, +\emph{i.e.}, it is equal to $e+(-1)^{s^0}\times 2^{10-s^0}$). +\item A shift to the left has been applied to the decimal part $y$, losing by +doing so the common first digit $s^0$. In other words, $y$ has been mapped into +$10\times y - s^0$. \end{itemize} -To sum up, the action of $g$ on the points of $I$ is as follows: first, make a multiplication by 10, and second, add the same constant to each term, which is $\dfrac{1}{10}\left(e+(-1)^{s^0}\times 2^{10-s^0}\right)-s^0$. +To sum up, the action of $g$ on the points of $I$ is as follows: first, make a +multiplication by 10, and second, add the same constant to each term, which is +$\dfrac{1}{10}\left(e+(-1)^{s^0}\times 2^{10-s^0}\right)-s^0$. \end{proof} \begin{remark} -Finally, chaotic iterations are elements of the large family of functions that are both chaotic and piecewise linear (like the tent map). +Finally, chaotic iterations are elements of the large family of functions that +are both chaotic and piecewise linear (like the tent map). \end{remark} \subsection{Comparison of the two metrics on $\big[ 0, 2^\mathsf{N} \big[$} -The two propositions bellow allow to compare our two distances on $\big[ 0, 2^\mathsf{N} \big[$: +The two propositions bellow allow to compare our two distances on $\big[ 0, +2^\mathsf{N} \big[$: \begin{proposition} -Id: $\left(~\big[ 0, 2^\mathsf{N} \big[,\Delta~\right) \to \left(~\big[ 0, 2^\mathsf{N} \big[, D~\right)$ is not continuous. +Id: $\left(~\big[ 0, 2^\mathsf{N} \big[,\Delta~\right) \to \left(~\big[ 0, +2^\mathsf{N} \big[, D~\right)$ is not continuous. \end{proposition} \begin{proof} -The sequence $x^n = 1,999\hdots 999$ constituted by $n$ 9 as decimal part, is such that: +The sequence $x^n = 1,999\hdots 999$ constituted by $n$ 9 as decimal part, is +such that: \begin{itemize} \item $\Delta (x^n,2) \to 0.$ \item But $D(x^n,2) \geqslant 1$, then $D(x^n,2)$ does not converge to 0. @@ -376,16 +1433,25 @@ The sequential characterization of the continuity concludes the demonstration. A contrario: \begin{proposition} -Id: $\left(~\big[ 0, 2^\mathsf{N} \big[,D~\right) \to \left(~\big[ 0, 2^\mathsf{N} \big[, \Delta ~\right)$ is a continuous fonction. +Id: $\left(~\big[ 0, 2^\mathsf{N} \big[,D~\right) \to \left(~\big[ 0, +2^\mathsf{N} \big[, \Delta ~\right)$ is a continuous fonction. \end{proposition} \begin{proof} -If $D(x^n,x) \to 0$, then $D_e(x^n,x) = 0$ at least for $n$ larger than a given threshold, because $D_e$ only returns integers. So, after this threshold, the integral parts of all the $x^n$ are equal to the integral part of $x$. - -Additionally, $D_s(x^n, x) \to 0$, then $\forall k \in \mathds{N}^*, \exists N_k \in \mathds{N}, n \geqslant N_k \Rightarrow D_s(x^n,x) \leqslant 10^{-k}$. This means that for all $k$, an index $N_k$ can be found such that, $\forall n \geqslant N_k$, all the $x^n$ have the same $k$ firsts digits, which are the digits of $x$. We can deduce the convergence $\Delta(x^n,x) \to 0$, and thus the result. +If $D(x^n,x) \to 0$, then $D_e(x^n,x) = 0$ at least for $n$ larger than a given +threshold, because $D_e$ only returns integers. So, after this threshold, the +integral parts of all the $x^n$ are equal to the integral part of $x$. + +Additionally, $D_s(x^n, x) \to 0$, then $\forall k \in \mathds{N}^*, \exists N_k +\in \mathds{N}, n \geqslant N_k \Rightarrow D_s(x^n,x) \leqslant 10^{-k}$. This +means that for all $k$, an index $N_k$ can be found such that, $\forall n +\geqslant N_k$, all the $x^n$ have the same $k$ firsts digits, which are the +digits of $x$. We can deduce the convergence $\Delta(x^n,x) \to 0$, and thus the +result. \end{proof} -The conclusion of these propositions is that the proposed metric is more precise than the Euclidian distance, that is: +The conclusion of these propositions is that the proposed metric is more precise +than the Euclidian distance, that is: \begin{corollary} $D$ is finer than the Euclidian distance $\Delta$. @@ -394,9 +1460,12 @@ $D$ is finer than the Euclidian distance $\Delta$. This corollary can be reformulated as follows: \begin{itemize} -\item The topology produced by $\Delta$ is a subset of the topology produced by $D$. +\item The topology produced by $\Delta$ is a subset of the topology produced by +$D$. \item $D$ has more open sets than $\Delta$. -\item It is harder to converge for the topology $\tau_D$ inherited by $D$, than to converge with the one inherited by $\Delta$, which is denoted here by $\tau_\Delta$. +\item It is harder to converge for the topology $\tau_D$ inherited by $D$, than +to converge with the one inherited by $\Delta$, which is denoted here by +$\tau_\Delta$. \end{itemize} @@ -407,82 +1476,47 @@ This corollary can be reformulated as follows: \subsubsection{Chaos according to Devaney} -We have recalled previously that the chaotic iterations $\left(\Go, \mathcal{X}_d\right)$ are chaotic according to the formulation of Devaney. We can deduce that they are chaotic on $\mathds{R}$ too, when considering the order topology, because: +We have recalled previously that the chaotic iterations $\left(\Go, +\mathcal{X}_d\right)$ are chaotic according to the formulation of Devaney. We +can deduce that they are chaotic on $\mathds{R}$ too, when considering the order +topology, because: \begin{itemize} -\item $\left(\Go, \mathcal{X}_d\right)$ and $\left(g, \big[ 0, 2^{10} \big[_D\right)$ are semiconjugate by $\varphi$, -\item Then $\left(g, \big[ 0, 2^{10} \big[_D\right)$ is a system chaotic according to Devaney, because the semiconjugacy preserve this character. -\item But the topology generated by $D$ is finer than the topology generated by the Euclidian distance $\Delta$ -- which is the order topology. -\item According to Theorem \ref{Th:chaos et finesse}, we can deduce that the chaotic iterations $g$ are indeed chaotic, as defined by Devaney, for the order topology on $\mathds{R}$. +\item $\left(\Go, \mathcal{X}_d\right)$ and $\left(g, \big[ 0, 2^{10} +\big[_D\right)$ are semiconjugate by $\varphi$, +\item Then $\left(g, \big[ 0, 2^{10} \big[_D\right)$ is a system chaotic +according to Devaney, because the semiconjugacy preserve this character. +\item But the topology generated by $D$ is finer than the topology generated by +the Euclidian distance $\Delta$ -- which is the order topology. +\item According to Theorem \ref{Th:chaos et finesse}, we can deduce that the +chaotic iterations $g$ are indeed chaotic, as defined by Devaney, for the order +topology on $\mathds{R}$. \end{itemize} This result can be formulated as follows. \begin{theorem} \label{th:IC et topologie de l'ordre} -The chaotic iterations $g$ on $\mathds{R}$ are chaotic according to the Devaney's formulation, when $\mathds{R}$ has his usual topology, which is the order topology. +The chaotic iterations $g$ on $\mathds{R}$ are chaotic according to the +Devaney's formulation, when $\mathds{R}$ has his usual topology, which is the +order topology. \end{theorem} -Indeed this result is weaker than the theorem establishing the chaos for the finer topology $d$. However the Theorem \ref{th:IC et topologie de l'ordre} still remains important. Indeed, we have studied in our previous works a set different from the usual set of study ($\mathcal{X}$ instead of $\mathds{R}$), in order to be as close as possible from the computer: the properties of disorder proved theoretically will then be preserved when computing. However, we could wonder whether this change does not lead to a disorder of a lower quality. In other words, have we replaced a situation of a good disorder lost when computing, to another situation of a disorder preserved but of bad quality. Theorem \ref{th:IC et topologie de l'ordre} prove exactly the contrary. +Indeed this result is weaker than the theorem establishing the chaos for the +finer topology $d$. However the Theorem \ref{th:IC et topologie de l'ordre} +still remains important. Indeed, we have studied in our previous works a set +different from the usual set of study ($\mathcal{X}$ instead of $\mathds{R}$), +in order to be as close as possible from the computer: the properties of +disorder proved theoretically will then be preserved when computing. However, we +could wonder whether this change does not lead to a disorder of a lower quality. +In other words, have we replaced a situation of a good disorder lost when +computing, to another situation of a disorder preserved but of bad quality. +Theorem \ref{th:IC et topologie de l'ordre} prove exactly the contrary. -\section{Efficient prng based on chaotic iterations} - -On parle du séquentiel avec des nombres 64 bits\\ - -Faire le lien avec le paragraphe précédent (je considère que la stratégie s'appelle $S^i$\\ - -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$. In -order to obtain the strategy we also use a classical PRNG. - -\begin{figure}[htbp] -\begin{center} -\fbox{ -\begin{minipage}{14cm} -unsigned int CIprng() \{\\ - static unsigned int x = 123123123;\\ - unsigned long t1 = xorshift();\\ - unsigned long t2 = xor128();\\ - unsigned long t3 = xorwow();\\ - 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} -} -\end{center} -\caption{sequential Chaotic Iteration PRNG} -\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 -\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} - -On parle du passage du sequentiel au GPU -\section{Experiments} -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{Conclusion}