fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Threading;
  4. using System.Diagnostics;
  5. using System.Runtime.CompilerServices;
  6.  
  7. // 64 bit fnv-1a hash
  8. // : http://w...content-available-to-author-only...e.com/chongo/tech/comp/fnv/
  9. public class FnvHash64
  10. {
  11.     private ulong _hash = 14695981039346656037ul;
  12.  
  13.     public ulong Value
  14.     {
  15.         get { return _hash; }
  16.     }
  17.  
  18.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
  19.     public void AppendByte(byte b)
  20.     {
  21.         _hash = _hash ^ b;
  22.         _hash = _hash * 1099511628211ul;
  23.     }
  24.  
  25.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
  26.     public void AppendShort(ushort x)
  27.     {
  28.         AppendByte((byte)(x & 0xff));
  29.         AppendByte((byte)((x >> 8) & 0xff));
  30.     }
  31.  
  32.     public void AppendInt(uint x)
  33.     {
  34.         AppendByte((byte)(x & 0xff));
  35.         AppendByte((byte)((x >> 8) & 0xff));
  36.         AppendByte((byte)((x >> 16) & 0xff));
  37.         AppendByte((byte)((x >> 24) & 0xff));
  38.     }
  39.  
  40.     public void AppendLong(ulong x)
  41.     {
  42.         AppendByte((byte)(x & 0xff));
  43.         AppendByte((byte)((x >> 8) & 0xff));
  44.         AppendByte((byte)((x >> 16) & 0xff));
  45.         AppendByte((byte)((x >> 24) & 0xff));
  46.         AppendByte((byte)((x >> 32) & 0xff));
  47.         AppendByte((byte)((x >> 40) & 0xff));
  48.         AppendByte((byte)((x >> 48) & 0xff));
  49.         AppendByte((byte)((x >> 56) & 0xff));
  50.     }
  51.  
  52.     public void AppendData(byte [] data)
  53.     {
  54.         for (int i = 0; i < data.Length; i++)
  55.             AppendByte(data[i]);
  56.     }
  57.  
  58.     [MethodImpl(MethodImplOptions.AggressiveInlining)]
  59.     public void AppendChar(char ch)
  60.     {
  61.         AppendShort(ch);
  62.     }
  63.  
  64.     public void AppendStr(string str)
  65.     {
  66.         for (int i = 0; i < str.Length; i++)
  67.             AppendShort(str[i]);
  68.     }
  69. }
  70.  
  71.  
  72. public class Random64: Random
  73. {
  74.     private UInt64 state;
  75.  
  76.     public Random64(): this((ulong)Environment.TickCount)
  77.     {
  78.     }
  79.  
  80.     public Random64(UInt64 seed)
  81.     {
  82.         const UInt64 DefaultSeed = 12030203114834284017ul;
  83.         if (seed != DefaultSeed)
  84.             seed = seed ^ DefaultSeed;
  85.         state = seed;
  86.  
  87.         for (int i = 0; i < 16; i++)
  88.             Next64();
  89.     }
  90.  
  91.     // XorShift implementation
  92.     // : http://w...content-available-to-author-only...x.com/tutorials/random_numbers/xorshift.shtml 
  93.     //   (Numerical Recipes, 3rd ed, p. 346)
  94.     //    - performace is likely limited by the virtual call, 
  95.     //      unless inlining optimizations work well
  96.     public virtual UInt64 Next64()
  97.     {
  98.         state ^= state << 21;
  99.         state ^= state >> 35;
  100.         state ^= state << 4;
  101.         return state - 1;
  102.     }
  103.  
  104.     protected override double Sample()
  105.     {
  106.         const double inv2r64 = 5.4210108624275216e-20;
  107.         //const double largestSub1 = 0.99999999999999989;
  108.         //Console.WriteLine("sub1: {0:f30}, <1: {1}", largestSub1, largestSub1 < 1.0);
  109.         //double maxSample = (double)ulong.MaxValue * inv2r64; 
  110.         //Console.WriteLine("maxS: {0:f30}, <1: {1}", maxSample, maxSample < 1.0);
  111.  
  112.         UInt64 val64 = Next64();
  113.         double sampledVal = (double)val64 * inv2r64;
  114.  
  115.         // >=1.0 is not needed and contains a branch, although a never taken one, 
  116.         //     and efficient compilation has 2 evaluated instructions 
  117.         //     (cmp x,1.0; jge ~never;; return; ~never: mv x,L; return)
  118.         //   : maxSample < 1 => product with any smaller val64 should be < 1 too, 
  119.         //     else ordering problems (could break Sort assumptions)
  120.         //if (sampledVal >= 1.0)
  121.         //    sampledVal = largestSub1;
  122.         return sampledVal;
  123.     }
  124.  
  125.     public override int Next()
  126.     {
  127.         UInt64 val64 = Next64();
  128.         int val = (int)(val64 & 0x7fffffff);
  129.         return val;
  130.     }
  131.  
  132.     private const int HaltLimit = 1000000;
  133.  
  134.     public override int Next(int maxValue)
  135.     {
  136.         if (maxValue < 0)
  137.             throw new Exception("Invalid parameter");
  138.         else if (maxValue < 2)
  139.             return 0;
  140.  
  141.         UInt64 maxValue64 = (UInt64)maxValue;
  142.         UInt64 limitValue = UInt64.MaxValue - UInt64.MaxValue % maxValue64;
  143.  
  144.         UInt64 val64 = Next64();
  145.         int haltCount = HaltLimit;
  146.         while (val64 >= limitValue && --haltCount >= 0)
  147.             val64 = Next64();
  148.  
  149.         UInt64 val = val64 % maxValue64;
  150.  
  151.         return (int)val;
  152.     }
  153.  
  154.     public override int Next(int minValue, int maxValue)
  155.     {
  156.         if (minValue > maxValue)
  157.             throw new Exception("Invalid parameter");
  158.         else if ((long)maxValue - (long)minValue < 2)
  159.             return minValue;
  160.  
  161.         UInt64 valueIntLen = (ulong)((long)maxValue - (long)minValue); // at most uint.MaxValue
  162.         UInt64 limitValue = UInt64.MaxValue - UInt64.MaxValue % valueIntLen;
  163.  
  164.         UInt64 val64 = Next64();
  165.         int haltCount = HaltLimit;
  166.         while (val64 >= limitValue && --haltCount >= 0)
  167.             val64 = Next64();
  168.  
  169.         UInt64 randDiff = val64 % valueIntLen;
  170.         long val = (long)minValue + (long)randDiff;
  171.  
  172.         return (int)val;
  173.     }
  174.  
  175.     public override void NextBytes(byte[] buffer)
  176.     {
  177.         int len = buffer.Length;
  178.         int lenX8 = len - len % 8; // len & 0x7ffffff8 = len & (MaxInt ^ 0x7)
  179.  
  180.         for (int i = 0; i < lenX8; i += 8)
  181.         {
  182.             UInt64 val = Next64();
  183.             buffer[i + 0] = (byte)(val & 0xff);
  184.             buffer[i + 1] = (byte)((val >> 8) & 0xff);
  185.             buffer[i + 2] = (byte)((val >> 16) & 0xff);
  186.             buffer[i + 3] = (byte)((val >> 24) & 0xff);
  187.             buffer[i + 4] = (byte)((val >> 32) & 0xff);
  188.             buffer[i + 5] = (byte)((val >> 40) & 0xff);
  189.             buffer[i + 6] = (byte)((val >> 48) & 0xff);
  190.             buffer[i + 7] = (byte)((val >> 56) & 0xff);
  191.         }
  192.  
  193.         if (lenX8 < len)
  194.         {
  195.             UInt64 val = Next64();
  196.             for (int i = lenX8, j = 0; i < len; i++, j++)
  197.             {
  198.                 buffer[i] = (byte)((val >> (8*j)) & 0xff);
  199.             }
  200.         }
  201.  
  202.     }
  203.  
  204.     public override double NextDouble()
  205.     {
  206.         // [performance note] calling virtual Sample which calls virtual Next64
  207.         return Sample();
  208.     }
  209.  
  210.     // Quality random seed 
  211.     //   : not crypto qyality but better than the constructor default, which is just simple and fast
  212.     public static UInt64 HashSeed
  213.     {
  214.         get
  215.         {
  216.             Process process = Process.GetCurrentProcess();
  217.  
  218.             FnvHash64 hash = new FnvHash64();
  219.             hash.AppendStr(Environment.MachineName); // network unique
  220.             hash.AppendInt((uint)process.Id); // system unique
  221.             hash.AppendInt((uint)Thread.CurrentThread.ManagedThreadId); // process or system unique
  222.  
  223.             hash.AppendLong((ulong)process.StartTime.Ticks); // constant for process, for seed used like process Id but more random bits
  224.             hash.AppendLong((ulong)process.TotalProcessorTime.Ticks);
  225.  
  226.             hash.AppendInt((uint)Environment.TickCount);
  227.             hash.AppendLong((ulong)DateTime.Now.Ticks); // brings most randomness for seed (easy to predict, but not crypto anyway)
  228.  
  229.             return hash.Value; // maybe 30-40 bits of randomness
  230.         }
  231.     }
  232. }
  233.  
  234.  
  235. public class Test
  236. {
  237.     public static void RandomPermute<T>(IList<T> items, Random rnd)
  238.     {
  239.         int icount = items.Count;
  240.         // [NOTE] Random.Next(maxValue) implementation is biased, can be overriden
  241.         //
  242.         // [TODO] mathematically prove equivalence with selecting a random available position in a new list 
  243.         //        or with any other clear randomness
  244.         //   : [draft notes]: all elements are fully randomized, once randomized it remains randomized, potential further moves are just as random,
  245.         //     nothing useful added / nothing lost at randomness by further fully random moves,
  246.         //     once fully random (any position could move to any) without RNG bias then no implicit algorithm bias is relevant 
  247.         //     (i.e. could apply any algorithm based on indices and the values remain randomly distributed)
  248.         // [TODO] at which swap count the random 2 elements swap becomes equivalent to this?
  249.         //   - [draft notes]: must be related with the probability for any element not to move at all with an end result that is
  250.         //     equivalent with a fully randomized list 
  251.         //     (in the same position we have elements that did not move at all and elements that moved back, 
  252.         //      the most probable count being same as in fully randomized and equally probable for all elements)
  253.         //      - the count may be infinite because always a small chance that one element was not touched and the touched ones
  254.         //        have the exact fully random distribution, like always a small bias that some elements remain outside the 
  255.         //        full randomization, like a bias for more elements on original position
  256.         //          - how much is the bias, does it matter at 1000*count ?
  257.         for (int i = 0; i < icount; i++)
  258.         {
  259.             int dsti = rnd.Next(icount);
  260.             T itemVal = items[i];
  261.             items[i] = items[dsti];
  262.             items[dsti] = itemVal;
  263.         }
  264.     }
  265.  
  266.  
  267.     public static void PermuteReverseRand1of5<T>(IList<T> items, Random rnd)
  268.     {
  269.         int icount = items.Count;
  270.         if (icount < 2)
  271.             return;
  272.  
  273.         // reverse list
  274.         for (int i = 0; i < icount/2; i++)
  275.         {
  276.             T aux = items[i];
  277.             items[i] = items[icount - i - 1];
  278.             items[icount - i - 1] = aux;
  279.         }
  280.  
  281.         // n/10 random swaps -> ~n/5 swapped elements (1 - 1/e^(1/5) ~= 0.18 * n)
  282.         //   : prob. not to be swapped: ((n - 1)/n)^(n/5) -> 1/e^(1/5) , 
  283.         //     https://w...content-available-to-author-only...a.com/input/?i=%28%28n+-+1%29%2Fn%29%5E%28n%2F5%29
  284.         int swapCount = icount / 10;
  285.         for (int i = 0; i < swapCount; i++)
  286.         {
  287.             int srcI = rnd.Next(icount);
  288.             int dstI = rnd.Next(icount);
  289.             T aux = items[srcI];
  290.             items[srcI] = items[dstI];
  291.             items[dstI] = aux;
  292.         }
  293.     }
  294.  
  295.  
  296.     public static double EstimatePi(int sampleCount, Random rnd)
  297.     {
  298.     	// Sampling the area of a cicle quadrant fit inside a square
  299.         // A4 = PI * r^2 / 4, r = 1 => A4 = PI / 4 => PI = 4 * A4, A4 = InR / All
  300.         int inCircleCount = 0;
  301.         for (int i = 0; i < sampleCount; i++)
  302.         {
  303.             double x = rnd.NextDouble(), y = rnd.NextDouble();
  304.             double d2 = x * x + y * y;
  305.             if (d2 <= 1)
  306.                 inCircleCount += 1;
  307.         }
  308.  
  309.         double pi = 4.0 * (double)inCircleCount / (double)sampleCount;
  310.         return pi;
  311.     }
  312.  
  313.  
  314. 	public static void Main()
  315. 	{
  316. 		Random rnd = new Random64(Random64.HashSeed);
  317.  
  318.         List<int> lsA = new List<int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  319.         RandomPermute(lsA, rnd);
  320.         lsA.ForEach(a => Console.Write("{0}, ", a)); Console.WriteLine(";");
  321.  
  322.         double pi = EstimatePi(100000, rnd);
  323.         Console.WriteLine("pi ~= {0:F9}, err: {1:F9} (PI = {2:F9})", pi, 
  324.                           Math.Abs(Math.PI - pi), Math.PI);
  325. 	}
  326. }
Success #stdin #stdout 0.04s 19952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1, 9, 4, 2, 5, 6, 8, 7, 0, 3, ;
pi ~= 3.148160000, err: 0.006567346 (PI = 3.141592654)
https://ideone.com/1aQYr7
language:
C# (gmcs 5.20.1)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!