Random BigInteger

[ThomasJohnsen]

Thank you for your kind words. But Boops boops <> Betty Boop. For my true profile, see here.

My thinking for the method was as follows. Setting a number of bits at random produces a random number; the randomness is as good as the random number generator used to set the bits, or a function of it at least. Random.NextBytes provides a method of setting the bits at random in convenient batches of 8, but doesn't introduce any non-randomness apart from the total number of bits.

I wondered whether knocking out the high order bits might affect the randomness, and I reasoned as follows. Suppose you want a random number in the range 1 to 4, and you have a normal 6-faced die (singular of dice). When you throw the die, each number has a one sixth chance of occurring. What happens if you just ignore throws of 5 or 6 to get the required random throw? The chances of 1, 2, 3 and 4 are still equal (one sixth). So excluding certain numbers from a set of random values does not necessarily change the randomness of those that remain. Zeroizing the high end bits does nothing except reduce the range of values.

BB

I seperated your function into 2 functions (like in Matt's example) to get rid of the looping (which was the running debate at the time), and this seems to perform a tad faster on the few examples I tried:

Private Function RandomBigInteger_Max(maximum As BigInteger) As BigInteger
        If maximum <= 0 Then Throw New Exception("Maximum must be positive!")
 
        Dim maxBytes() As Byte = maximum.ToByteArray
        Dim count As Integer = maxBytes.Count
        Dim resultBytes(count - 1) As Byte
 
        'Get a random byte array of the same length as the maxBytes:
        _random.NextBytes(resultBytes)
 
        'zeroise bits in the most significant byte which are leading zeros in maxBytes:
        For i As Integer = 7 To 0 Step -1
            Dim bitmask = 1 << i
            If (maxBytes.Last And bitmask) = bitmask Then
                'If the tested bit is 1, there are no more leading zeros:
                Exit For
            Else
                'Zeroize the tested byte:
                resultBytes(count - 1) = CByte(resultBytes.Last And (Not bitmask))
            End If
        Next
 
        Return New BigInteger(resultBytes)
    End Function
    Private Function RandomBigInteger_Gen(minimum As BigInteger, maximum As BigInteger) As BigInteger
 
        Dim biDiff As BigInteger = maximum - minimum
        If biDiff < 0 Then Throw New Exception("Maximum must be more than minimum!")
 
        Return BigInteger.Add(RandomBigInteger_Max(biDiff), minimum)
 
    End Function

To test, I used:

        bimin = New BigInteger(75426795804)
        bimax = New BigInteger(479207684327642)

        Dim s As New Stopwatch

        s.Start()
        For i = 1 To 10000000
            RandomBigInteger(bimin, bimax)
        Next
        s.Stop()

        TextBox1.AppendText(String.Format("Time for BB algo: {0}{1}", s.ElapsedMilliseconds, Environment.NewLine))

        s.Reset()
        s.Start()
        For i = 1 To 10000000
            RandomBigInteger_Gen(bimin, bimax)
        Next
        s.Stop()

        TextBox1.AppendText(String.Format("Time for Gen algo: {0}{1}", s.ElapsedMilliseconds, Environment.NewLine))

Unless I screwed something up (again), you have succeded in making a non-looping truly random bigint generator