-
Oct 26th, 2012, 11:12 AM
#1
Thread Starter
New Member
Random BigInteger
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)).
-
Oct 26th, 2012, 11:22 AM
#2
Re: Random BigInteger
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.
-
Oct 26th, 2012, 11:26 AM
#3
Re: Random BigInteger
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.
-
Oct 26th, 2012, 11:40 AM
#4
Re: Random BigInteger
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?
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Oct 26th, 2012, 11:45 AM
#5
Re: Random BigInteger
Originally Posted by jmcilhinney
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.
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.
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.
Last edited by ThomasJohnsen; Oct 26th, 2012 at 11:50 AM.
In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)
-
Oct 26th, 2012, 11:53 AM
#6
Re: Random BigInteger
Originally Posted by jmcilhinney
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.
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.
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Oct 26th, 2012, 11:54 AM
#7
Re: Random BigInteger
Originally Posted by ThomasJohnsen
#EDIT: Dooh - why not just use Random.NextBytes? That would seem like the way to go here.
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.
-
Oct 26th, 2012, 11:57 AM
#8
Re: Random BigInteger
Originally Posted by dunfiddlin
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.
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.
-
Oct 26th, 2012, 12:00 PM
#9
Re: Random BigInteger
Originally Posted by jmcilhinney
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.
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.
My usual boring signature: Nothing
-
Oct 26th, 2012, 12:03 PM
#10
Re: Random BigInteger
why not just use Random.NextBytes? That would seem like the way to go here.
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.
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Oct 26th, 2012, 12:05 PM
#11
Re: Random BigInteger
Originally Posted by Shaggy Hiker
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.
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.
-
Oct 26th, 2012, 12:08 PM
#12
Re: Random BigInteger
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.
My usual boring signature: Nothing
-
Oct 26th, 2012, 12:26 PM
#13
Re: Random BigInteger
Originally Posted by Shaggy Hiker
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.
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!
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Oct 26th, 2012, 12:28 PM
#14
Re: Random BigInteger
Is the OP asking for numbers between 8.9884656743115795386465259539451e+307 and 1.415461031044954789001553027745e+9864?
-
Oct 26th, 2012, 12:29 PM
#15
Re: Random BigInteger
Originally Posted by dunfiddlin
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!
And by extension, the only time I've been wrong, obviously.
-
Oct 26th, 2012, 12:43 PM
#16
Re: Random BigInteger
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.
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Oct 26th, 2012, 12:46 PM
#17
Re: Random BigInteger
Originally Posted by dbasnett
Is the OP asking for numbers between 8.9884656743115795386465259539451e+307 and 1.415461031044954789001553027745e+9864?
Indeed! Makes the lottery look like a coin toss!
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Oct 26th, 2012, 12:49 PM
#18
Re: Random BigInteger
Why 9850? IF the upper range is 2^32768 it won't take 9850 bytes.
-
Oct 26th, 2012, 01:30 PM
#19
Re: Random BigInteger
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
Last edited by dbasnett; Oct 26th, 2012 at 01:40 PM.
-
Oct 26th, 2012, 02:17 PM
#20
My usual boring signature: Nothing
-
Oct 26th, 2012, 02:19 PM
#21
Re: Random BigInteger
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:
Imports RandomBigInt
Imports System.Numerics
Public Class Form1
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
Dim min = BigInteger.Pow(BigInteger.Pow(2, 31) - 1, 33)
Dim max = BigInteger.Pow(2, BigInteger.Pow(2, 15))
Dim r As BigInteger = FsBigInteger.Random(min, max)
End Sub
End Class
This pattern in common to all great programmers I know: they're not experts in something as much as experts in becoming experts in something.
The best programming advice I ever got was to spend my entire career becoming educable. And I suggest you do the same.
-
Oct 26th, 2012, 02:37 PM
#22
Re: Random BigInteger
Originally Posted by MattP
Would you feel bad about creating an F# library and using that in your 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:
vb.net Code:
Private Function random_pos_bigint(ByVal sMax As BigInteger) As BigInteger
Static rnd As New Random
If sMax.Sign <> 1 Then Throw New ArgumentOutOfRangeException("sMax", "Parameter must be positive.")
Dim vMaxBytes() As Byte = sMax.ToByteArray
Dim vBuffer(vMaxBytes.Length) As Byte 'Array one larger in order to have leading 0 at pos 0
Dim i As Integer = vMaxBytes.Length - 1 'Index of high-order byte in vMaxBytes
'Generate random bytes in the buffer.
rnd.NextBytes(vBuffer)
'Zero high-order byte to indicate positive bigint
vBuffer(vMaxBytes.Length) = 0
'Remove optional positive sign and all possible leading zeros.
While vMaxBytes(i) = 0
vBuffer(i) = 0
i -= 1
End While
'Highest-order byte is generated randomly.
vBuffer(i) = Convert.ToByte(rnd.Next(vMaxBytes(i)))
Return New BigInteger(vBuffer)
End Function
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:
vb.net Code:
vBuffer(i) = Convert.ToByte(rnd.Next(vMaxBytes(i) + 1))
While vBuffer(i) = vMaxBytes(i) AndAlso i > 0
i -= 1
vBuffer(i) = Convert.ToByte(rnd.Next(vMaxBytes(i) + 1))
End While
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).
Last edited by ThomasJohnsen; Oct 26th, 2012 at 03:05 PM.
In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)
-
Oct 26th, 2012, 03:36 PM
#23
Re: Random BigInteger
Originally Posted by Shaggy Hiker
It should be.
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.
@ThomasJohnsen - You said "...and it still dosen't generate numbers with equal randomness." How are you checking?
Last edited by dbasnett; Oct 26th, 2012 at 03:39 PM.
-
Oct 26th, 2012, 04:36 PM
#24
Re: Random BigInteger
With a range that big, checking exhaustively should be pretty nearly impossible.
My usual boring signature: Nothing
-
Oct 27th, 2012, 12:36 AM
#25
Re: Random BigInteger
Originally Posted by dbasnett
@ThomasJohnsen - You said "...and it still dosen't generate numbers with equal randomness." How are you checking?
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}.
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:
vb.net Code:
Private Function random_pos_bigint(ByVal sMax As BigInteger) As BigInteger
Static rnd As New Random
If sMax.Sign <> 1 Then Throw New ArgumentOutOfRangeException("sMax", "Parameter must be positive.")
Dim vMaxBytes() As Byte = sMax.ToByteArray
Dim vBuffer(vMaxBytes.Length) As Byte 'Array one larger in order to have leading 0 at pos 0
Dim rVal As BigInteger
'Fill buffer with random bytes.
rnd.NextBytes(vBuffer)
'Zero highest-order byte to indicate positive bigint
vBuffer(vMaxBytes.Length) = 0
'Eliminate all possible leading zeros
i = vMaxBytes.Length - 1
While vMaxBytes(i) = 0
vBuffer(i) = 0
i -= 1
End While
'High-order byte is randomly generated between 0 and the high-order byte of sMax (inclusive)
vBuffer(i) = rnd.Next(vMaxBytes(i) + 1)
'Generate a bigint from the buffer.
rVal = New BigInteger(vBuffer)
'If the randomly generated bigint is >= sMax a new is generated recursively.
If rVal.CompareTo(sMax) > -1 Then Return random_pos_bigint(sMax)
Return rVal
End Function
or in words:
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
Last edited by ThomasJohnsen; Oct 27th, 2012 at 03:17 AM.
In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)
-
Oct 27th, 2012, 09:04 AM
#26
Re: Random BigInteger
"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
-
Oct 27th, 2012, 02:42 PM
#27
Re: Random BigInteger
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:
Code:
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
and it seems to me to be completely equivalent to using
Code:
Dim n() As Byte = New Byte(_prng.Next(aMinL, aMaxL + 1)) {}
_prng.NextBytes(n)
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.
#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 .
Last edited by ThomasJohnsen; Oct 27th, 2012 at 02:46 PM.
In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)
-
Oct 28th, 2012, 11:12 AM
#28
Re: Random BigInteger
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.
-
Oct 28th, 2012, 11:34 AM
#29
Re: Random BigInteger
Originally Posted by dbasnett
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.
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.
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Oct 29th, 2012, 10:13 AM
#30
Re: Random BigInteger
Originally Posted by dunfiddlin
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.
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.
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
-
Oct 29th, 2012, 10:36 AM
#31
Re: Random BigInteger
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.
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
-
Oct 29th, 2012, 11:47 AM
#32
Re: Random BigInteger
Originally Posted by dunfiddlin
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 .
In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)
-
Oct 29th, 2012, 11:56 AM
#33
Re: Random BigInteger
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.
My usual boring signature: Nothing
-
Oct 29th, 2012, 12:26 PM
#34
Re: Random BigInteger
Originally Posted by Shaggy Hiker
...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.
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.
#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.
Last edited by ThomasJohnsen; Oct 29th, 2012 at 12:31 PM.
In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)
-
Oct 29th, 2012, 01:18 PM
#35
Re: Random BigInteger
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.
Code:
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
edit: Changed
n(aMaxL - 1) = CByte(_prng.Next(0, 2))
to
n(aMaxL - 1) = 1
Another DUH!
Last edited by dbasnett; Oct 29th, 2012 at 01:40 PM.
-
Oct 29th, 2012, 05:02 PM
#36
Re: Random BigInteger
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.
In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)
-
Oct 30th, 2012, 11:41 AM
#37
Re: Random BigInteger
When I was debugging I was looking at them in the debugger, and finally wondered why This was a fun and distracting exercise.
-
Oct 30th, 2012, 03:38 PM
#38
Re: Random BigInteger
Originally Posted by dbasnett
Code:
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
Hi DBasnett, I would like to suggest what might be a minor improvement (if I'm not getting it wrong altogether).
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
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?
BB
Last edited by boops boops; Oct 30th, 2012 at 04:22 PM.
Reason: even got my pseudocode wrong!
-
Oct 30th, 2012, 04:02 PM
#39
Re: Random BigInteger
I've never seen you guys have so much fun with a question
-
Oct 30th, 2012, 04:07 PM
#40
Re: Random BigInteger
Originally Posted by Niya
I've never seen you guys have so much fun with a question
Well it's proper 'computing', ain't it. Makes a change from re-inventing the wheel which is pretty much all we do the rest of the time!
As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"
Reviews: "dunfiddlin likes his DataTables" - jmcilhinney
Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|