Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles
Print
(untagged)

Windows Forms, Random Number Generators, and Parallel Programming

0.00/5 (No votes)
16 Apr 2010 1  
An article that demonstrates building a Windows Forms application via Parallel computing

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#.

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:

Plain Text
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.

C#
 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:

Plain Text
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:

C#
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:

C#
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”.

1.JPG

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:

2.JPG

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:

3.JPG

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

  • 16th April, 2010: Initial post

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here