Intro

Lastly, I have decided to create a new library for .NET core that handles (big) prime numbers. You know - testing, generating and other stuff that could be useful for playing with big numbers.

It is obvious that to accomplish this, I needed a service that should generate a bunch of random values. Easy task? Yep!

Random provider

The only method I need is to generate random bytes that are placed in a buffer - our numbers could much more beyond int/long range, so I have decided to represent numbers as the byte array (like BigInteger it does).

public sealed class SimpleRandomProvider : IRandomProvider
{
    private static readonly Lazy<Random> RandomHolder = new Lazy<Random>(() => new Random());

    public void NextBytes(byte[] buffer)
    {
        RandomHolder.Value.NextBytes(buffer);
    }
}

Usage & Testing

Random provider is used to generate random big integer below a specified range, fe.

See snippet below:

public class BigIntegerGenerator
{
    public Task<BigInteger> GenerateNonZeroAsync(BigInteger maxExclusive)
    {
        var rndProvider = new SimpleRandomProvider(); 
        var buffer = maxExclusive.ToByteArray();
   
       if (maxExclusive < int.MaxValue) {
           //special case, not relevant
           //generate simple int etc
           return;
       }

        return Task.Run(() => {
            
            BigInteger result;

            do {
                rndProvider.NextBytes(buffer);
                bytes[bytes.Length - 1] &= 0x7F; //ensure positive
                result = new BigInteger(bytes);
            } while (result >= maxExclusive || result == 0);

            return result;
        });
    } 
}

Like a model programmer, I wrote some unit tests ran by xUnit:

Disclaimer: Tests are simple as possible to simplify the case.

public  class SampleTest
{
    public async Task SomeTestMethodNo1()
    {
        var generator = new BigIntegerGenerator();
        var someVeryBigNumber = BigInteger.Parse("20988936657440586486151264256610222593863921");
        var generated = await generator.GenerateNonZeroAsync(someVeryBigNumber);

        Assert.True(generated < someVeryBigNumber); 
    }

    public async Task SomeTestMethodNo2()
    {
        var generator = new BigIntegerGenerator();
        var someVeryBigNumber = BigInteger.Parse("209889366574405864861512642566102256456456456863921");
        var generated = await generator.GenerateNonZeroAsync(someVeryBigNumber);

        Assert.True(generated < someVeryBigNumber); 
    }
}

Trap

I have ran my tests and… Testing has never ever finished. Or even failed. Just like an endless loop.

What went wrong

I have spent couple hours to find out the cause of this weird behavior (my tests % snippets are much more complicated). Indeed, the problem was an endless loop… here:

do {
    rndProvider.NextBytes(buffer);
    bytes[bytes.Length - 1] &= 0x7F; //ensure positive
    result = nwe BigInteger(bytes);
} while (result >= maxExclusive || result == 0);

Yeep! It turned out, that xUnit runs tests in separate threads. What’s more, Random.NextBytes is not threadsafe, so… it started to fill bytes with 0 when more than one thread accessed it at the same time.

Solution

Very simple:

public sealed class SimpleRandomProvider : IRandomProvider
{
    [ThreadStatic] private static Random _random;

    private static Random RandomInstance
    {
        get
        {
            if (_random == null) _random = new Random();

            return _random;
        }
    }
    
    public void NextBytes(byte[] buffer)
    {
        RandomInstance.NextBytes(buffer);
    }
}

We could alse use ThreadLocal:

public sealed class SimpleRandomProvider : IRandomProvider
{
    private static readonly ThreadLocal<Random> Random = new ThreadLocal<Random>(() => new Random());

    public void NextBytes(byte[] buffer)
    {
        Random.Value.NextBytes(buffer);
    }
}

Patryk Wąsiewicz

A very casual blog about programmer's life.