suite

[turing4complexity.git] / turing4complexity.tex

diff --git a/turing4complexity.tex b/turing4complexity.tex
index bbc2e69263d2af70664803c6962b264002771743..c3898bbe0c504e8ec551ad77b5db1d163086fe93 100644 (file)
--- a/turing4complexity.tex
+++ b/turing4complexity.tex
@@ -16,10 +16,10 @@ blabalbabla
 
 \section{Algorithmic complexity for short strings}
 
 
 \section{Algorithmic complexity for short strings}
 

-In their paper, they introduced a method to compute the complexity of D(n).
+In their paper, they introduced a method to compute the complexity of $D(n)$.

 With D(4), 5 970 768 960 machines halt. There are 1832 different strings.
 
 With D(4), 5 970 768 960 machines halt. There are 1832 different strings.
 

-\section{PRNG preserve distribution of short strings}
+\section{Property: a PRNG must preserve the distribution of short strings}

 
 In this section, we propose to measure the quality of a PRNG by considering that
 a good PRNG must preserve the distribution of short strings. More precisely, the
 
 In this section, we propose to measure the quality of a PRNG by considering that
 a good PRNG must preserve the distribution of short strings. More precisely, the


@@ -27,6 +27,82 @@ pseudo-random  numbers obtained  by a  PRNG can  form the  states of  the Rado's
 original  Busy Beaver. Then,  machines obtained  by such  a construction  can be
 executed and if the PRNG is good, machines should generate the same strings with
 the same distribution than the theoretical Busy Beaver (with all the enumeration
 original  Busy Beaver. Then,  machines obtained  by such  a construction  can be
 executed and if the PRNG is good, machines should generate the same strings with
 the same distribution than the theoretical Busy Beaver (with all the enumeration

-of states).
+of states).  In  practice, PRNGs will not generate all  the strings with exactly
+the  same  probabilities. Nevertheless,  the  distance  between the  theoretical
+probabibilities and the obtained probabilities  with a PRNG is a good indication
+of the quality of the PRNG.
+
+In the  following we report our  experiments. Let $S(n)_i$ be  the string number
+$i$  obtained by  the  busy  beaver $D(n)$,  $S(n)$  is the  set  of strings  of
+$D(n)$. With $D(4)$ there are  1832 strings, so $|S(4)|=1832$.  $N_{bb}(S(n)_i)$ is
+the number of occurrences of the string $S(n)_i$ obtained by the Busy Beaver and $N_{PRNG}(S(n)_i)$ is the
+number of occurrences  of the  string  $S(n)_i$ obtained  with  the execution  of a  given
+PRNG. In  order to measure the  distance between the theoretical  result and the
+pratical one, we use this measure:
+\begin{equation}
+Dist(PRNG,BB)=\sum_{i=1}^{|S(n)|} \frac{|N_{bb}S(n)_i-N_{PRNG}S(n)_i|}{N_{bb}S(n)_i}
+\end{equation}
+
+Here are the result for some PRNGS: bbs, lcg, xor128, rand, xorshift, devrandom,
+newprng,  isaac.  These results  are  reported  for  experiments with  different
+numbers of random number generation.
+
+
+\begin{table}
+\begin{tabular}{|l|l|}
+\hline
+                & Number of experiments\\
+\hline
+Name of PRNG    &  500000000\\
+\hline
+BBS             & 358.38\\
+\hline
+lcg             & 491.78\\
+\hline
+xor128          & 380.69\\
+\hline 
+rand            & 382.04\\
+\hline
+xorshift        & 372.68\\
+\hline
+dev random      & 376.78\\
+\hline
+new prng        & 367.42\\
+\hline
+isaac           & 366.91\\
+\hline
+\end{tabular}
+\caption{Distance for some PRNG with different number generations}
+\end{table}
+
+
+In the following table, we report the same experiment with small occurence strings (i.e. less than 50).
+\begin{table}
+\begin{tabular}{|l|l|}
+\hline
+                & Number of experiments\\
+\hline
+Name of PRNG    &  500000000\\
+\hline
+BBS             & 322.88\\
+\hline
+lcg             & 435.89\\
+\hline
+xor128          & 347.61\\
+\hline 
+rand            & 348.02\\
+\hline
+xorshift        & 338.33\\
+\hline
+dev random      & 341.16\\
+\hline
+new prng        & 335.00\\
+\hline
+isaac           & 333.39\\
+\hline
+\end{tabular}
+\caption{Distance for some PRNG with different number generations for small occurrence strings}
+\end{table}
+

 
 \end{document}
 
 \end{document}