Windows Forms, Random Number Generators, and Parallel Programming

• Download source - 139.31 KB

Introduction and Usage

The purpose of this article to show how to use parallel programming to build a Windows Forms application that is able to use a random number generator to implement an encryption of a quote. The reader will find that when the parallel check box is checked, the number of random number generations is much greater than if done sequentially. Apart from the Windows designer code that is generated by IDE while building form, there is a program file that contains the main function of source execution. The complicated part is understanding the two classes: the TextMatchGeneticAlgorithm.cs and the ThreadSafeRandom.cs algorithm. The ThreadSafeRandom file contains objects that are constructed in the TextMathGeneticAlgorithm file. Both of these files are mutually inclusive to the main form files and the Program.cs files.

Because we are dealing with random number generation of certain types, I am going to begin this article explaining the .NET provisions for these mechanisms. After exemplifying the basics about random number generator (RNGCryptoServiceProvider), the downloadable source ThreadSafeRandom.cs should not appear too complicated. The TextMatchGeneticAlgorithm.cs follows after these parallel patterns. An excellent source of information regarding parallel programming resides at the MSDN Parallel Programming Center. Most of the articles are must reads and useful for both reference and developing your own content.

Abstract

The .NET Framework has two ways of generating random numbers. Most programs will instantiate a System.Random object instance and call one of the member functions to get random numbers. The numbers returned aren't truly random, but rather pseudo random. But they're good enough for most applications that call for randomness. But the pseudo random nature of the numbers returned by System.Random objects is not good enough for cryptographic purposes. The algorithm used by System.Random to generate random numbers is actually generating a sequence in which the next number generated is dependent on the previous number generated. The algorithm is deterministic and predictable. Somebody who knows how the algorithm works can use that information to trivially break any encryption based on the pseudorandom numbers. Cryptographic applications require truly random sequences that can't be predicted. In .NET, the System.Security.Cryptography.RandomNumberGenerator abstract class serves as the base class for all cryptographic random number generators. System.Security.Cryptography.RNGCryptoServiceProvider provides an implementation of that abstract class.

Generating Secure Random Values

The first step in generating truly random values is to create an instance of the RNGCryptoServiceProvider class. Then, allocate an array of bytes and pass that array to the GetBytes method. The random number generator will fill the byte array with a sequence of random values. Here's how to do it in C#.

using System;
using System.Security;
using System.Security.Cryptography;
public class Program {
public static void Main() {
    RNGCryptoServiceProvider random = new RNGCryptoServiceProvider();
    byte[] randomBytes = new byte[1024];
    random.GetBytes(randomBytes);
    foreach (var b in randomBytes)
         {
         Console.Write("{0:X2} ", b);
         }
        }
   }

Here is the output:

7D 96 7D EB C3 A1 81 64 52 7E 80 57 7D 3B 10 2C 8E 7D 27 D8 4F 38 29 99 2E 
32 BB 23 74 4E 61 65 43 45 EB 15 53 9B 50 F2 74 A5 83 9E C0 AF CB 72 53 86 
75 7F 6A 83 D7 74 8A B5 CF D1 B8 F8 BF 2A 7D A6 62 44 6F E9 8B F8 26 C4 CE 
D2 A7 F0 29 94 A9 F8 F6 E6 95 58 6F DF 4F DE 60 2D 56 A4 93 35 3A CA B3 17 
E9 E6 19 C3 41 D7 C6 D1 9E E6 A3 94 C8 A3 20 14 4F F5 83 30 EB 08 C7 39 D2 
65 B3 F1 65 6B 23 1E 61 D9 AA 22 D0 59 BC 02 B5 CC 06 D2 48 0E 14 CD FC D2 
5F 77 17 26 79 40 C6 F9 FE 00 69 EF 9A 3F E4 BE E5 9D FB 89 1D 7F E6 1E A1 
F7 DF BA B6 CC 9F B4 F9 5A 37 FE 58 B5 2F 9F 51 86 FE 69 57 7E F8 45 16 34 
52 3C 8E 87 AF 59 5E 9B EF 61 79 59 AC 73 81 52 7A C9 F4 3F EC E0 C9 5B FE 
30 E8 E9 00 7B DC E6 C5 F4 88 30 93 48 80 B2 0E D9 F5 B4 1F 1D E7 F4 A1 DA 
DA CD CE 26 5F 30 A0 D1 9E 73 01 8D 2D 70 34 51 80 97 08 39 3B C8 0F EC 2A 
18 BD C1 06 95 20 3D F7 3F 79 8A 9C 26 76 10 22 47 01 38 3A 94 04 30 BB A4 
DB A1 FD 3D 43 45 EA F3 0D 1C 87 77 DC C3 41 AC 0D 82 28 05 54 61 42 F5 BC 
1D 92 AC BD 36 53 C7 1F E9 F3 D4 9C 51 B3 69 77 E3 A5 92 52 FF 18 E7 5C 11 
95 09 C2 EE 53 D9 E7 D9 D4 6A 6B 5F D8 B6 08 36 6C 5B 95 A6 24 49 BD 1F B6 
5A 18 1D C5 30 54 33 9B 3C 30 95 83 C3 48 B2 AB 21 92 65 35 E9 86 EC 26 71 
65 5A 94 05 CA 1D FB DE 81 B3 ED 7F 04 20 16 A5 68 2D E2 EC 46 B5 6D 00 17 
2F 81 76 3A 86 11 05 31 ED BA BF 1D 3D D6 69 8F AD 3F 18 94 61 E2 CE B3 08 
2D 6A E7 AF 17 02 75 48 60 00 7D 9B 92 0B A1 A3 62 D6 46 D0 C9 6A E9 FB D5 
03 1C 43 4A 6A 76 1D 45 90 0D D8 6B 64 3A 2C 38 F1 42 4F 98 79 2C 6C 77 69 
3B 87 A4 7E 00 87 15 92 02 67 5C C0 20 1C 81 E7 DF F7 7A 28 6F 7F 70 10 51 
8A 17 67 2C 75 9C 2E 20 C2 5E 80 98 11 CC 46 87 FB 4A 85 65 99 58 06 6D 86 
E2 50 2C FB EA 69 47 DE 3E B2 39 B0 E4 5D B3 63 F3 70 C6 52 67 F1 09 C8 AC 
9D 3E F6 59 72 4B 5C EF F4 5C A7 D0 1B E1 38 7B E8 D0 AC A2 A9 87 9D 8F 99 
DD 13 3D C2 73 61 A3 AC BF 2B 66 8C 28 BC A1 23 53 B6 DA A6 AE BA 5D BC A1 
71 E0 7A BE 08 85 04 3E A9 C8 76 C6 94 23 AB 86 10 79 C5 23 EE 4E E9 0A 27 
3D D4 6E 13 7F 47 98 9C 9F 6A CC 49 07 07 EE 1A 66 5C 11 DA D7 EF 82 AF 51 
6E 5F 7B 5E 05 EB 8E 5D B4 14 9C C0 B0 85 F9 C2 F9 C7 D8 C1 1F 30 32 0A 16 
1E 9F EA BC 30 8E E4 5D BE 08 92 FD 27 BC 1C 84 C7 49 6A 89 6F 50 9E 6D 6D 
D0 7F 9D E0 8E CC 8E 85 30 2B 42 F2 55 7D 11 A7 22 87 47 AF E6 8E 62 89 12 
07 D1 2F 20 09 CB 92 D8 D6 E1 4B 29 85 8D C3 39 A0 B6 16 74 8C C2 33 04 07 
EF EF 1B BA EE FC 69 96 74 95 92 CE 20 25 81 D7 77 CF 41 7A 20 F3 64 9B 3B 
F0 CA 18 E4 F7 E7 4F 80 B5 B9 D2 BF 53 4A 14 D4 5D 81 21 92 CC 94 92 E2 9F 
0C F7 EC 2A 0B 56 22 74 7A 8C 4C 74 49 62 0F 77 11 F2 9B 2B 01 E7 5F 4C 2E 
C1 93 68 08 4F 79 1A BF 57 77 CD D8 AF 38 08 8E DB E2 8D A5 EA DA 5E FF 29 
F5 AF D4 B8 C4 D1 F1 EC BC 01 2D DC 15 31 C9 6F 12 19 75 86 2F B3 43 F0 12 
0E 83 69 EF 49 89 06 67 67 6A C3 01 1A 9A 77 CF 26 95 F0 27 C3 CB 59 AF C5 
3A 6F 91 7A F4 57 C7 24 CE 4F F8 17 D3 29 67 74 9D 3E 70 D1 46 3F 43 80 51 
0A 83 4E C3 28 8C 95 4A F2 EC D8 C1 9B B1 64 EC AF 25 0D 58 28 ED 22 1D 91 
29 C6 86 A3 4F 56 06 2C AF E5 6C F6 49 F7 DF 7D 3F 5A 43 20 63 8B 1F 85 75 
84 CA F0 71 A7 44 70 F0 7B CD 49 B2 59 74 30 37 53 04 A6 16 B3 B9 39 3F

Generating Random Integers

In general, applications that require the use of truly random values don't typically need random integers or random floating point numbers. They just need random bytes. But if you really want random integers or other multi-byte values, you'll have to construct them yourself from the bytes returned by GetBytes. The code below generates 256 random positive integers from the random bytes returned by GetBytes.

 using System;
 using System.Security.Cryptography;
 public class Program {
 public static void Main() {
    RNGCryptoServiceProvider random = new RNGCryptoServiceProvider("testo");
    byte[] randomBytes = new byte[256 * sizeof(int)];
    random.GetBytes(randomBytes);
     for (int i = 0; i < 256; ++i)
       {
         int val = BitConverter.ToInt32(randomBytes, i * 4);
         val &= 0x7fffffff;
         Console.WriteLine(val);
       }
    }
}

Here is the output:

466312334
 22151376
 1681766675
  .  .  .    
 2138931828
 117706740
 1674011901
371608382
1180273970
1851532107
856202020
37047746
1454318877
1370326982
290413720
2020103993
317550161
422861278
526562124
449336275
991713816
1652487604
880619295
633790643
1397989797
696122560
2081704890
338459605
1023259457
903093930
630767348
554883809
809901421
685484127
1992278417
1651570395
1606911073
1970878803
1813967620
1119285127
1545465870
1674136843
212937010
1301413975
1144306793
997391586
234662339
1345235759
1055049749
914349757
1286666161
506392153
1768422944
914725219
335875720
720919927
1278360239
1362332549
270292310
1587219133
403765394
1192342225
597086276
802359086
864984234
1418110830
1778645307
.  .  .  etc
1880851086
1590460413
1932528460
1119714499
315909793
753026156

BitConverter.ToInt32 gets the next four bytes in the array and returns a 32 bit integer. The next line of code just makes sure that the number is positive. If you don't mind getting negative numbers, then you can skip that. Or, you can get unsigned integers by calling BitConverter.ToUInt32.

The Two Class Library Files

Here is ThreadSafeRandom.cs:

using System;
using System.Security.Cryptography;

namespace System.Threading
{    
    public class ThreadSafeRandom : Random
    {
        
        private static readonly RNGCryptoServiceProvider _global = 
					new RNGCryptoServiceProvider();
        
        private ThreadLocal<random> _local = new ThreadLocal<random>(() =>
        {
            var buffer = new byte[4];
            _global.GetBytes(buffer); 	// RNGCryptoServiceProvider is 
					// thread-safe for use in this manner
            return new Random(BitConverter.ToInt32(buffer, 0));
        });

        
        public override int Next()
        {
            return _local.Value.Next();
        }
        
        public override int Next(int maxValue)
        {
            return _local.Value.Next(maxValue);
        }       
        
        public override int Next(int minValue, int maxValue)
        {
            return _local.Value.Next(minValue, maxValue);
        }
        public override double NextDouble()
        {
            return _local.Value.NextDouble();
        }
       
        public override void NextBytes(byte[] buffer)
        {
            _local.Value.NextBytes(buffer);
        }
    }
}

And here is the TextMatchGeneticAlgorithm.cs file:

using System;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Security.Cryptography;
namespace ShakespeareanMonkeys
{
    public class TextMatchGeneticAlgorithm
    {
        private static ThreadSafeRandom _random = new ThreadSafeRandom();
        private static char[] _validChars;
        private string _targetText;
        private GeneticAlgorithmSettings _settings;
        private TextMatchGenome[] _currentPopulation;
        private bool _runParallel;

        static TextMatchGeneticAlgorithm()
        {
            // Initialize the valid characters to newlines plus 
            // all the alphanumerics and symbols
            _validChars = new char[2 + (127 - 32)];
            _validChars[0] = (char)10;
            _validChars[1] = (char)13;
            for (int i = 2, pos = 32; i < _validChars.Length; i++, pos++)
            {
                _validChars[i] = (char)pos;
            }
        }

        public TextMatchGeneticAlgorithm(bool runParallel, 
		string targetText, GeneticAlgorithmSettings settings)
        {
            if (settings == null) throw new ArgumentNullException("settings");
            if (targetText == null) throw new ArgumentNullException("targetText");
            _runParallel = runParallel;
            _settings = settings;
            _targetText = targetText;
        }

        public void MoveNext()
        {
            // If this is the first iteration, create a random population
            if (_currentPopulation == null)
            {
                _currentPopulation = CreateRandomPopulation();
            }
            // Otherwise, iterate
            else _currentPopulation = CreateNextGeneration();
        }

        public TextMatchGenome CurrentBest { get { return _currentPopulation[0]; } }

        private TextMatchGenome[] CreateRandomPopulation()
        {
            return (from i in Enumerable.Range(0, _settings.PopulationSize)
                    select CreateRandomGenome(_random)).ToArray();
        }

        private TextMatchGenome CreateRandomGenome(Random rand)
        {
            var sb = new StringBuilder(_targetText.Length);
            for (int i = 0; i < _targetText.Length; i++)
            {
                sb.Append(_validChars[rand.Next(0, _validChars.Length)]);
            }
            return new TextMatchGenome 
		{ Text = sb.ToString(), TargetText = _targetText };
        }

        private TextMatchGenome[] CreateNextGeneration()
        {
            var maxFitness = _currentPopulation.Max(g => g.Fitness) + 1;
            var sumOfMaxMinusFitness = _currentPopulation.Sum
			(g => (long)(maxFitness - g.Fitness));

            if (_runParallel)
            {
                return (from i in ParallelEnumerable.Range
				(0, _settings.PopulationSize / 2)
                        from child in CreateChildren(
                            FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),
                            FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
                        select child).
                        ToArray();
            }
            else
            {
                return (from i in Enumerable.Range(0, _settings.PopulationSize / 2)
                        from child in CreateChildren(
                            FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),
                            FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
                        select child).
                        ToArray();
            }
        }

        private TextMatchGenome[] CreateChildren(
            TextMatchGenome parent1, TextMatchGenome parent2)
        {
            // Crossover parents to create two children
            TextMatchGenome child1, child2;
            if (_random.NextDouble() < _settings.CrossoverProbability)
            {
                Crossover(_random, parent1, parent2, out child1, out child2);
            }
            else
            {
                child1 = parent1;
                child2 = parent2;
            }

            // Potentially mutate one or both children
            if (_random.NextDouble() < _settings.MutationProbability) 
			Mutate(_random, ref child1);
            if (_random.NextDouble() < _settings.MutationProbability) 
			Mutate(_random, ref child2);

            // Return the young'ens
            return new[] { child1, child2 };
        }

        private TextMatchGenome FindRandomHighQualityParent
			(long sumOfMaxMinusFitness, int max)
        {
            long val = (long)(_random.NextDouble() * sumOfMaxMinusFitness);
            for (int i = 0; i < _currentPopulation.Length; i++)
            {
                int maxMinusFitness = max - _currentPopulation[i].Fitness;
                if (val < maxMinusFitness) return _currentPopulation[i];
                val -= maxMinusFitness;
            }
            throw new InvalidOperationException("Not to be, apparently.");
        }

        private void Crossover(Random rand, TextMatchGenome p1, 
	TextMatchGenome p2, out TextMatchGenome child1, out TextMatchGenome child2)
        {
            int crossoverPoint = rand.Next(1, p1.Text.Length);
            child1 = new TextMatchGenome { Text = p1.Text.Substring(0, crossoverPoint) + 
		p2.Text.Substring(crossoverPoint), TargetText = _targetText };
            child2 = new TextMatchGenome { Text = p2.Text.Substring(0, crossoverPoint) + 
		p1.Text.Substring(crossoverPoint), TargetText = _targetText };
        }

        private void Mutate(Random rand, ref TextMatchGenome genome)
        {
            var sb = new StringBuilder(genome.Text);
            sb[rand.Next(0, genome.Text.Length)] = _validChars[rand.Next
				(0, _validChars.Length)];
            genome.Text = sb.ToString();
        }
    }

    public struct TextMatchGenome
    {
        private string _targetText;
        private string _text;

        public string Text
        {
            get { return _text; }
            set
            {
                _text = value;
                RecomputeFitness();
            }
        }

        public string TargetText
        {
            get { return _targetText; }
            set
            {
                _targetText = value;
                RecomputeFitness();
            }
        }

        private void RecomputeFitness()
        {
            if (_text != null && _targetText != null)
            {
                int diffs = 0;
                for (int i = 0; i < _targetText.Length; i++)
                {
                    if (_targetText[i] != _text[i]) diffs++;
                }
                Fitness = diffs;
            }
            else Fitness = Int32.MaxValue;
        }

        public int Fitness { get; private set; }
    }

    public class GeneticAlgorithmSettings
    {
        public int PopulationSize
        {
            get { return _populationSize; }
            set
            {
                if (value < 1 ||
                    value % 2 != 0) 
			throw new ArgumentOutOfRangeException("PopulationSize");
                _populationSize = value;
            }
        }

        public double MutationProbability
        {
            get { return _mutationProbability; }
            set
            {
                if (value < 0 || value > 1) 
		throw new ArgumentOutOfRangeException("MutationProbability");
                _mutationProbability = value;
            }
        }

        public double CrossoverProbability
        {
            get { return _crossoverProbability; }
            set
            {
                if (value < 0 || value > 1) 
		throw new ArgumentOutOfRangeException("CrossoverProbability");
                _crossoverProbability = value;
            }
        }

        private int _populationSize = 30;
        private double _mutationProbability = .01;
        private double _crossoverProbability = .87;
    }
}

Those files are downloadable as a zip file. When you open the zip file, press Ctrl-A to select all of the files (or the initial folder) and then extract to a new folder in the Projects folder of the Visual Studio 2010 folder. Visual Studio 2010 is an easy download as an ISO file and is easy to burn to a DVD. Once the files are exposed, click the solution file, build the solution, and then choose “run without debugging”.

Now we run the application first in sequential mode (i.e., we don't check the parallel check box). Take care to note the number of generations per second, as well as the number of generations altogether:

And finally, we run this Windows Forms application with the parallel check box checked. Notice the difference in speed when generating random numbers and the effect of the text:

Notice the difference in time, generations, and generations per second. And in the simplest sense, all that we did was find regions of code that could run in parallel, executing code (tasks) on separate virtual CPUs (or cores). There is also a performance improvement without a waste of memory resources.

References

• The MSDN Parallel Computing Center

History

• 16^th April, 2010: Initial post