Hi, I was wondering if there's any way to randomly select a BigInteger within a certain range on Visual Basic 2010 (in my case, it's between (2 ^ 31 - 1) ^ 33 and 2 ^ (2 ^ 15)).
Printable View
Hi, I was wondering if there's any way to randomly select a BigInteger within a certain range on Visual Basic 2010 (in my case, it's between (2 ^ 31 - 1) ^ 33 and 2 ^ (2 ^ 15)).
You can create a BigInteger by passing an array of Bytes to the constructor. You could work out what Bytes represent the limits of your range and then use a Random object to generate the appropriate number of random Bytes. Note that some of the Bytes generated will be able to span the entire 2 - 255 range while others may not, so you may have to use limits on the Next method to control that.
Actually, now that I think about it that would probably not really work because the likelihood of getting a low number would be very small because you'd be unlikely to get all zeroes for the higher-order Bytes. What you probably ought to do is to use Random.NextDouble and then scale that value using the length of your range to select a value within it.
Is there a way to randomly choose one of over 10^9500 integers using a single command on a home computer? What do you think?
You can get a Cray for $200k these days. Maybe you should start saving up?
He could determine the number of bytes used to generate both bigints and them generate a random number between the 2 (both inclusive). Then all he had to do was to generate random doubles and use bitconverter on them until he had bytes equal to or larger than the number generated first. A bigint constructor would then be used on the resulting byte array.Quote:
Originally Posted by jmcilhinney
As far as I can tell, that would generate all numbers equally likely (but I haven't done the math - it's just a general assessment)
#EDIT: Dooh - why not just use Random.NextBytes? That would seem like the way to go here.
That would still exclude more numbers than it included as there would need to be a massive upscaling which (as we know all too well from image scaling) simply increases the gaps between possible values. Mathematics on this scale is just something for which the PC, even with BIgInteger, is simply not designed.Quote:
Originally Posted by jmcilhinney
Because, as I said earlier, that range would likely lead to some Bytes that must be zero, some that could be anywhere in the range 0 - 255 and some that could only be some part of that range.Quote:
Originally Posted by ThomasJohnsen
Yeah, you're right about the gaps. It might be possible to use an iterative approach, where a Double was used to determine a range and then another random value was generated within that range so on until there were no more gaps between scaled values. Pretty messy though.Quote:
Originally Posted by dunfiddlin
I'm not sure that that is right. Suppose you were to get a random ULong. To get any given single digit number (0-9) would be roughly one in a bajillion, but not because the odds of getting all 0s in the upper 7 bytes plus a nibble were low. If you got a number that low, then all those upper bits would have to be 0, which is highly improbable, but not more improbable that drawing the number 0-9 from the range of 0 - 2^64. Those numbers are very improbable simply because ANY given number is very improbable once the range is very large.Quote:
Originally Posted by jmcilhinney
For the reason that jmc gave earlier. Not all bytes are equal. The chances of getting a string of zeroes in the high valued bytes (say 1-100 in the sequence) is microscopic compared to the probability of it occurring naturally in a true random choice and given that we're talking a range of over 9800 bytes it's going to be massive skewing toward the higher values.Quote:
why not just use Random.NextBytes? That would seem like the way to go here.
Even when I was posting that I was thinking "is that right" but it's 4 AM here and I can't really think too hard on anything. I should be in bed but I thought I'd stay up and play with my shiny new Office 2013 to see what's new.Quote:
Originally Posted by Shaggy Hiker
You are a notable insomniac. However, evaluating new software on a lack of sleep is always risky: No, the pink elephant icons are NOT part of the feature set.
Oh pooh! You're right, of course (I've just done the math!). Typical. The one time I agree with jmc and he's wrong!Quote:
Originally Posted by Shaggy Hiker
Is the OP asking for numbers between 8.9884656743115795386465259539451e+307 and 1.415461031044954789001553027745e+9864?
And by extension, the only time I've been wrong, obviously. ;)Quote:
Originally Posted by dunfiddlin
Ok, I'm getting around .13 secs to fill a 9850 byte array and convert it to a BigInteger so I suppose it's just about practical if you don't overdo it. Of course that doesn't take any account of the need to adjust for ranges such as the one proposed.
Indeed! Makes the lottery look like a coin toss!Quote:
Originally Posted by dbasnett
Why 9850? IF the upper range is 2^32768 it won't take 9850 bytes.
The minimum number fits in a byte array of 129 bytes and the maximum fits into an array of 4097, if I have done my math correctly. So if we create an array of random length between those values, and then set each bit randomly, is it random?
Code:Imports System.Numerics
Public Class Form1
Dim _prng As New Random
Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
For x As Integer = 1 To 100
Debug.WriteLine("")
Debug.WriteLine(x)
amThisRandomQ()
Next
End Sub
Private Sub amThisRandomQ()
Dim minBI As New BigInteger(8.98846567431158E+307)
Dim maxBI As New BigInteger(2)
maxBI = BigInteger.Pow(maxBI, 32768)
'Debug.WriteLine(minBI.ToByteArray.Length)
'Debug.WriteLine(maxBI.ToByteArray.Length)
Dim foo As New BigInteger
Dim stpw As New Stopwatch
Do
'129 bytes to 4097
Dim n() As Byte = New Byte(_prng.Next(129, 4098)) {}
stpw.Reset()
stpw.Start()
'what if _prng.NextBytes(n) see *** near end of for loop
For y As Integer = 0 To n.Length - 1
Dim nb As Byte = CByte(_prng.Next(0, 2))
For x As Integer = 1 To 7
nb = nb Or CByte(_prng.Next(0, 2) << x)
Next
'*** what if n(y) = n(y) Xor nb instead of n(y) = nb
n(y) = nb
Next
stpw.Stop()
foo = BigInteger.Abs(New BigInteger(n))
Loop Until foo >= minBI AndAlso foo <= maxBI
Debug.WriteLine(stpw.Elapsed.ToString)
Debug.WriteLine(foo.ToString)
End Sub
End Class
It should be.
Would you feel bad about creating an F# library and using that in your code?
Code:namespace RandomBigInt
type FsBigInteger() =
static let internalRandom = new System.Random()
/// Returns a BigInteger random number of the specified number of bytes.
static member Random(numBytes:int, rand:System.Random) =
let r = if rand=null then internalRandom else rand
let bytes : byte[] = Array.zeroCreate (numBytes+1)
r.NextBytes(bytes)
bytes.[numBytes] <- 0uy
bigint bytes
/// Returns a BigInteger random number from 0 (inclusive) to max (exclusive).
static member Random(max:bigint, rand:System.Random) =
let rec getNumBytesInRange num bytes = if max < num then bytes else getNumBytesInRange (num * 256I) bytes+1
let bytesNeeded = getNumBytesInRange 256I 1
FsBigInteger.Random(bytesNeeded, rand) % max
/// Returns a BigInteger random number from min (inclusive) to max (exclusive).
static member Random(min:bigint, max:bigint) =
FsBigInteger.Random(max - min, internalRandom) + min
/// Returns a BigInteger random number from min (inclusive) to max (exclusive).
static member Random(min:bigint, max:bigint, rand:System.Random) =
FsBigInteger.Random(max - min, rand) + min
vb.net Code:
As far as I can tell (from a quick glance never having delved into F#) this is similar to the naive approach, like for instance:Quote:
Originally Posted by MattP
vb.net Code:
It has the problem of not being able to generate all bigintegers with even likelyhood, since the highest order byte is generated non-inclusive (ie. generating random number in range 0 to 1000 will generate number in the range 0 to 767 with even likelyhood and never integers larger than 767). Adding one (ie. making the high-order byte inclusive) will ofc generate integers in the range 0 to 1024 with even likelyhood when asked for integers in range 0 to 1000.
But F# may be a solution - like I said I cannot really determine if your code accounts for that or not, since I have no experience using F#.
Tom
#EDIT: I tried a naive fix (on my naive sub) and replaced 'vBuffer(i) = Convert.ToByte(rnd.Next(vMaxBytes(i)))' (exclusive) with:
and it still dosen't generate numbers with equal randomness. The fewer combinations available with a randomly selected high-order byte equal to the initial high-order byte, makes my 'random' function favor those slightly. This effect could be reduced by randomizing over multiple high-order bytes, but McIlhinney was right in his initial assumption, that generating a random-function for big integers isn't trivial (unless ofc. Matt's solution works, in which case the problem has already been solved).vb.net Code:
The problem I see is testing the randomness because of the size of the numbers. Maybe Knuth's TAOCP will shed some light on this.Quote:
Originally Posted by Shaggy Hiker
@ThomasJohnsen - You said "...and it still dosen't generate numbers with equal randomness." How are you checking?
With a range that big, checking exhaustively should be pretty nearly impossible.
I wasn't talking about your code or Matt's code, but my own sad version. Generating alot of random numbers within a small range made it clear really quickly, that my algorithm is flawed. I tried a couple of different versions of it, but every one was flawed. The problem lies in the highest byte. To illustrate consider standard base-10 notation and let us assume WLOG, that we are able to generate true random numbers in the range 0-9 (one such random digit denoted {R}), and also in any range 0 - x, x in {1, ..., 9} denoted {x}.Quote:
Originally Posted by dbasnett
If we define Random(1000) = {R}{R}{R}, we would get equally distributed random numbers between 0 and 999 each equally likely.
But consider Random(44)
Defining it as Random(44) = {4}{4} will clearly lead to gaps (ie. never produce 38 for instance).
Thus we might choose to define it as:
Let a = {4}
If a = 4 then (*) Random(44) = a{4} else (**) Random(44) = a{9}
Each of a in {0, 1, 2, 3, 4} will be equally likely meaning that (*) a{4} will be chosen in 20% of the traverses leading to a 4% chance of Random(44) generating each of {40, 41, 42, 43, 44}. But (**) a{9} will be chosen in 80% of the traverses leading to a 2% chance of Random(44) generating each of {0, 1, ..., 39}, thus making numbers with high-order digit of 4 twice as likely to be generated.
I tried various variations relying on mod and similar, but wasn't able to create code for a version with a uniform probability for each number within the range.
#EDIT: Your bit version should exhibit the same problems as my byte version or the example base-10 version. The highest order bit/byte/digit will be generated equally likely as the other bits/bytes/digits but have a smaller range of outcomes, thus leading to a higher chance of those outcomes (though with extremely large numbers and a large base of maybe 64 bits, the difference may not be all that noticeable).
#EDIT2: The best version, I was able to come up with (and it seems to generate true random numbers - an induction proof based on the number of digits in a base B appears to be at least semi-doable (the fact that (1/dn)^i converges to zero for i increasing is key)), is rather ugly:
or in words:vb.net Code:
Random(dn...d2d1d0) on a number in base B with digits di in {0, 1, ..., B-1} and WLOG dn > 0, is defined by
Code:While True
ai = Random(B) for i < n
an = Random(dn + 1)
If an...a2a1a0 < dn...d2d1d0 Then Return an...a2a1a0
End While
"Your bit version should exhibit the same problems as my byte version or the example base-10 version. The highest order bit/byte/digit will be generated equally likely as the other bits/bytes/digits but have a smaller range of outcomes, thus leading to a higher chance of those outcomes", may be true, but it doesn't look to be the case:
Code:Imports System.Numerics
Public Class Form1
Dim _prng As New Random
Const test As Integer = 44
Dim cts(test) As Integer
'Dim minBI As New BigInteger(8.98846567431158E+307) '129 bytes
'Dim maxBI As New BigInteger(BigInteger.Pow(New BigInteger(2), 32768)) '4097 bytes)
Dim minBI As New BigInteger(0)
Dim maxBI As New BigInteger(test)
'
Dim aMinL As Integer = minBI.ToByteArray.Length
Dim aMaxL As Integer = maxBI.ToByteArray.Length
Private Sub Form1_Shown(sender As Object, e As System.EventArgs) Handles Me.Shown
If aMinL = 0 Then aMinL = 1
Debug.WriteLine(minBI.ToString)
Debug.WriteLine(maxBI.ToString)
End Sub
Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
Debug.WriteLine(DateTime.Now.ToLongTimeString)
If CheckBox1.Checked Then Array.Clear(cts, 0, cts.Length)
For x As Integer = 1 To 1000
bigIrand()
Next
For x As Integer = 0 To cts.Length - 1
Debug.WriteLine(x & " " & cts(x))
Next
Debug.WriteLine("")
End Sub
Private Sub bigIrand()
Dim foo As New BigInteger
Do
Dim n() As Byte = New Byte(_prng.Next(aMinL, aMaxL + 1)) {}
'what if _prng.NextBytes(n) see *** near end of for loop
For y As Integer = 0 To n.Length - 1
Dim nb As Byte = CByte(_prng.Next(0, 2))
For x As Integer = 1 To 7
nb = nb Or CByte(_prng.Next(0, 2) << x)
Next
'*** what if n(y) = n(y) Xor nb instead of n(y) = nb
n(y) = nb
Next
foo = BigInteger.Abs(New BigInteger(n))
Loop Until foo >= minBI AndAlso foo <= maxBI
cts(CInt(foo)) += 1
End Sub
End Class
You are absolutely right - I failed to look properly through your code before making the remark.
There is a question, I'd like to ask though out of curiosity:
I have looked at this for a while:
and it seems to me to be completely equivalent to usingCode:Dim n() As Byte = New Byte(_prng.Next(aMinL, aMaxL + 1)) {}
'what if _prng.NextBytes(n) see *** near end of for loop
For y As Integer = 0 To n.Length - 1
Dim nb As Byte = CByte(_prng.Next(0, 2))
For x As Integer = 1 To 7
nb = nb Or CByte(_prng.Next(0, 2) << x)
Next
'*** what if n(y) = n(y) Xor nb instead of n(y) = nb
n(y) = nb
Next
though your comments suggest otherwise. I fail to see how taking random bits on a by 8 basis is any different than taking a random byte, but there may be something I am missing. Using the latter gives completely equivalent statistical data in the examples, I tried.Code:Dim n() As Byte = New Byte(_prng.Next(aMinL, aMaxL + 1)) {}
_prng.NextBytes(n)
#EDIT: And I ofc forgot to appologize, which was the intention of this post:
My appologies for making a rash statement about your code before looking properly through it :blush:.
I don't know that setting the bits individually makes any difference whatsoever. Earlier in the thread I think I interpreted something someone said to mean that it didn't produce a random sequence. The issue is that with numbers of the magnitude that the OP is talking about it would be hard to sample a large enough set of numbers to determine is what anyone here is proposing is sound, IMHO.
No apology required. Your willingness to re-evaluate your statement said volumes.
If the random number generator is as near true random as possible then you don't need a large set of numbers to sample (or indeed any set at all) as the math is invariant. The problem of the non-zero start to the range could potentially be a problem simply because it's a bit of a swine to work out which byte marks the minimum value (especially in base 255!) but it's not insurmountable. After that it's exactly the same principle for a 9000+ digit number and a two digit number.Quote:
Originally Posted by dbasnett
So there are some few number of cases out of a 'bajillion' that are at issue? Did whatever number generated using whatever random biginteger method happen to be the <min or >max of the desired range? The method I chose was to simply check the number, and if it fell outside the range, regenerate it, which would work for other methods. I have no reason to believe that what ThomasJohnsen pointed out (using .NextBytes) would be sufficient.Quote:
Originally Posted by dunfiddlin
Code:Dim _prng As New Random
Dim minBI As New BigInteger(8.98846567431158E+307) '129 bytes
Dim maxBI As New BigInteger
'
Dim aMinL As Integer
Dim aMaxL As Integer
Private Sub Form1_Shown(sender As Object, e As System.EventArgs) Handles Me.Shown
maxBI = New BigInteger(2)
maxBI = BigInteger.Pow(maxBI, 32768)
aMinL = minBI.ToByteArray.Length
aMaxL = maxBI.ToByteArray.Length '4097 bytes
If aMinL = 0 Then aMinL = 1
End Sub
Private Function bigIrand() As BigInteger
Dim foo As New BigInteger
Dim retry As Integer = 0
Do
Dim n() As Byte = New Byte(_prng.Next(aMinL, aMaxL + 1)) {}
_prng.NextBytes(n) 'as ThomasJohnsen pointed out this one statement should be sufficient
'For y As Integer = 0 To n.Length - 1
' Dim nb As Byte = CByte(_prng.Next(0, 2))
' For x As Integer = 1 To 7
' nb = nb Or CByte(_prng.Next(0, 2) << x)
' Next
' n(y) = nb
' 'foo = BigInteger.Abs(New BigInteger(n))
' 'If foo > maxBI Then
' ' n(y) = 0
' ' Exit For
' 'End If
'Next
foo = BigInteger.Abs(New BigInteger(n))
retry += 1
Loop Until foo >= minBI AndAlso foo <= maxBI 'if not in range regenerate
If retry > 1 Then Debug.WriteLine(">>>>>>>>>>>>>>>>>>>>")
Return foo
End Function
The lower bound of the range is a 308 digit figure. The probability of getting into an loop where no acceptable number is generated for several thousand cycles is significantly higher than is acceptable given that generating any number at all takes around .1 seconds.
There never has to be any lower bound ofc - wlog generating a posive random bigint suffices, as Matt's F# library demonstrates. But I agree that 'loop until a successful solution is found' is not a viable solution to this problem, which is why I referred to my version of it as ugly. It is a useable solution though, and hopefully the OP dosen't have to generate too many random bigints in a great hurry :).Quote:
Originally Posted by dunfiddlin
Did the OP ever come back? It looks like we've just been talking amongst ourselves. If that is the case, I prefer the original suggestion by JMC, with a slight modification. When the range is that big, what's a few extra bits? After all, we have no idea what the OP really wants, and whether or not there is any wiggle room. Is there a reason that the number range is exactly as it is? Could it be a few bits larger on both the lower and upper bound such that the true range could be an even multiple of bytes? If that's the case, I'd create the proper number of random bytes in an array of bytes, and use that.
I can see one problem - the wiggle room needed would be to avoid the looping (ie. to ensure that the bigint constructed by the randomly generated bytes never gets bigger than max and smaller than min), which means adding bits on top of a very large number. That kind of wiggle-room could lead to max suddenly being many times larger.Quote:
Originally Posted by Shaggy Hiker
#EDIT: ie. the min would need to be scaled down to nearest whole byte and the new max would be min + the gap in bytes between min and max filled with &hff.
Wow, on second look there were several errors in my code. This looks a lot better, does not seem to ever regenerate, and is fairly fast(.04 ms. / number). I left the do loop because I don't intend to sample this in any meaningful way.
edit: ChangedCode:Imports System.Numerics
Public Class Form1
Dim _prng As New Random
Dim minBI As New BigInteger(8.98846567431158E+307) '129 bytes
Dim maxBI As New BigInteger
'
Dim aMinL As Integer
Dim aMaxL As Integer
Private Sub Form1_Shown(sender As Object, e As System.EventArgs) Handles Me.Shown
maxBI = New BigInteger(2)
maxBI = BigInteger.Pow(maxBI, 32768)
aMinL = minBI.ToByteArray.Length
aMaxL = maxBI.ToByteArray.Length '4097 bytes byte(4096)=1, remaining bytes = 0
Debug.WriteLine("")
End Sub
Private Function bigIrand() As BigInteger
'min as array
' n(128) 0
' n(127) 128
' n(126) 0
' n(125) 0
'max as array
' n(4096) 1
' n(4095) 0
' n(4094) 0
' n(4093) 0
Dim foo As New BigInteger
Dim retry As Integer = 0
Do
retry += 1
If retry > 1 Then
Stop
Debug.WriteLine(">>>>>>>>>>>>>>>>>>>>")
End If
Dim n() As Byte = New Byte(_prng.Next(aMinL - 1, aMaxL)) {}
_prng.NextBytes(n) 'get bytes for the random big integer as suggested by ThomasJohnsen
'special case max / min buffer lengths
If n.Length = aMaxL OrElse n.Length = aMinL Then
If n.Length = aMaxL Then
Dim nb As Byte = 0
For y As Integer = 0 To n.Length - 2
nb = nb Or n(y)
Next
If nb = 0 Then
n(aMaxL - 1) = 1
Else
n(aMaxL - 1) = 0
End If
Else
n(aMinL - 1) = 0
n(aMinL - 2) = CByte(_prng.Next(128, 256))
End If
End If
foo = BigInteger.Abs(New BigInteger(n))
Loop Until foo >= minBI AndAlso foo <= maxBI 'if not in range regenerate
Return foo
End Function
Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
Const tries As Integer = 100000
Dim stpw As New Stopwatch
stpw.Reset()
stpw.Start()
For x As Integer = 1 To tries
bigIrand()
Next
stpw.Stop()
Debug.WriteLine("fini " & (stpw.ElapsedMilliseconds / tries).ToString)
End Sub
End Class
n(aMaxL - 1) = CByte(_prng.Next(0, 2))
to
n(aMaxL - 1) = 1
Another DUH! :o
Computers today are impressively fast - I tried comparing my algorithm to yours, and not surprisingly it was twice as slow since I have the overhead of parameters and the need to call BigInteger.Add(random_pos_bigint(BigInteger.Subtract(maxBI, minBI)), minBI) on each iteration, but still: try printing out a single one of those numbers. Amazing that all that can be accomplished 100000 times with memory allocation and everything within just a few seconds.
When I was debugging I was looking at them in the debugger, and finally wondered why :) This was a fun and distracting exercise.
Hi DBasnett, I would like to suggest what might be a minor improvement (if I'm not getting it wrong altogether).Quote:
Originally Posted by dbasnett
It reduces the amount of randomization needed, although not by much if the minimum is much smaller than the maximum. And it needs only one BigInteger comparison in the Loop instruction. Or not:)?Code:Dim diffBI As BigInteger = maxBI - minBI
Do
'.....
'get a random value foo of the same bit length of diffBI, in the way you are doing it now.
'.....
Loop Until foo <= diffBI
Return foo + minBI
BB
I've never seen you guys have so much fun with a question :)
Well it's proper 'computing', ain't it. :cool: Makes a change from re-inventing the wheel which is pretty much all we do the rest of the time!Quote:
Originally Posted by Niya