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
Now I know what to do if I ever throw a party for you guys....Eats, drinks and pioneering questions ;)
...and the OP couldn't care less - he has probably forgotten all about this post :)Quote:
Originally Posted by Niya
The next project should be to extend bigintegers to bigdecimals (or longdecimals, moreprecisedecimals,...?) and begin implementing the math functions using floating points with a user-specified number of decimals :D. Maybe I'll make a new user and pose a question about decimals myself and lean back while someone struggles to implement Sin with 10,000 decimals :D.
Wouldn't that be eighth deadly Sin? BBQuote:
Originally Posted by ThomasJohnsen
You're really evil ;)Quote:
Originally Posted by ThomasJohnsen
I remember reading about a guy that spent a great deal of his life calculating PI with something like 700 decimals by hand.
Lucky for him he was dead before anyone realized, that they were all wrong after a certain point. Iirc they were carved into his tombstone.
Arh - I remembered wrong and mixed up 2 stories. link
Anyways an implementation of a floating-point variable with a user-defined range of decimals could actually be used for something (though not for calculating PI with a record-breaking number of decimals, since that would require more than a trillion decimals and most likely occupy a decent portion of your computers RAM). I'm sure there is something out there already - used by astronomers and the like.
Speaking of PI, I've always thought it to be a bit revealing about our concept of Math as being imperfect since the ratio of a circle's circumference to its diameter cannot be perfectly represented.....then again you can say that 22/7 is a perfect a representation and its base 10 decimal units that cannot represent it perfectly.
I remember wondering after seeing the movie "The Sphere" that if we ever came across a perfect sphere, how would we know since we cannot represent PI perfectly....that is assuming PI is significant to determining how close to perfection a sphere is.
Well, actually, pi is irrelevant to measuring a perfect sphere or circle, come to that, even if such a thing were possible (which it isn't)! One only has to determine that an infinite number of radii are all exactly equal. Piece of cake!
I imagine you can find a mathematician or two, that would claim that the infinite sums used to describe/calculate PI, are indeed perfect representations.Quote:
Originally Posted by Niya
While I am not one of them, I do like the fact, that the field of math has a great number of problems, that aren't easily calculated/proved while being extremely simple to describe. Or things that defy conventional logic. In my opinion, that is what makes the field worth a study.
Perfect representations of imperfection I'd say ;)Quote:
Originally Posted by ThomasJohnsen
The Do Loop was there for testing. Once you (all of the you's that might read this) are satisfied that the loop only runs once it can be removed.Quote:
Originally Posted by boops boops
You can't remove the loop!Quote:
Originally Posted by dbasnett
Try this for instance:
vb.net Code:
@tj - for the values given originally you can. If you want to change the min / max then the code should be changed. A more general approach could be derived from what I have done that would over come the need for the loop regardless of the min / max.
I would like to see that :)Quote:
Originally Posted by dbasnett
#EDIT: What I mean is: I tried various options of eliminating the loop and failed. Whichever method I tried causesd the statistical output to become non-uniformly distributed. But maybe you have an idea, that my old brain didn't, and I'd like to learn (case old dogs still can).
It really is about understanding what values can be in the high order byte of the min/max values, and whether or not BigInteger has prefixed the array with a zero byte or not. It appears to do that when the high order byte has bit 7 on.
I know - in my sub, there's a check for the highest byte to be zero. It just a sign-bit that cannot fit into the previous byte (ie. bit 8 set in the byte preceeding it).Quote:
Originally Posted by dbasnett
Still - assume that max has bits something like 00001001 in the high-order byte. You will have to generate random bytes for all bytes in the output to avoid addling the statistical output, but you cannot check for size, since your object is to eliminate the loop. So your last byte can have any value 0 <= v <= 255, but the only allowed values are 00001000 or 00000xxx. Aritmetic or bitwise operations will not work since more than one byte-value may produce the same value (ie. statistical data invalid).
I tried producing one less byte and the using a random value of 0 to high_order_byte - 1 for the high-order byte in max, but that seemed to addle the output as well.
...and after that I drew all blanks :)
So this isn't done, just a start. Don't know if I need to do everything I am doing. Also, I am trying to allow for negatives :eek:
Code:Imports System.Numerics
Class BigIntRand
Shared _PRNG As New Random
Property min As BigInteger
Property max As BigInteger
Property minLen As Integer
Property maxLen As Integer
Property minHO As Integer
Property maxHO As Integer
Property isMinNeg As Boolean = False
Property isMaxNeg As Boolean = False
Const hob As Byte = 128 'high order bit
Const onesC As Integer = &HFFFFFFFF 'ones complement
Property loops As Integer 'for debugging
Public Sub New(min As BigInteger, max As BigInteger)
If min + 1 >= max Then Throw New OverflowException
Me.min = min 'get the min
Me.max = max 'and max
'setup min variables
Dim temp() As Byte = Me.min.ToByteArray
If (temp(temp.Length - 1) And hob) = hob Then 'set negative
Me.isMinNeg = True
End If
Me.minLen = temp.Length 'set length
Me.minHO = temp(temp.Length - 1) 'convert high order byte to integer
If Me.isMinNeg Then Me.minHO = (Me.minHO Xor onesC) + 1 'take care of negatives (reverse the bits, and add one)
'do the same setup for max variables
temp = Me.max.ToByteArray
If (temp(temp.Length - 1) And hob) = hob Then
Me.isMaxNeg = True
End If
Me.maxLen = temp.Length
Me.maxHO = temp(temp.Length - 1)
If Me.isMaxNeg Then Me.maxHO = (Me.maxHO Xor onesC) + 1
End Sub
Public Function NextBI() As BigInteger
Dim n() As Byte = New Byte(_PRNG.Next(Me.minLen - 1, Me.maxLen)) {}
_PRNG.NextBytes(n)
Dim retval As BigInteger = New BigInteger(n)
Dim temp() As Byte
If n.Length = Me.minLen OrElse retval < Me.min Then
'temp = BitConverter.GetBytes(Me.maxHO)
If n.Length = Me.minLen Then
'minimum length
Else
'new number < minimum
End If
retval = New BigInteger(n)
End If
If n.Length = Me.maxLen OrElse retval >= Me.max Then
'temp = BitConverter.GetBytes(Me.minHO)
If n.Length = Me.maxLen Then
'maximum length
Else
'new number >= maximum
End If
retval = New BigInteger(n)
End If
If retval < Me.min Or retval >= Me.max Then
Debug.WriteLine(Me.loops)
Debug.WriteLine(retval < Me.min)
Debug.WriteLine(retval > Me.max)
Debug.WriteLine(n.Length)
Stop
End If
Return retval
End Function
End Class
Public Class Form1
Dim maxbi As BigInteger
Private Sub Form1_Shown(sender As Object, e As System.EventArgs) Handles Me.Shown
maxBI = New BigInteger(2)
maxBI = BigInteger.Pow(maxBI, 32768)
Debug.WriteLine("")
End Sub
Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
Const tries As Integer = 100000
Dim testBI As BigInteger
Dim foo As New BigIntRand(-1.0, maxbi)
Dim stpw As New Stopwatch
stpw.Reset()
stpw.Start()
For x As Integer = 1 To tries
foo.loops = x
testBI = foo.NextBI
If testBI < foo.min Or testBI > foo.max Then
Debug.WriteLine("err " & (stpw.ElapsedMilliseconds / tries).ToString & " " & foo.loops.ToString)
End If
Next
stpw.Stop()
Debug.WriteLine("fini " & (stpw.ElapsedMilliseconds / tries).ToString)
End Sub
End Class
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:
vb.net Code:
Here's a test sub I have been using.
vb.net Code:
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.
Last night while watching the TBBT I realized my approach was wrong. Then I read BB's post and saw some things that made sense and caused me to have some other insights. Once again I'd like to point out that this has not been tested for randomness.
edit: One way to speed up the ui loop would be to generate the next random number in a separate thread.
Code:Imports System.Numerics
Class BigIntRand
Shared _PRNG As New Random
Public min As BigInteger
Public max As BigInteger
Private newNum() As Byte
Private newNumMaxLen As Integer
Private newNumMinLen As Integer
Private minIsPos As Boolean
Property loops As Integer 'for debugging
Public Sub New(min As BigInteger, max As BigInteger)
Dim foo As BigInteger = max - min 'get the difference
If foo < 1 Then Throw New OverflowException 'must be a difference
Me.min = min 'get the min
Me.max = max 'and max
If Me.min >= 0 Then Me.minIsPos = True Else Me.minIsPos = False 'is min positive?
'get lengths
Me.newNumMaxLen = foo.ToByteArray.Length + 1
Me.newNumMinLen = min.ToByteArray.Length
'is this needed, I don't think so...
If Me.newNumMinLen >= Me.newNumMaxLen Then
Throw New Exception("Logic Error Length") 'remove this if tested
Me.newNumMaxLen = Me.newNumMinLen + 1
Me.newNumMinLen = 1
End If
End Sub
Shared mask As Byte = 255
Shared posMask As Byte = 127
Shared negByte As Byte = 128
Public Function NextBI() As BigInteger
Array.Resize(Me.newNum, _PRNG.Next(Me.newNumMinLen, Me.newNumMaxLen)) 'size the result
_PRNG.NextBytes(Me.newNum) 'create new number
Dim wd As Integer = Me.newNum.Length - 1 'which word
Dim bit As Integer = 7 'which bit
Dim newBI As BigInteger = New BigInteger(Me.newNum) + Me.min 'the random BigInteger
Do While newBI < Me.min Or newBI >= Me.max 'is it in range
'no
'if minimum is positive force high order byte positive
If Me.minIsPos AndAlso ((Me.newNum(wd) And negByte) = negByte) Then
Me.newNum(wd) = Me.newNum(wd) And posMask
bit = 6
Else
'get rid of high order bits one at a time
If wd < 0 Then Throw New Exception("Logic Error - should be > zero")
Dim foo As Byte = CByte((1 << bit) Xor mask) 'create mask
Me.newNum(wd) = Me.newNum(wd) And foo
bit -= 1
If bit < 0 Then
bit = 7
wd -= 1
End If
End If
newBI = New BigInteger(Me.newNum) + Me.min
Loop
Return newBI
End Function
End Class
Public Class Form1
Dim maxbi As BigInteger
Dim minbi As BigInteger
Private Sub Form1_Shown(sender As Object, e As System.EventArgs) Handles Me.Shown
maxbi = New BigInteger(2)
minbi = BigInteger.Pow((BigInteger.Pow(maxbi, 31) - 1), 33)
maxbi = BigInteger.Pow(maxbi, 32768)
Debug.WriteLine("")
End Sub
Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
Const tries As Integer = 100000
Dim testBI As BigInteger
'starting points
'Dim foo As New BigIntRand(-32768, 100)
Dim foo As New BigIntRand(minbi, maxbi)
'Dim foo As New BigIntRand(-minbi, maxbi)
Dim stpw As New Stopwatch
stpw.Reset()
stpw.Start()
For x As Integer = 1 To tries
foo.loops = x
testBI = foo.NextBI
If testBI < foo.min Or testBI > foo.max Then
Debug.WriteLine("err " & (stpw.ElapsedMilliseconds / tries).ToString & " " & foo.loops.ToString)
Stop
End If
Next
stpw.Stop()
Debug.WriteLine("fini " & (stpw.ElapsedMilliseconds / tries).ToString)
End Sub
End Class
There is no test for randomness, more or less by definition. All combinations of values being equally probable how could you decide which series of the following is random?Quote:
has not been tested for randomness
12345
35142
33333
24242
Any 'pattern' you detect is entirely a product of your brain's maddening inability to see anything without imposing a pattern on it. As it is, we know for certain that any computer generated random series is only ever pseudo-random and that applies to this multiple random byte process just as much as to a simple dice simulation. But the point is that you cannot tell the difference. This is why it's very difficult to be certain that dice are loaded or roulette wheels weighted. Even after a large sample you can never say with complete certainty that any series of results, no matter how suspicious, cannot arise from a random selection process.
My point was that there are some accepted tests for pseudo randomness, and that I performed none of them using any code I have posted in this thread.Quote:
Originally Posted by dunfiddlin
edit: So I ran it with min =1 and max = 7. It was consistently wrong in that it generated significantly more 3's and 4's. Here is a typical run:
Code:(1) 12448 Integer
(2) 12450 Integer
(3) 25168 Integer
(4) 24798 Integer
(5) 12558 Integer
(6) 12578 Integer