/* Source code of System.Random is available at: CodePlex/Random.cs System.Random is fast, basically a new random number is generated by a subtraction of two numbers. A straightforward copy of the source code is two times slower compared to using rand.Next directly. A way to speed it up: the codeplex code uses a multiplication by a double type. The multiplication can be replaced by a shift and an "if" statement when 30 random bits are needed, very occasionally an addition "+ 1" (and an "& 1") are necessary, that's what "Next30()" does in, voila: Fast Random Range (CodePlex) Other improvements over the previous version: -a 64 bits buffer, instead of a 32 bits one. Operations like "uint + uint" are as fast as "ulong + uint", same for: " - , ^ , | , << , >> " -Random numbers were computed bit by bit, now the bits are taken at once, some bit twiddling recycles unused random bits. Finally: A probably very true scaled (pseudo) random number generator, based on the .Net4 RNGCryptoServiceProvider class: ".. rng = new RNGCryptoServiceProvider". The "rng.Getbytes(..)" method fills a byte array, one byte as fast as 40 bytes, 40 bytes seems to be an optimum. "Buffer.BlockCopy" copies the byte array to a uint array. The uint array is used to fill a 64 random bits buffer, etc. "uint x = g_uint_c(uint u)" gives a random value for x, such that: 0 <= x <= u <= uint.MaxValue Results: 10^7 times rand.Next() takes: 107 ms (~11 ns per random number) 10^7 times rand.Next(int someValue) takes: 236 ms (~24 ns ...) |--------|-------------------------| rand.Next() 11 ns | | ms 10^7 * | rand.Next(i) 24 ns | |-----------|-------------| gen_uint(u) 50 ns, mean ~35 ns | u |gen_uint(u)| g_uint_c(u) | g_uint_c(u) 280 ns, mean ~250 ns |--------|-----|-----|------|------| | 0 | 24 | | 24 | | | 1 | | 73 | | 139 | | 2 | 124 | | 296 | | | 3 | | 78 | | 211 | | 4 | 242 | | 518 | | | 7 | | 83 | | 282 | | 8 | 290 | | 680 | | | 2^7-1 | | 102 | | 562 | | 2^7-0 | 380 | | 1079 | | | 2^15-1 | | 130 | | 1123 | | 2^15-0 | 414 | | 1634 | | | 2^30-1 | | 193 | | 2164 | | 2^30-0 | 494 | | 2672 | | | 2^31-1 | | 210 | | 2251 | | 2^31-0 | 461 | | 2747 | | | 2^32-1 | | 211 | | 2307 | |--------|-----|-----|------|------| http://www.cacert.at/cgi-bin/rngresults find: "P_P" , hover mouse over "Net4 System.Random" for the code. Random ~ gen_uint(u) CSP ~ g_uint_c(u) |--------|---------|--------|----------|----------|--------|---------|----------|----------|----------|----------| | Gene- | Speed | Upload | Entropy | Birthday | Matrix | 6*8 Ma- | Minimum | Random | Squeeze | Overlap- | | rator | (MiB/s) | Size | (->8) | Spacing | Ranks | trix R | Distance | Spheres | | ping Sums| |--------|---------|--------|----------|----------|--------|---------|----------|----------|----------|----------| | Random | 370 | 17 MiB | 7.999989 | 0.000000 | 0.392 | 0.136 | 0.063920 | 0.905097 | 0.098440 | 0.005467 | | CSP | 34 | 15 MiB | 7.999987 | 0.032102 | 0.084 | 0.942 | 0.894277 | 0.036221 | 0.706538 | 0.023523 | |--------|---------|--------|----------|----------|--------|---------|----------|----------|----------|----------| */ using System; using System.Diagnostics; using System.Security.Cryptography; class scaled_random_uint { private static ulong buf = 0; // 64 random bits buffer private static int av = 0; // available bits in buf private static uint g_u = 0; // copy of u private static int g_nd = 0; // nd (needed) bits = highest set bit of u private static int g_s = 0; // shift private static bool ones = false; // true if u = 10, 110, 1110, ... private static uint g_uint_c(uint u) { uint x; int s; if (u == 0) return 0; if (u != g_u) { g_u = u; g_nd = nob(u); g_s = 64 - g_nd; ones = (u + 1 & u + 2) == 0; } L0: if (av < g_nd) { av += 32; buf <<= 32; buf |= next32(); } x = (uint)buf << g_s >> g_s; buf >>= g_nd; av -= g_nd; if (x <= u) return x; if (ones) goto L0; // faster when u = 2, 6, 14, ... s = nob(x ^ u) - 1; buf <<= s; buf ^= x; av += s; goto L0; } private static RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider(); private static byte[] r08 = new byte[40]; // ... [400] ... ~15% faster private static uint[] r32 = new uint[10]; // ... [100] ... ,, ,, private static int i_r32 = 10; // ... = 100 ... ,, ,, private static uint next32() { if (i_r32 != 10) return r32[i_r32++]; // ... != 100... ,, ,, i_r32 = 1; rng.GetBytes(r08); Buffer.BlockCopy(r08, 0, r32, 0, 40); // ... , 400)... ,, ,, return r32[0]; } private static int nob(uint u) // number of bits, position of the highest set bit, u > 0 { return u < 1u << 16 ? u < 1u << 08 ? u < 1u << 04 ? u < 1u << 02 ? u < 1u << 01 ? 01 : 02 : u < 1u << 03 ? 03 : 04 : u < 1u << 06 ? u < 1u << 05 ? 05 : 06 : u < 1u << 07 ? 07 : 08 : u < 1u << 12 ? u < 1u << 10 ? u < 1u << 09 ? 09 : 10 : u < 1u << 11 ? 11 : 12 : u < 1u << 14 ? u < 1u << 13 ? 13 : 14 : u < 1u << 15 ? 15 : 16 : u < 1u << 24 ? u < 1u << 20 ? u < 1u << 18 ? u < 1u << 17 ? 17 : 18 : u < 1u << 19 ? 19 : 20 : u < 1u << 22 ? u < 1u << 21 ? 21 : 22 : u < 1u << 23 ? 23 : 24 : u < 1u << 28 ? u < 1u << 26 ? u < 1u << 25 ? 25 : 26 : u < 1u << 27 ? 27 : 28 : u < 1u << 30 ? u < 1u << 29 ? 29 : 30 : u < 1u << 31 ? 31 : 32; } private static Stopwatch sw = new Stopwatch(); static void Main() { speed((1u << 31) - 0); Console.ReadLine(); } private static void speed(uint u) { int i, j = 10000000; double t; sw.Restart(); for (i = 0; i < j; i++) g_uint_c(u); sw.Stop(); t = sw.ElapsedMilliseconds; sw.Restart(); for (i = 0; i < j; i++) ; // nada sw.Stop(); t -= sw.ElapsedMilliseconds; Console.WriteLine("u: " + u); Console.WriteLine("gen_uint(u)"); Console.WriteLine(" ms: " + t); Console.WriteLine(" bits: " + (double)(nob(u)) * j); Console.WriteLine(" bits/s: {0:.000}", (double)((nob(u)) * j) / t / 1000000); Console.WriteLine(); } }
No comments:
Post a Comment