new

[turing4complexity.git] / turing4complexity.tex

diff --git a/turing4complexity.tex b/turing4complexity.tex
index 21460399dc780fce7b943d895178dd110aec1dd0..5753ad8bbc798f7ae8c3cb8568a03be42436895d 100644 (file)
--- a/turing4complexity.tex
+++ b/turing4complexity.tex
@@ -16,7 +16,7 @@ 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.
 
 \section{Property: a PRNG must preserve the distribution of short strings}
 With D(4), 5 970 768 960 machines halt. There are 1832 different strings.
 
 \section{Property: a PRNG must preserve the distribution of short strings}


@@ -32,11 +32,139 @@ 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.
 
 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_i$ be  the string number $i$
-obtained by the busy beaver, $S(n)$ is the set of strings of $D(n)$. With $D(4)$
-there  are  1832  strings,  so  $|S(4)|=1832$.  $P_t(S_i)$  is  the  theoretical
-probability of  the string $S_i$ and  $P_{PRNG}(S_i)$ is the  probability of the
-string $S_i$  obtained with the execution of  a given PRNG. Let  For $D(n)$, the
-number of strings is
+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    &  500,000,000\\
+\hline
+lcg             & 491.78\\
+\hline
+rand            & 382.04\\
+\hline
+xor128          & 380.69\\
+\hline
+dev random      & 376.78\\
+\hline
+xorshift        & 372.68\\
+\hline 
+new prng        & 367.42\\
+\hline
+isaac           & 366.91\\
+\hline
+BBS             & 358.38\\
+\hline
+
+\end{tabular}
+\caption{Distance for some PRNG with different number generations in decreasing ordering}
+\end{table}
+
+
+
+\begin{table}
+\begin{tabular}{|l|l|}
+\hline
+                & Number of experiments\\
+\hline
+Name of PRNG    &  500,000,000\\
+\hline
+lcg             & 2652694\\
+\hline
+rand            & 1511.34\\
+\hline
+xor128          & 1489.53\\
+\hline
+dev random      & 1477.99\\
+\hline
+xorshift        & 1474.00\\
+\hline 
+BBS             & 1403.50\\
+\hline
+isaac           & 1397.28\\
+\hline
+new prng        & 1356.76\\
+\hline
+
+\end{tabular}
+\caption{Chi squared for some PRNG with different number generations in decreasing ordering}
+\end{table}
+
+
+\begin{table}
+\begin{tabular}{|l|l|}
+\hline
+                & Number of experiments\\
+\hline
+Name of PRNG    &  50,000,000\\
+\hline
+lcg             & 1191.87\\
+\hline
+rand            & 1187.18\\
+\hline
+xorshift        & 1257.87\\
+\hline 
+new prng        & 1210.77\\
+\hline
+dev random      & 1190.33\\
+\hline
+xor128          & 1190.11\\
+\hline
+isaac           & 1188.74\\
+\hline
+BBS             & 1185.77\\
+\hline
+
+\end{tabular}
+\caption{Distance for some PRNG with different number generations in decreasing ordering}
+\end{table}
+
+
+\begin{table}
+\begin{tabular}{|l|l|}
+\hline
+                & Number of experiments\\
+\hline
+Name of PRNG    &  50,000,000\\
+\hline
+lcg             & 2664408\\
+\hline
+xorshift        & 14904.91\\
+\hline 
+new prng        & 14711.53\\
+\hline
+dev random      & 14189.61\\
+\hline
+BBS             & 13857.77\\
+\hline
+isaac           & 13933.8\\
+\hline
+xor128          & 13426.15\\
+\hline
+rand            & 13339.74\\
+\hline
+
+\end{tabular}
+\caption{Chi squared for some PRNG with different number generations in decreasing ordering}
+\end{table}
+
+
+

 
 \end{document}
 
 \end{document}