Printable View
Are there? Accepted by whom? No mathematician would commit to the accuracy or usefulness of such a test, especially given that the main problem with pseudo random is that it's too random (for want of a better expression)! Flip a coin enough times and a sequence of 10 consecutive heads is a near certainty but you can keep a pseudo random selector going to the crack of doom and never come close to it.Quote:
Originally Posted by dbasnett
What you are doing is the equivalent of what I mentioned in my previous post (ie. using random(0, high_oreder_byte -1) as new highorderbyte). And while I agree with your statement in principle, I found that the statistical data I got, wasn't uniformly distributed among all values within the range. But maybe I was too quick to discard the method - I will have a little look at your version of it in a little while, try some loops over it, and see if you can convince me :)Quote:
Originally Posted by boops boops
#EDIT: Wrote an initial edit here, that I deleted due to it being false! After more testing, I have found out why I discarded the method in the first place. Using a random between 0 and the high-order-byte is NOT the same as the bitmask used by BB (and after seeing my data I banged my head into the wall for even thinking it). BB has it completely right, and I was completely wrong!
I hope that you are wrong for Dr. Knuth's sake.Quote:
Originally Posted by dunfiddlin
I tried BB's method with min = 1, max = 7 and it showed great distribution over 100,000 tries. I have already up voted her, and wish I could again.Quote:
Originally Posted by ThomasJohnsen
Thank you for your kind words. But Boops boops <> Betty Boop. For my true profile, see here.Quote:
Originally Posted by dbasnett
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:cool:). 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:Quote:
Originally Posted by boops boops
To test, I used:vb.net Code:
Unless I screwed something up (again), you have succeded in making a non-looping truly random bigint generator :)Code: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))
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
Once again you're right - I should've never written a word in this thread :)Quote:
Originally Posted by boops boops
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).
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.
@dbasnett: The size of the array depends only on the maximum. The minimum has nothing to do with it.
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).Code:Dim maxBytes() As Byte = maximum.ToByteArray
Dim count As Integer = maxBytes.Count
Dim resultBytes(count - 1) As Byte
@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:
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.Code: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)
BB
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 :)Quote:
Originally Posted by boops boops
#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.
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.Quote:
Originally Posted by boops boops
So I made the following modifications to the test routine using the OP's original numbers and BB's function. The minimum number has a length of 308 characters, and the maximum has a length of 9865 characters.
Code:Dim bi As BigInteger
Dim i As Integer
Dim chCt As Long = 0
For i = 1 To iterations
bi = RandomBigInteger(minimum, maximum)
If bi < minimum OrElse bi >= maximum Then
Debug.WriteLine("Error: " & bi.ToString)
errors += 1
Else
Dim s As String = bi.ToString.TrimStart(New Char() {"0"c})
chCt += s.Length
End If
Next
Debug.WriteLine(chCt / (i - 1))
sw.Stop()
The average in the tests I ran was 9864+. When I ran the same test with my class the average was 5000+.
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.Quote:
Originally Posted by dbasnett
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:D. BB
BB
Did you try the test code I posted? The results I found seemed to indicate that your method is skewed to the high end of the range, which is what I suspected. Maybe it is an error with how I tested.Quote:
Originally Posted by boops boops
When I saw that your method used the larger size only I suspected this would be the result. Since there was only a 1 in 256 chance that the high order byte would be 0, as well as any other, it seemed logical that this would be the result.
No it should be high. What you're failing to take into account is that there are 10 times as many 9865 digit numbers as there are 9864 digit numbers, 100 times as many as as 9863 digit numbers, 1000 times as many as 9862 digit numbers and so on.
Think about it from the other end. In the numbers 0-99 there are just 10 single digit numbers. The average length is therefore marginally less then 2. In 0 - 999 there are 10 single digit numbers, 90 double digits and 900 triple digits. The average length is therefore marginally less than 3. This pattern continues at all scales, so with 9865 digits the average length is marginally less than 9865. This will be reduced somewhat by the minimum number but it is still only a marginal effect over the range.
I didn't try your test code because I don't think it is useful and in my view you are misinterpreting its results. I checked my function for skewing by dividing the range of actual output values into eight equal segments from minimum to maximum (minimum to minimum + one-eight of the maximum, minimum+one-eighth of maximum to minimum+one-quarter etc.). The results were flat across all eight segments. Here's the test code I used:Quote:
Originally Posted by dbasnett
The output was:Code:Dim rangeSegment(7) As Integer
iterations = 10000000
minimum = 0
maximum = Long.MaxValue
Dim range = maximum - minimum
For i As Integer = 0 To iterations - 1
Dim bi As BigInteger = RandomBigInteger(minimum, maximum)
Select Case (bi - minimum)
Case Is < range / 8
rangeSegment(0) += 1
Case Is < range * 2 / 8
rangeSegment(1) += 1
Case Is < range * 3 / 8
rangeSegment(2) += 1
Case Is < range * 4 / 8
rangeSegment(3) += 1
Case Is < range * 5 / 8
rangeSegment(4) += 1
Case Is < range * 6 / 8
rangeSegment(5) += 1
Case Is < range * 7 / 8
rangeSegment(6) += 1
Case Else
rangeSegment(7) += 1
End Select
Next
For i As Integer = 0 To rangeSegment.Count - 1
Console.Write("Segment " & i & ": " & rangeSegment(i) & " ; ")
Next
As you can see, the output for each segment from minimum to maximum varies by no more than 0.3 percent. To me this indicates that the output of the method is not skewed. If there are any output values with more than three leading zero bits, they will be included in the first segment.Code:Segment 0: 1249396 ; Segment 1: 1251108 ; Segment 2: 1251514 ; Segment 3: 1251063 ; Segment 4: 1249567 ; Segment 5: 1249511 ; Segment 6: 1249467 ; Segment 7: 1248374
BB
I stand corrected. Both of your points make sense. I must have fallen into the stupid pit, I certainly can't claim ignorance.
I did take BB's approach and make some changes that allow it to generate the next random big integer in the background. This is only faster if you are continually getting numbers between a fixed range, and isn't all that much faster even then.
I used this to testCode:Class RandomBI
Shared _PRNG As New Random
Private minimum As BigInteger = 0
Private maximum As BigInteger = 1
Private newBI(0) As Byte 'next random number
Private nextOne As BigInteger
Private HOMask As Byte 'high order mask
Private thrd As Threading.Thread
Private doCalc As New Threading.AutoResetEvent(False)
Private waitAnswer As New Threading.AutoResetEvent(False)
Public Sub New()
If IsNothing(Me.thrd) Then
Me.thrd = New Threading.Thread(AddressOf Me.NextBIbkg)
Me.thrd.IsBackground = True
Me.thrd.Start()
End If
Me.doCalc.Set()
End Sub
Public Function NextBI(min As BigInteger, max As BigInteger) As BigInteger
If min >= max Then Throw New OverflowException
If min <> Me.minimum OrElse max <> Me.maximum Then
Me.newBI = (max - min).ToByteArray 'set the array size
Me.minimum = min
Me.maximum = max
Me.HOMask = 255 'all ones
Dim mask As Byte
For m As Integer = 7 To 0 Step -1 'create mask for high order bits in high order byte
mask = CByte(1 << m)
If (Me.newBI(Me.newBI.Length - 1) And mask) = mask Then
Exit For
Else
Me.HOMask = Me.HOMask Xor mask
End If
Next
Me.waitAnswer.Reset() 'invalidate current answer if one
Me.doCalc.Set() 'tell bkg to go
End If
Me.waitAnswer.WaitOne() 'wait for answer
Dim bi As BigInteger = Me.nextOne 'get the answer
Me.doCalc.Set() 'tell bkg to compute next one
Return bi
End Function
Private Sub NextBIbkg()
Do
Me.doCalc.WaitOne() 'wait for go
Do
_PRNG.NextBytes(Me.newBI)
Me.newBI(Me.newBI.Length - 1) = Me.newBI(Me.newBI.Length - 1) And Me.HOMask
Me.nextOne = New BigInteger(Me.newBI) + Me.minimum
Loop While Me.nextOne < Me.minimum OrElse Me.nextOne >= Me.maximum
Me.waitAnswer.Set() 'new number calculated
Loop
End Sub
End Class
Code:Dim bar As New RandomBI
Private Sub Button2_Click(sender As System.Object, e As System.EventArgs) Handles Button2.Click
Dim minimum As BigInteger
Dim maximum As BigInteger
Dim errors As Integer
Dim a As BigInteger = 2 ^ 31 - 1
minimum = BigInteger.Pow(a, 33)
Dim b As Integer = CInt(2 ^ 15)
maximum = BigInteger.Pow(2, b)
'
Dim half As BigInteger = ((maximum - minimum) / 2) + minimum
'
Dim lh As Integer = 0 'lower half
Dim uh As Integer = 0 'upper half
Dim bi As BigInteger
Dim i As Integer
Dim sw As Stopwatch = Stopwatch.StartNew
Debug.WriteLine("")
Dim iterations As Integer = 10000
For i = 1 To iterations
'bi = bar.NextBI(minimum, maximum)
bi = RandomBigInteger(minimum, maximum)
If bi < minimum OrElse bi >= maximum Then
Debug.WriteLine("Error: " & bi.ToString)
errors += 1
Else
'which half?
If bi < half Then lh += 1 Else uh += 1
End If
Next
sw.Stop()
Debug.WriteLine(sw.ElapsedMilliseconds / (i - 1))
End Sub
This thread is great, eye bleeding, entertaining reading. keep it up :D