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    &  500,000,000\\
  57 \hline
  58 lcg             & 491.78\\
  59 \hline
  60 rand            & 382.04\\
  61 \hline
  62 xor128          & 380.69\\
  63 \hline
  64 dev random      & 376.78\\
  65 \hline
  66 xorshift        & 372.68\\
  67 \hline
  68 new prng        & 367.42\\
  69 \hline
  70 isaac           & 366.91\\
  71 \hline
  72 BBS             & 358.38\\
  73 \hline
  74
  75 \end{tabular}
  76 \caption{Distance for some PRNG with different number generations in decreasing ordering}
  77 \end{table}
  78
  79
  80
  81 \begin{table}
  82 \begin{tabular}{|l|l|}
  83 \hline
  84                 & Number of experiments\\
  85 \hline
  86 Name of PRNG    &  500,000,000\\
  87 \hline
  88 lcg             & 2652694\\
  89 \hline
  90 rand            & 1511.34\\
  91 \hline
  92 xor128          & 1489.53\\
  93 \hline
  94 dev random      & 1477.99\\
  95 \hline
  96 xorshift        & 1474.00\\
  97 \hline
  98 BBS             & 1403.50\\
  99 \hline
 100 isaac           & 1397.28\\
 101 \hline
 102 new prng        & 1356.76\\
 103 \hline
 104
 105 \end{tabular}
 106 \caption{Chi squared for some PRNG with different number generations in decreasing ordering}
 107 \end{table}
 108
 109
 110 \begin{table}
 111 \begin{tabular}{|l|l|}
 112 \hline
 113                 & Number of experiments\\
 114 \hline
 115 Name of PRNG    &  50,000,000\\
 116 \hline
 117 lcg             & 1191.87\\
 118 \hline
 119 rand            & 1187.18\\
 120 \hline
 121 xorshift        & 1257.87\\
 122 \hline
 123 new prng        & 1210.77\\
 124 \hline
 125 dev random      & 1190.33\\
 126 \hline
 127 xor128          & 1190.11\\
 128 \hline
 129 isaac           & 1188.74\\
 130 \hline
 131 BBS             & 1185.77\\
 132 \hline
 133
 134 \end{tabular}
 135 \caption{Distance for some PRNG with different number generations in decreasing ordering}
 136 \end{table}
 137
 138
 139 \begin{table}
 140 \begin{tabular}{|l|l|}
 141 \hline
 142                 & Number of experiments\\
 143 \hline
 144 Name of PRNG    &  50,000,000\\
 145 \hline
 146 lcg             & 2664408\\
 147 \hline
 148 xorshift        & 14904.91\\
 149 \hline
 150 new prng        & 14711.53\\
 151 \hline
 152 dev random      & 14189.61\\
 153 \hline
 154 BBS             & 13857.77\\
 155 \hline
 156 isaac           & 13933.8\\
 157 \hline
 158 xor128          & 13426.15\\
 159 \hline
 160 rand            & 13339.74\\
 161 \hline
 162
 163 \end{tabular}
 164 \caption{Chi squared for some PRNG with different number generations in decreasing ordering}
 165 \end{table}
 166
 167
 168
 169
 170 \end{document}