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

[boops boops]

Thomas, this version ensures that the random number (resultBytes) has the right number of bits but it doesn't compare the result to the maximum. You still have to do that. Suppose the high end byte of the maximum happens to be 00001000. You can't be sure if the generated random number won't have 00001001 in that byte -- or anything up to 00001111. In fact, even the least significant bit of the whole number could result in exceeding the maximum. As far as I can see, there is no option but to compare against the maximum in a loop because you can't know in advance whether each new random number will exceed the maximum. The exception is when the maximum happens to have solid 1s all the way, i.e its value is of the form 2^n - 1.

Still, I feel a bit uneasy. I don't understand why on average so few passes of the loop were needed in my testing with various maximum values.

BB

[ThomasJohnsen]

Thomas, this version ensures that the random number (resultBytes) has the right number of bits but it doesn't compare the result to the maximum. You still have to do that. Suppose the high end byte of the maximum happens to be 00001000. You can't be sure if the generated random number won't have 00001001 in that byte -- or anything up to 00001111. In fact, even the least significant bit of the whole number could result in exceeding the maximum. As far as I can see, there is no option but to compare against the maximum in a loop because you can't know in advance whether each new random number will exceed the maximum. The exception is when the maximum happens to have solid 1s all the way, i.e its value is of the form 2^n - 1.

Once again you're right - I should've never written a word in this thread

Though I do not regret doing so - this is an interesting problem, and I cannot quite get my head around why that loop is neccessary. In my mind, it must be possible to generate a random number between a min and max with uniform distribution within a predetermined amount of time (ie. only depending on the length of the numbers), as long as you are able to generate uniformly distributed random bytes. I think I will pull this problem out once in a while hoping for a Heureka moment, until someone posts a solution (or proves that generating one is impossible without a loop).

[dbasnett]

Using the OP's original numbers, I have a gut feeling that I have a problem with BB's solution, though I have no way to prove it. In BB's solution the array representing the new number is always 4097 bytes, though the minimum only uses 129 bytes. My gut keeps telling me that this will skew the results.

[boops boops]

@dbasnett: The size of the array depends only on the maximum. The minimum has nothing to do with it.

 Dim maxBytes() As Byte = maximum.ToByteArray
 Dim count As Integer = maxBytes.Count
 Dim resultBytes(count - 1) As Byte

The array doesn't get ReDimmed anywhere so it stays the same size. That doesn't mean the value filled in by Random.NextBytes has to be that big. There will often be some leading zeroes. There is a 50% chance of 1 leading zero, a 25% chance of 2 leading zeros and so on. Any leading zeroes in the randomized array will be ignored by the constructor New BigInteger(byte array).

@Thomas: I'm not sure why you want to avoid using a loop. I don't think efficiency can be the reason because in practice the number of loops is low. I tested the average number of loops needed for my random bigintegers function. Each call had a random maximum. The average loops per call was consistently 1.385-1.386 measured over 1 million calls of the randomizer.

Here's the code I used for the test:

Dim loopTotal As Integer = 0
		For i As Integer = 0 To 999999
			_loopCount = 0 '_loopCount is updated in the RandomBiginteger function.
			maximum = _random.Next
			minimum = 0
			Dim bi As BigInteger = RandomBigInteger(minimum, maximum)
			loopTotal += _loopCount
		Next
		Console.WriteLine("Averge loops per biginteger (random maximum): " & loopTotal / 1000000)

I still need to take a closer look at the negative maximum and minimum. I suspect that some code changes will be needed to deal with a non-symmetrical range.

BB

[ThomasJohnsen]

@Thomas: I'm not sure why you want to avoid using a loop.

Simply because I find it to be ugly. The fact that this problem, in my eyes requiring only inner loops, seems to be difficult if not impossible to write without an outer loop, offends me. I'm a fan of odd, elegant and untraditional solutions, that may lead to simpler, faster and/or more general code (bit twiddling hacks and similar), and I feel that you are so close with your solution. Even 1.38 loops per call is .38 too many in my eyes - but then again; I'm an odd sort of fellow and I haven't done this for a living for 20+ years. Maybe if I had to churn out x amount of lines every day, problems like these wouldn't need to be revisited

#EDIT: After having tried expanding the bitfield solution (ie. BB's version of comparing bits in max vs. rnd so 00 -> 00, 01 -> 00, 10 -> exit, 11 -> 11) to the entire array until it could be determined that max > rnd, I have come to the conclusion, that the loop (ugly as I find it) is indeed the best solution. The rnd byte-array will be equal to the max byte-array after the bit-removal has been completed in 100% / (2 ^ number_of_bits_in(max)) of the cases, meaning that the fewer bits there is in max, the more likely it is, that the bit-removal process has to traverse the entire byte-array. Thus forcing another generation of a random byte-array (ie. in the cases where rnd = max after bit-removal).
Trying to sift out bits in the random byte-array to ensure that it is allways smaller than max without ever having to generate a new array and not influencing the distribution of random values, has proved to be impossible for me. Hopefully someone will come along with a solution without a loop at some point; until then, I'm satisfied, that the BB-solution is the best one available.

[dbasnett]

@dbasnett: The size of the array depends only on the maximum. The minimum has nothing to do with it.
... That doesn't mean the value filled in by Random.NextBytes has to be that big. There will often be some leading zeroes. There is a 50% chance of 1 leading zero, a 25% chance of 2 leading zeros and so on. Any leading zeroes in the randomized array will be ignored by the constructor New BigInteger(byte array).

That is my concern, that the minimum has nothing to do with it. If the minimum number can be represented with 129 bytes, but you always use an array of 4097 then to get near the minimum you will have to generate approximately 3900 leading zeros in a row. As I said, I have no data to back up my concerns, just a gut feel.

[boops boops]

That is my concern, that the minimum has nothing to do with it. If the minimum number can be represented with 129 bytes, but you always use an array of 4097 then to get near the minimum you will have to generate approximately 3900 leading zeros in a row. As I said, I have no data to back up my concerns, just a gut feel.

I don't know why you are concerned about the number of leading zeroes. A random number should average half way in value between the minimum and the maximum. For example, random numbers from 1 to 1000 should average 500, not 50. Shorter numbers are increasingly rare: in the range 1 to 1000 there are only 49 numbers less than 50 but 950 above it.

In binary terms, the average value of random binary numbers from 0 to 1nnn.... should be 01nnn...., not something with a lot of leading zeroes. The chance of any given number cropping up in a 4097-byte random array is once in 2^(4097*8). The chance of a randomized byte array having 3900 zero bytes in a row is once in 2^(3900*8). I bet you would wear out dunfiddlin's Cray trying to find even one of those. BB

BB