Random BigInteger

[boops boops]

I couldn't resist having a go at this myself, and I think I have a solution. It works as far as I can see for any any minimum and maximum, including those stated by the OP, and (so it seems) including negatives. I didn't plan for the negatives, but they just seem to work.

My method is similar to those so far, building an array of random bytes of the same length as BigInteger.ToByteArray. What I do that is different is to zeroise any bits in the most significant byte of the random output which correspond to leading zeros in the most significant byte of the test maximum. That way the random value has the same bit length (not just byte length) as the maximum, greatly reducing the probability that the value will exceed the maximum. This does not affect the randomness of the remaining bits. There is no need to worry about a zero sign byte at the most signficant end since it simply remains unaltered; and there cannot be any leading zeros in the next most significant byte.

As a result, only one pass of the loop is often needed, depending on the chosen maximum and minimum. The OP's limits seem to need only one pass, and the same is true for a range from Long.MinValue (inclusive) to Long.MaxValue (exclusive). Sometimes the average number of loops per biginteger is slightly more than one, showing that the loop is actually needed. In one test, with a range from 0 to &H899999, an average of 1.86 loops were needed. The performance seems satisfactory: with the OP's minimum and maximum, I get an average of 0.12 milliseconds per generated biginteger on a fairly humdrum twincore. Smaller limits are obviously much faster.

Here's the code of the function:

Private Function RandomBigInteger(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!")
 
        Dim biResult As BigInteger
        Dim diffBytes() As Byte = biDiff.ToByteArray
        Dim count As Integer = diffBytes.Count
        Dim resultBytes(count - 1) As Byte
 
        Do
            'Get a random byte array of the same length as the diffBytes:
            _random.NextBytes(resultBytes)
 
            'zeroise bits in the most significant byte which are leading zeros in diffBytes:
            For i As Integer = 7 To 0 Step -1
                Dim bitmask = 1 << i
                If (diffBytes.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
 
            biResult = New BigInteger(resultBytes)
            _loopCount += 1
 
        Loop Until biResult < biDiff
 
        Return biResult + minimum
    End Function

Here's a test sub I have been using.

Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        _loopCount = 0
        Dim minimum As BigInteger
        Dim maximum As BigInteger
        Dim errors As Integer
        Dim positives As Integer
        Dim negatives As Integer
        Dim total As BigInteger
        Dim average As BigInteger
 
        'OP's test limits:
        Dim a As BigInteger = 2 ^ 31 - 1
        minimum = BigInteger.Pow(a, 33)
        Dim b As Integer = CInt(2 ^ 15)
        maximum = BigInteger.Pow(2, b)
        
        'alternative test limits:
        minimum = Long.MinValue
        maximum = Long.MaxValue
        'minimum = 0
        'maximum = &H899999
 
        Dim iterations As Integer = 999999
 
        Dim sw As Stopwatch = Stopwatch.StartNew
        For i As Integer = 0 To iterations - 1
            Dim bi As BigInteger = RandomBigInteger(minimum, maximum)
            'Console.WriteLine(bi.ToString) '(Comment this line out when performance testing.)
            If bi < minimum OrElse bi >= maximum Then
                Console.WriteLine("Error: " & bi.ToString)
                errors += 1
            Else
                total += bi
            End If
            If bi >= 0 Then positives += 1 Else negatives += 1
 
        Next
        Console.WriteLine("Loop count per biginteger : " & (_loopCount / iterations).ToString())
        Console.WriteLine((1000 * sw.ElapsedTicks / Stopwatch.Frequency / iterations).ToString("N3") _
           & " average milliseconds per random biginteger")
        Console.WriteLine("Out-of-range errors : " & errors)
        Console.WriteLine("Positives : " & positives)
        Console.WriteLine("Negatives : " & negatives)
        average = BigInteger.Divide(total, iterations - errors)
        Console.WriteLine("Average: " & average.ToString)
        Console.WriteLine("Average as % of maximum: " & (CDec(average) / CDec(maximum)).ToString("P2"))
    End Sub

BB

EDIT: I added some more feedback to the test sub. In particular, there are now some simple tests for skewing. With a symmetrical range (e.g. Long.MinValue to Long.MaxValue) the number of positive results should be close to the number of negatives. With a minimum=0 and a large number of iterations, the average output should be close to 50% of the maximum; this test is limited to Decimal ranges because I haven't thought out how to do a fractional divide of bigintegers.