[29] | 1 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
---|
| 2 | |
---|
| 3 | <html> |
---|
| 4 | <head> |
---|
| 5 | <meta http-equiv="Content-Language" content="en-us"> |
---|
| 6 | <meta http-equiv="Content-Type" content="text/html; charset=us-ascii"> |
---|
| 7 | |
---|
| 8 | <title>Boost Random Number Library Performance</title> |
---|
| 9 | </head> |
---|
| 10 | |
---|
| 11 | <body bgcolor="#FFFFFF" text="#000000"> |
---|
| 12 | <h1>Random Number Library Performance</h1> |
---|
| 13 | |
---|
| 14 | <p>For some people, performance of random number generation is an important |
---|
| 15 | consideration when choosing a random number generator or a particular |
---|
| 16 | distribution function. This page provides numerous performance tests with |
---|
| 17 | the wide variety of generators and distributions available in the boost |
---|
| 18 | library.</p> |
---|
| 19 | |
---|
| 20 | <p>The performance has been evaluated on a Pentium Pro 200 MHz with gcc |
---|
| 21 | 2.95.2, Linux 2.2.13, glibc 2.1.2. The speed is reported in million random |
---|
| 22 | numbers per second (M rn/sec), generated in a tight loop.</p> |
---|
| 23 | |
---|
| 24 | <h2>Basic Generators</h2> |
---|
| 25 | |
---|
| 26 | <table border="1" summary=""> |
---|
| 27 | <tr> |
---|
| 28 | <th>generator</th> |
---|
| 29 | |
---|
| 30 | <th>M rn/sec</th> |
---|
| 31 | |
---|
| 32 | <th>time per random number [usec]</th> |
---|
| 33 | |
---|
| 34 | <th>relative speed compared to fastest [percent]</th> |
---|
| 35 | </tr> |
---|
| 36 | |
---|
| 37 | <tr> |
---|
| 38 | <td>rand48</td> |
---|
| 39 | |
---|
| 40 | <td>5.38</td> |
---|
| 41 | |
---|
| 42 | <td>0.183</td> |
---|
| 43 | |
---|
| 44 | <td>61%</td> |
---|
| 45 | </tr> |
---|
| 46 | |
---|
| 47 | <tr> |
---|
| 48 | <td>rand48 run-time configurable</td> |
---|
| 49 | |
---|
| 50 | <td>1.48</td> |
---|
| 51 | |
---|
| 52 | <td>0.677</td> |
---|
| 53 | |
---|
| 54 | <td>17%</td> |
---|
| 55 | </tr> |
---|
| 56 | |
---|
| 57 | <tr> |
---|
| 58 | <td>lrand48 glibc 2.1.2</td> |
---|
| 59 | |
---|
| 60 | <td>1.19</td> |
---|
| 61 | |
---|
| 62 | <td>0.843</td> |
---|
| 63 | |
---|
| 64 | <td>13%</td> |
---|
| 65 | </tr> |
---|
| 66 | |
---|
| 67 | <tr> |
---|
| 68 | <td>minstd_rand</td> |
---|
| 69 | |
---|
| 70 | <td>2.39</td> |
---|
| 71 | |
---|
| 72 | <td>0.318</td> |
---|
| 73 | |
---|
| 74 | <td>35%</td> |
---|
| 75 | </tr> |
---|
| 76 | |
---|
| 77 | <tr> |
---|
| 78 | <td>ecuyer1988</td> |
---|
| 79 | |
---|
| 80 | <td>1.12</td> |
---|
| 81 | |
---|
| 82 | <td>0.892</td> |
---|
| 83 | |
---|
| 84 | <td>13%</td> |
---|
| 85 | </tr> |
---|
| 86 | |
---|
| 87 | <tr> |
---|
| 88 | <td>kreutzer1986</td> |
---|
| 89 | |
---|
| 90 | <td>3.87</td> |
---|
| 91 | |
---|
| 92 | <td>0.258</td> |
---|
| 93 | |
---|
| 94 | <td>43%</td> |
---|
| 95 | </tr> |
---|
| 96 | |
---|
| 97 | <tr> |
---|
| 98 | <td>hellekalek1995 (inversive)</td> |
---|
| 99 | |
---|
| 100 | <td>0.20</td> |
---|
| 101 | |
---|
| 102 | <td>5.12</td> |
---|
| 103 | |
---|
| 104 | <td>2%</td> |
---|
| 105 | </tr> |
---|
| 106 | |
---|
| 107 | <tr> |
---|
| 108 | <td>mt11213b</td> |
---|
| 109 | |
---|
| 110 | <td>6.07</td> |
---|
| 111 | |
---|
| 112 | <td>0.165</td> |
---|
| 113 | |
---|
| 114 | <td>68%</td> |
---|
| 115 | </tr> |
---|
| 116 | |
---|
| 117 | <tr> |
---|
| 118 | <td>mt19937</td> |
---|
| 119 | |
---|
| 120 | <td>6.06</td> |
---|
| 121 | |
---|
| 122 | <td>0.165</td> |
---|
| 123 | |
---|
| 124 | <td>68%</td> |
---|
| 125 | </tr> |
---|
| 126 | |
---|
| 127 | <tr> |
---|
| 128 | <td>mt19937 original</td> |
---|
| 129 | |
---|
| 130 | <td>5.33</td> |
---|
| 131 | |
---|
| 132 | <td>0.188</td> |
---|
| 133 | |
---|
| 134 | <td>60%</td> |
---|
| 135 | </tr> |
---|
| 136 | |
---|
| 137 | <tr> |
---|
| 138 | <td>lagged_fibonacci607</td> |
---|
| 139 | |
---|
| 140 | <td>8.90</td> |
---|
| 141 | |
---|
| 142 | <td>0.112</td> |
---|
| 143 | |
---|
| 144 | <td>100%</td> |
---|
| 145 | </tr> |
---|
| 146 | |
---|
| 147 | <tr> |
---|
| 148 | <td>lagged_fibonacci4423</td> |
---|
| 149 | |
---|
| 150 | <td>8.54</td> |
---|
| 151 | |
---|
| 152 | <td>0.117</td> |
---|
| 153 | |
---|
| 154 | <td>96%</td> |
---|
| 155 | </tr> |
---|
| 156 | |
---|
| 157 | <tr> |
---|
| 158 | <td>lagged_fibonacci19937</td> |
---|
| 159 | |
---|
| 160 | <td>7.49</td> |
---|
| 161 | |
---|
| 162 | <td>0.133</td> |
---|
| 163 | |
---|
| 164 | <td>84%</td> |
---|
| 165 | </tr> |
---|
| 166 | |
---|
| 167 | <tr> |
---|
| 168 | <td>lagged_fibonacci23209</td> |
---|
| 169 | |
---|
| 170 | <td>6.63</td> |
---|
| 171 | |
---|
| 172 | <td>0.151</td> |
---|
| 173 | |
---|
| 174 | <td>74%</td> |
---|
| 175 | </tr> |
---|
| 176 | |
---|
| 177 | <tr> |
---|
| 178 | <td>lagged_fibonacci44497</td> |
---|
| 179 | |
---|
| 180 | <td>4.01</td> |
---|
| 181 | |
---|
| 182 | <td>0.250</td> |
---|
| 183 | |
---|
| 184 | <td>45%</td> |
---|
| 185 | </tr> |
---|
| 186 | </table> |
---|
| 187 | |
---|
| 188 | <p>Note that the lagged Fibonacci generators produce floating-point |
---|
| 189 | numbers, whereas all others produce integers.</p> |
---|
| 190 | |
---|
| 191 | <h2>Distributions</h2> |
---|
| 192 | |
---|
| 193 | <table border="1" summary=""> |
---|
| 194 | <tr> |
---|
| 195 | <th>[M rn/sec]</th> |
---|
| 196 | |
---|
| 197 | <th>minstd_rand</th> |
---|
| 198 | |
---|
| 199 | <th>kreutzer1986</th> |
---|
| 200 | |
---|
| 201 | <th>mt19937</th> |
---|
| 202 | |
---|
| 203 | <th>lagged_fibonacci607</th> |
---|
| 204 | </tr> |
---|
| 205 | |
---|
| 206 | <tr> |
---|
| 207 | <th>uniform_smallint</th> |
---|
| 208 | |
---|
| 209 | <td>1.26</td> |
---|
| 210 | |
---|
| 211 | <td>1.55</td> |
---|
| 212 | |
---|
| 213 | <td>1.93</td> |
---|
| 214 | |
---|
| 215 | <td>-</td> |
---|
| 216 | </tr> |
---|
| 217 | |
---|
| 218 | <tr> |
---|
| 219 | <th>uniform_01</th> |
---|
| 220 | |
---|
| 221 | <td>1.79</td> |
---|
| 222 | |
---|
| 223 | <td>1.88</td> |
---|
| 224 | |
---|
| 225 | <td>3.03</td> |
---|
| 226 | |
---|
| 227 | <td>7.74</td> |
---|
| 228 | </tr> |
---|
| 229 | |
---|
| 230 | <tr> |
---|
| 231 | <th>uniform_real</th> |
---|
| 232 | |
---|
| 233 | <td>1.74</td> |
---|
| 234 | |
---|
| 235 | <td>1.56</td> |
---|
| 236 | |
---|
| 237 | <td>2.34</td> |
---|
| 238 | |
---|
| 239 | <td>6.62</td> |
---|
| 240 | </tr> |
---|
| 241 | |
---|
| 242 | <tr> |
---|
| 243 | <th>geometric</th> |
---|
| 244 | |
---|
| 245 | <td>0.593</td> |
---|
| 246 | |
---|
| 247 | <td>0.629</td> |
---|
| 248 | |
---|
| 249 | <td>0.753</td> |
---|
| 250 | |
---|
| 251 | <td>0.916</td> |
---|
| 252 | </tr> |
---|
| 253 | |
---|
| 254 | <tr> |
---|
| 255 | <th>triangle</th> |
---|
| 256 | |
---|
| 257 | <td>0.97</td> |
---|
| 258 | |
---|
| 259 | <td>1.02</td> |
---|
| 260 | |
---|
| 261 | <td>1.35</td> |
---|
| 262 | |
---|
| 263 | <td>1.31</td> |
---|
| 264 | </tr> |
---|
| 265 | |
---|
| 266 | <tr> |
---|
| 267 | <th>exponential</th> |
---|
| 268 | |
---|
| 269 | <td>0.849</td> |
---|
| 270 | |
---|
| 271 | <td>0.828</td> |
---|
| 272 | |
---|
| 273 | <td>0.887</td> |
---|
| 274 | |
---|
| 275 | <td>1.53</td> |
---|
| 276 | </tr> |
---|
| 277 | |
---|
| 278 | <tr> |
---|
| 279 | <th>normal (polar method)</th> |
---|
| 280 | |
---|
| 281 | <td>0.608</td> |
---|
| 282 | |
---|
| 283 | <td>0.626</td> |
---|
| 284 | |
---|
| 285 | <td>0.738</td> |
---|
| 286 | |
---|
| 287 | <td>0.755</td> |
---|
| 288 | </tr> |
---|
| 289 | |
---|
| 290 | <tr> |
---|
| 291 | <th>lognormal</th> |
---|
| 292 | |
---|
| 293 | <td>0.417</td> |
---|
| 294 | |
---|
| 295 | <td>0.442</td> |
---|
| 296 | |
---|
| 297 | <td>0.470</td> |
---|
| 298 | |
---|
| 299 | <td>0.481</td> |
---|
| 300 | </tr> |
---|
| 301 | |
---|
| 302 | <tr> |
---|
| 303 | <th>uniform_on_sphere</th> |
---|
| 304 | |
---|
| 305 | <td>0.154</td> |
---|
| 306 | |
---|
| 307 | <td>0.155</td> |
---|
| 308 | |
---|
| 309 | <td>0.174</td> |
---|
| 310 | |
---|
| 311 | <td>0.218</td> |
---|
| 312 | </tr> |
---|
| 313 | </table> |
---|
| 314 | |
---|
| 315 | <p>Note that the lagged Fibonacci generator is at least 2.5 times faster |
---|
| 316 | than the Mersenne twister when generating uniformly distributed |
---|
| 317 | floating-point numbers. For more sophisticated distributions, the speed |
---|
| 318 | improvement is less. Note however that these distributions have not been |
---|
| 319 | optimized for speed, yet.</p> |
---|
| 320 | <hr> |
---|
| 321 | |
---|
| 322 | <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src= |
---|
| 323 | "http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Transitional" |
---|
| 324 | height="31" width="88"></a></p> |
---|
| 325 | |
---|
| 326 | <p>Revised |
---|
| 327 | <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05 |
---|
| 328 | December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p> |
---|
| 329 | |
---|
| 330 | <p><i>Copyright © 2001 <a href="../../people/jens_maurer.htm">Jens |
---|
| 331 | Maurer</a></i></p> |
---|
| 332 | |
---|
| 333 | <p><i>Distributed under the Boost Software License, Version 1.0. (See |
---|
| 334 | accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or |
---|
| 335 | copy at <a href= |
---|
| 336 | "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p> |
---|
| 337 | </body> |
---|
| 338 | </html> |
---|