turing4complexity.tex

   1 \documentclass{article}
   2
   3 \title{Using complexity of short strings to define new statistical tests for PRNGs}
   4
   5
   6 \begin{document}
   7 \maketitle
   8
   9
  10 \begin{abstract}
  11 blabalbabla
  12 \end{abstract}
  13
  14
  15 \section{Introduction}
  16
  17 \section{Algorithmic complexity for short strings}
  18
  19 In their paper, they introduced a method to compute the complexity of $D(n)$.
  20 With D(4), 5 970 768 960 machines halt. There are 1832 different strings.
  21
  22 \section{Property: a PRNG must preserve the distribution of short strings}
  23
  24 In this section, we propose to measure the quality of a PRNG by considering that
  25 a good PRNG must preserve the distribution of short strings. More precisely, the
  26 pseudo-random  numbers obtained  by a  PRNG can  form the  states of  the Rado's
  27 original  Busy Beaver. Then,  machines obtained  by such  a construction  can be
  28 executed and if the PRNG is good, machines should generate the same strings with
  29 the same distribution than the theoretical Busy Beaver (with all the enumeration
  30 of states).  In  practice, PRNGs will not generate all  the strings with exactly
  31 the  same  probabilities. Nevertheless,  the  distance  between the  theoretical
  32 probabibilities and the obtained probabilities  with a PRNG is a good indication
  33 of the quality of the PRNG.
  34
  35 In the  following we report our  experiments. Let $S(n)_i$ be  the string number
  36 $i$  obtained by  the  busy  beaver $D(n)$,  $S(n)$  is the  set  of strings  of
  37 $D(n)$. With $D(4)$ there are  1832 strings, so $|S(4)|=1832$.  $N_{bb}(S(n)_i)$ is
  38 the number of occurrences of the string $S(n)_i$ obtained by the Busy Beaver and $N_{PRNG}(S(n)_i)$ is the
  39 number of occurrences  of the  string  $S(n)_i$ obtained  with  the execution  of a  given
  40 PRNG. In  order to measure the  distance between the theoretical  result and the
  41 pratical one, we use this measure:
  42 \begin{equation}
  43 Dist(PRNG,BB)=\sum_{i=1}^{|S(n)|} \frac{|N_{bb}S(n)_i-N_{PRNG}S(n)_i|}{N_{bb}S(n)_i}
  44 \end{equation}
  45
  46 Here are the result for some PRNGS: bbs, lcg, xor128, rand, xorshift, devrandom,
  47 newprng,  isaac.  These results  are  reported  for  experiments with  different
  48 numbers of random number generation.
  49
  50
  51 \begin{table}
  52 \begin{tabular}{|l|l|}
  53 \hline
  54                 & Number of experiments\\
  55 \hline
  56 Name of PRNG    &  500000000\\
  57 \hline
  58 BBS             & 358.38\\
  59 \hline
  60 lcg             & 491.78\\
  61 \hline
  62 xor128          & 380.69\\
  63 \hline
  64 rand            & 382.04\\
  65 \hline
  66 xorshift        & 372.68\\
  67 \hline
  68 dev random      & 376.78\\
  69 \hline
  70 new prng        & 367.42\\
  71 \hline
  72 isaac           & 366.91\\
  73 \hline
  74 \end{tabular}
  75 \caption{Distance for some PRNG with different number generations}
  76 \end{table}
  77
  78
  79 In the following table, we report the same experiment with small occurence strings (i.e. less than 50).
  80 \begin{table}
  81 \begin{tabular}{|l|l|}
  82 \hline
  83                 & Number of experiments\\
  84 \hline
  85 Name of PRNG    &  500000000\\
  86 \hline
  87 BBS             & 322.88\\
  88 \hline
  89 lcg             & 435.89\\
  90 \hline
  91 xor128          & 347.61\\
  92 \hline
  93 rand            & 348.02\\
  94 \hline
  95 xorshift        & 338.33\\
  96 \hline
  97 dev random      & 341.16\\
  98 \hline
  99 new prng        & 335.00\\
 100 \hline
 101 isaac           & 333.39\\
 102 \hline
 103 \end{tabular}
 104 \caption{Distance for some PRNG with different number generations for small occurrence strings}
 105 \end{table}
 106
 107
 108 \end{document}