-
Oct 30th, 2012, 04:15 PM
#41
Re: Random BigInteger
Now I know what to do if I ever throw a party for you guys....Eats, drinks and pioneering questions
-
Oct 30th, 2012, 04:18 PM
#42
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, 04:34 PM
#43
Re: Random BigInteger
Originally Posted by ThomasJohnsen
and lean back while someone struggles to implement Sin with 10,000 decimals .
Wouldn't that be eighth deadly Sin? BB
-
Oct 30th, 2012, 04:36 PM
#44
Re: Random BigInteger
Originally Posted by ThomasJohnsen
...and the OP couldn't care less - he has probably forgotten all about this post
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 . 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 .
You're really evil
-
Oct 30th, 2012, 04:51 PM
#45
Re: Random BigInteger
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.
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, 05:27 PM
#46
Re: Random BigInteger
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.
Last edited by Niya; Oct 30th, 2012 at 05:36 PM.
-
Oct 30th, 2012, 05:42 PM
#47
Re: Random BigInteger
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!
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 31st, 2012, 12:35 PM
#48
Re: Random BigInteger
Originally Posted by Niya
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.
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.
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.
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 31st, 2012, 03:40 PM
#49
Re: Random BigInteger
Originally Posted by ThomasJohnsen
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.
Perfect representations of imperfection I'd say
-
Nov 1st, 2012, 12:13 PM
#50
Re: Random BigInteger
Originally Posted by boops boops
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
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.
-
Nov 1st, 2012, 12:28 PM
#51
Re: Random BigInteger
Originally Posted by dbasnett
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.
You can't remove the loop!
Try this for instance:
vb.net Code:
'Generate 100 random (and small) bigintegers to test out bigIrand For i As Integer = 1 To 100 Dim bufmin(_prng.Next(3, 16)) As Byte Dim bufmax(_prng.Next(17, 40)) As Byte _prng.NextBytes(bufmin) _prng.NextBytes(bufmax) minBI = BigInteger.Abs(New BigInteger(bufmin)) maxBI = BigInteger.Abs(New BigInteger(bufmax)) aMinL = minBI.ToByteArray.Length aMaxL = maxBI.ToByteArray.Length 'Get 100 random bigintegers from bigIrand between min and max For j = 1 To 100 bigIrand() Next Next
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)
-
Nov 1st, 2012, 12:35 PM
#52
Re: Random BigInteger
@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.
-
Nov 1st, 2012, 12:42 PM
#53
Re: Random BigInteger
Originally Posted by dbasnett
@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
#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).
Last edited by ThomasJohnsen; Nov 1st, 2012 at 12:49 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)
-
Nov 1st, 2012, 01:01 PM
#54
Re: Random BigInteger
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.
-
Nov 1st, 2012, 01:21 PM
#55
Re: Random BigInteger
Originally Posted by dbasnett
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).
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
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)
-
Nov 1st, 2012, 04:59 PM
#56
Re: Random BigInteger
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
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
-
Nov 1st, 2012, 09:20 PM
#57
Re: Random BigInteger
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:
Private Function RandomBigInteger(minimum As BigInteger, maximum As BigInteger) As BigInteger Dim biDiff As BigInteger = maximum - minimum If biDiff < 0 Then Throw New Exception("Maximum must be more than minimum!") Dim biResult As BigInteger Dim diffBytes() As Byte = biDiff.ToByteArray Dim count As Integer = diffBytes.Count Dim resultBytes(count - 1) As Byte Do 'Get a random byte array of the same length as the diffBytes: _random.NextBytes(resultBytes) 'zeroise bits in the most significant byte which are leading zeros in diffBytes: For i As Integer = 7 To 0 Step -1 Dim bitmask = 1 << i If (diffBytes.Last And bitmask) = bitmask Then 'If the tested bit is 1, there are no more leading zeros: Exit For Else 'Zeroize the tested byte: resultBytes(count - 1) = CByte(resultBytes.Last And (Not bitmask)) End If Next biResult = New BigInteger(resultBytes) _loopCount += 1 Loop Until biResult < biDiff Return biResult + minimum End Function
Here's a test sub I have been using.
vb.net Code:
Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click _loopCount = 0 Dim minimum As BigInteger Dim maximum As BigInteger Dim errors As Integer Dim positives As Integer Dim negatives As Integer Dim total As BigInteger Dim average As BigInteger 'OP's test limits: Dim a As BigInteger = 2 ^ 31 - 1 minimum = BigInteger.Pow(a, 33) Dim b As Integer = CInt(2 ^ 15) maximum = BigInteger.Pow(2, b) 'alternative test limits: minimum = Long.MinValue maximum = Long.MaxValue 'minimum = 0 'maximum = &H899999 Dim iterations As Integer = 999999 Dim sw As Stopwatch = Stopwatch.StartNew For i As Integer = 0 To iterations - 1 Dim bi As BigInteger = RandomBigInteger(minimum, maximum) 'Console.WriteLine(bi.ToString) '(Comment this line out when performance testing.) If bi < minimum OrElse bi >= maximum Then Console.WriteLine("Error: " & bi.ToString) errors += 1 Else total += bi End If If bi >= 0 Then positives += 1 Else negatives += 1 Next Console.WriteLine("Loop count per biginteger : " & (_loopCount / iterations).ToString()) Console.WriteLine((1000 * sw.ElapsedTicks / Stopwatch.Frequency / iterations).ToString("N3") _ & " average milliseconds per random biginteger") Console.WriteLine("Out-of-range errors : " & errors) Console.WriteLine("Positives : " & positives) Console.WriteLine("Negatives : " & negatives) average = BigInteger.Divide(total, iterations - errors) Console.WriteLine("Average: " & average.ToString) Console.WriteLine("Average as % of maximum: " & (CDec(average) / CDec(maximum)).ToString("P2")) End Sub
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 edited by boops boops; Nov 2nd, 2012 at 06:05 AM.
Reason: improved tests
-
Nov 2nd, 2012, 10:31 AM
#58
Re: Random BigInteger
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
Last edited by dbasnett; Nov 2nd, 2012 at 11:37 AM.
-
Nov 2nd, 2012, 11:15 AM
#59
Re: Random BigInteger
has not been tested for randomness
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?
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.
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!
-
Nov 2nd, 2012, 11:20 AM
#60
Re: Random BigInteger
Originally Posted by dunfiddlin
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?
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.
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
Last edited by dbasnett; Nov 2nd, 2012 at 11:40 AM.
-
Nov 2nd, 2012, 11:39 AM
#61
Re: Random BigInteger
Originally Posted by dbasnett
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.
Are there? Accepted by whom? No mathematician would commit to the accuracy or usefulness of such a test, especially given that the main problem with pseudo random is that it's too random (for want of a better expression)! Flip a coin enough times and a sequence of 10 consecutive heads is a near certainty but you can keep a pseudo random selector going to the crack of doom and never come close to it.
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!
-
Nov 2nd, 2012, 12:07 PM
#62
Re: Random BigInteger
Originally Posted by boops boops
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.
What you are doing is the equivalent of what I mentioned in my previous post (ie. using random(0, high_oreder_byte -1) as new highorderbyte). And while I agree with your statement in principle, I found that the statistical data I got, wasn't uniformly distributed among all values within the range. But maybe I was too quick to discard the method - I will have a little look at your version of it in a little while, try some loops over it, and see if you can convince me
#EDIT: Wrote an initial edit here, that I deleted due to it being false! After more testing, I have found out why I discarded the method in the first place. Using a random between 0 and the high-order-byte is NOT the same as the bitmask used by BB (and after seeing my data I banged my head into the wall for even thinking it). BB has it completely right, and I was completely wrong!
Last edited by ThomasJohnsen; Nov 2nd, 2012 at 01:13 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)
-
Nov 2nd, 2012, 01:20 PM
#63
Re: Random BigInteger
Originally Posted by dunfiddlin
Are there? Accepted by whom? No mathematician would commit to the accuracy or usefulness of such a test, especially given that the main problem with pseudo random is that it's too random (for want of a better expression)! Flip a coin enough times and a sequence of 10 consecutive heads is a near certainty but you can keep a pseudo random selector going to the crack of doom and never come close to it.
I hope that you are wrong for Dr. Knuth's sake.
-
Nov 2nd, 2012, 02:14 PM
#64
Re: Random BigInteger
Originally Posted by ThomasJohnsen
What you are doing is the equivalent of what I mentioned in my previous post (ie. using random(0, high_oreder_byte -1) as new highorderbyte). And while I agree with your statement in principle, I found that the statistical data I got, wasn't uniformly distributed among all values within the range. But maybe I was too quick to discard the method - I will have a little look at your version of it in a little while, try some loops over it, and see if you can convince me
#EDIT: Wrote an initial edit here, that I deleted due to it being false! After more testing, I have found out why I discarded the method in the first place. Using a random between 0 and the high-order-byte is NOT the same as the bitmask used by BB (and after seeing my data I banged my head into the wall for even thinking it). BB has it completely right, and I was completely wrong!
I tried BB's method with min = 1, max = 7 and it showed great distribution over 100,000 tries. I have already up voted her, and wish I could again.
-
Nov 3rd, 2012, 06:23 AM
#65
Re: Random BigInteger
Originally Posted by dbasnett
I tried BB's method with min = 1, max = 7 and it showed great distribution over 100,000 tries. I have already up voted her, and wish I could again.
Thank you for your kind words. But Boops boops <> Betty Boop. For my true profile, see here.
My thinking for the method was as follows. Setting a number of bits at random produces a random number; the randomness is as good as the random number generator used to set the bits, or a function of it at least. Random.NextBytes provides a method of setting the bits at random in convenient batches of 8, but doesn't introduce any non-randomness apart from the total number of bits.
I wondered whether knocking out the high order bits might affect the randomness, and I reasoned as follows. Suppose you want a random number in the range 1 to 4, and you have a normal 6-faced die (singular of dice). When you throw the die, each number has a one sixth chance of occurring. What happens if you just ignore throws of 5 or 6 to get the required random throw? The chances of 1, 2, 3 and 4 are still equal (one sixth). So excluding certain numbers from a set of random values does not necessarily change the randomness of those that remain. Zeroizing the high end bits does nothing except reduce the range of values.
BB
-
Nov 3rd, 2012, 06:56 AM
#66
Re: Random BigInteger
Originally Posted by boops boops
Thank you for your kind words. But Boops boops <> Betty Boop. For my true profile, see here.
My thinking for the method was as follows. Setting a number of bits at random produces a random number; the randomness is as good as the random number generator used to set the bits, or a function of it at least. Random.NextBytes provides a method of setting the bits at random in convenient batches of 8, but doesn't introduce any non-randomness apart from the total number of bits.
I wondered whether knocking out the high order bits might affect the randomness, and I reasoned as follows. Suppose you want a random number in the range 1 to 4, and you have a normal 6-faced die (singular of dice ). When you throw the die, each number has a one sixth chance of occurring. What happens if you just ignore throws of 5 or 6 to get the required random throw? The chances of 1, 2, 3 and 4 are still equal (one sixth). So excluding certain numbers from a set of random values does not necessarily change the randomness of those that remain. Zeroizing the high end bits does nothing except reduce the range of values.
BB
I seperated your function into 2 functions (like in Matt's example) to get rid of the looping (which was the running debate at the time), and this seems to perform a tad faster on the few examples I tried:
vb.net Code:
Private Function RandomBigInteger_Max(maximum As BigInteger) As BigInteger If maximum <= 0 Then Throw New Exception("Maximum must be positive!") Dim maxBytes() As Byte = maximum.ToByteArray Dim count As Integer = maxBytes.Count Dim resultBytes(count - 1) As Byte 'Get a random byte array of the same length as the maxBytes: _random.NextBytes(resultBytes) 'zeroise bits in the most significant byte which are leading zeros in maxBytes: For i As Integer = 7 To 0 Step -1 Dim bitmask = 1 << i If (maxBytes.Last And bitmask) = bitmask Then 'If the tested bit is 1, there are no more leading zeros: Exit For Else 'Zeroize the tested byte: resultBytes(count - 1) = CByte(resultBytes.Last And (Not bitmask)) End If Next Return New BigInteger(resultBytes) End Function Private Function RandomBigInteger_Gen(minimum As BigInteger, maximum As BigInteger) As BigInteger Dim biDiff As BigInteger = maximum - minimum If biDiff < 0 Then Throw New Exception("Maximum must be more than minimum!") Return BigInteger.Add(RandomBigInteger_Max(biDiff), minimum) End Function
To test, I used:
Code:
bimin = New BigInteger(75426795804)
bimax = New BigInteger(479207684327642)
Dim s As New Stopwatch
s.Start()
For i = 1 To 10000000
RandomBigInteger(bimin, bimax)
Next
s.Stop()
TextBox1.AppendText(String.Format("Time for BB algo: {0}{1}", s.ElapsedMilliseconds, Environment.NewLine))
s.Reset()
s.Start()
For i = 1 To 10000000
RandomBigInteger_Gen(bimin, bimax)
Next
s.Stop()
TextBox1.AppendText(String.Format("Time for Gen algo: {0}{1}", s.ElapsedMilliseconds, Environment.NewLine))
Unless I screwed something up (again), you have succeded in making a non-looping truly random bigint generator
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)
-
Nov 3rd, 2012, 07:45 AM
#67
Re: Random BigInteger
Thomas, this version ensures that the random number (resultBytes) has the right number of bits but it doesn't compare the result to the maximum. You still have to do that. Suppose the high end byte of the maximum happens to be 00001000. You can't be sure if the generated random number won't have 00001001 in that byte -- or anything up to 00001111. In fact, even the least significant bit of the whole number could result in exceeding the maximum. As far as I can see, there is no option but to compare against the maximum in a loop because you can't know in advance whether each new random number will exceed the maximum. The exception is when the maximum happens to have solid 1s all the way, i.e its value is of the form 2^n - 1.
Still, I feel a bit uneasy. I don't understand why on average so few passes of the loop were needed in my testing with various maximum values.
BB
-
Nov 3rd, 2012, 11:14 AM
#68
Re: Random BigInteger
Originally Posted by boops boops
Thomas, this version ensures that the random number (resultBytes) has the right number of bits but it doesn't compare the result to the maximum. You still have to do that. Suppose the high end byte of the maximum happens to be 00001000. You can't be sure if the generated random number won't have 00001001 in that byte -- or anything up to 00001111. In fact, even the least significant bit of the whole number could result in exceeding the maximum. As far as I can see, there is no option but to compare against the maximum in a loop because you can't know in advance whether each new random number will exceed the maximum. The exception is when the maximum happens to have solid 1s all the way, i.e its value is of the form 2^n - 1.
Once again you're right - I should've never written a word in this thread
Though I do not regret doing so - this is an interesting problem, and I cannot quite get my head around why that loop is neccessary. In my mind, it must be possible to generate a random number between a min and max with uniform distribution within a predetermined amount of time (ie. only depending on the length of the numbers), as long as you are able to generate uniformly distributed random bytes. I think I will pull this problem out once in a while hoping for a Heureka moment, until someone posts a solution (or proves that generating one is impossible without a loop).
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)
-
Nov 3rd, 2012, 12:30 PM
#69
Re: Random BigInteger
Using the OP's original numbers, I have a gut feeling that I have a problem with BB's solution, though I have no way to prove it. In BB's solution the array representing the new number is always 4097 bytes, though the minimum only uses 129 bytes. My gut keeps telling me that this will skew the results.
-
Nov 3rd, 2012, 03:00 PM
#70
Re: Random BigInteger
@dbasnett: The size of the array depends only on the maximum. The minimum has nothing to do with it.
Code:
Dim maxBytes() As Byte = maximum.ToByteArray
Dim count As Integer = maxBytes.Count
Dim resultBytes(count - 1) As Byte
The array doesn't get ReDimmed anywhere so it stays the same size. That doesn't mean the value filled in by Random.NextBytes has to be that big. There will often be some leading zeroes. There is a 50% chance of 1 leading zero, a 25% chance of 2 leading zeros and so on. Any leading zeroes in the randomized array will be ignored by the constructor New BigInteger(byte array).
@Thomas: I'm not sure why you want to avoid using a loop. I don't think efficiency can be the reason because in practice the number of loops is low. I tested the average number of loops needed for my random bigintegers function. Each call had a random maximum. The average loops per call was consistently 1.385-1.386 measured over 1 million calls of the randomizer.
Here's the code I used for the test:
Code:
Dim loopTotal As Integer = 0
For i As Integer = 0 To 999999
_loopCount = 0 '_loopCount is updated in the RandomBiginteger function.
maximum = _random.Next
minimum = 0
Dim bi As BigInteger = RandomBigInteger(minimum, maximum)
loopTotal += _loopCount
Next
Console.WriteLine("Averge loops per biginteger (random maximum): " & loopTotal / 1000000)
I still need to take a closer look at the negative maximum and minimum. I suspect that some code changes will be needed to deal with a non-symmetrical range.
BB
-
Nov 3rd, 2012, 04:39 PM
#71
Re: Random BigInteger
Originally Posted by boops boops
@Thomas: I'm not sure why you want to avoid using a loop.
Simply because I find it to be ugly. The fact that this problem, in my eyes requiring only inner loops, seems to be difficult if not impossible to write without an outer loop, offends me. I'm a fan of odd, elegant and untraditional solutions, that may lead to simpler, faster and/or more general code (bit twiddling hacks and similar), and I feel that you are so close with your solution. Even 1.38 loops per call is .38 too many in my eyes - but then again; I'm an odd sort of fellow and I haven't done this for a living for 20+ years. Maybe if I had to churn out x amount of lines every day, problems like these wouldn't need to be revisited
#EDIT: After having tried expanding the bitfield solution (ie. BB's version of comparing bits in max vs. rnd so 00 -> 00, 01 -> 00, 10 -> exit, 11 -> 11) to the entire array until it could be determined that max > rnd, I have come to the conclusion, that the loop (ugly as I find it) is indeed the best solution. The rnd byte-array will be equal to the max byte-array after the bit-removal has been completed in 100% / (2 ^ number_of_bits_in(max)) of the cases, meaning that the fewer bits there is in max, the more likely it is, that the bit-removal process has to traverse the entire byte-array. Thus forcing another generation of a random byte-array (ie. in the cases where rnd = max after bit-removal).
Trying to sift out bits in the random byte-array to ensure that it is allways smaller than max without ever having to generate a new array and not influencing the distribution of random values, has proved to be impossible for me. Hopefully someone will come along with a solution without a loop at some point; until then, I'm satisfied, that the BB-solution is the best one available.
Last edited by ThomasJohnsen; Nov 4th, 2012 at 06:24 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)
-
Nov 4th, 2012, 08:16 AM
#72
Re: Random BigInteger
Originally Posted by boops boops
@dbasnett: The size of the array depends only on the maximum. The minimum has nothing to do with it.
... That doesn't mean the value filled in by Random.NextBytes has to be that big. There will often be some leading zeroes. There is a 50% chance of 1 leading zero, a 25% chance of 2 leading zeros and so on. Any leading zeroes in the randomized array will be ignored by the constructor New BigInteger(byte array).
That is my concern, that the minimum has nothing to do with it. If the minimum number can be represented with 129 bytes, but you always use an array of 4097 then to get near the minimum you will have to generate approximately 3900 leading zeros in a row. As I said, I have no data to back up my concerns, just a gut feel.
-
Nov 4th, 2012, 08:50 AM
#73
Re: Random BigInteger
So I made the following modifications to the test routine using the OP's original numbers and BB's function. The minimum number has a length of 308 characters, and the maximum has a length of 9865 characters.
Code:
Dim bi As BigInteger
Dim i As Integer
Dim chCt As Long = 0
For i = 1 To iterations
bi = RandomBigInteger(minimum, maximum)
If bi < minimum OrElse bi >= maximum Then
Debug.WriteLine("Error: " & bi.ToString)
errors += 1
Else
Dim s As String = bi.ToString.TrimStart(New Char() {"0"c})
chCt += s.Length
End If
Next
Debug.WriteLine(chCt / (i - 1))
sw.Stop()
The average in the tests I ran was 9864+. When I ran the same test with my class the average was 5000+.
-
Nov 4th, 2012, 12:09 PM
#74
Re: Random BigInteger
Originally Posted by dbasnett
That is my concern, that the minimum has nothing to do with it. If the minimum number can be represented with 129 bytes, but you always use an array of 4097 then to get near the minimum you will have to generate approximately 3900 leading zeros in a row. As I said, I have no data to back up my concerns, just a gut feel.
I don't know why you are concerned about the number of leading zeroes. A random number should average half way in value between the minimum and the maximum. For example, random numbers from 1 to 1000 should average 500, not 50. Shorter numbers are increasingly rare: in the range 1 to 1000 there are only 49 numbers less than 50 but 950 above it.
In binary terms, the average value of random binary numbers from 0 to 1nnn.... should be 01nnn...., not something with a lot of leading zeroes. The chance of any given number cropping up in a 4097-byte random array is once in 2^(4097*8). The chance of a randomized byte array having 3900 zero bytes in a row is once in 2^(3900*8). I bet you would wear out dunfiddlin's Cray trying to find even one of those. BB
BB
-
Nov 4th, 2012, 05:03 PM
#75
Re: Random BigInteger
Originally Posted by boops boops
I don't know why you are concerned about the number of leading zeroes. A random number should average half way in value between the minimum and the maximum. For example, random numbers from 1 to 1000 should average 500, not 50. Shorter numbers are increasingly rare: in the range 1 to 1000 there are only 49 numbers less than 50 but 950 above it.
In binary terms, the average value of random binary numbers from 0 to 1nnn.... should be 01nnn...., not something with a lot of leading zeroes. The chance of any given number cropping up in a 4097-byte random array is once in 2^(4097*8). The chance of a randomized byte array having 3900 zero bytes in a row is once in 2^(3900*8). I bet you would wear out dunfiddlin's Cray trying to find even one of those . BB
BB
Did you try the test code I posted? The results I found seemed to indicate that your method is skewed to the high end of the range, which is what I suspected. Maybe it is an error with how I tested.
When I saw that your method used the larger size only I suspected this would be the result. Since there was only a 1 in 256 chance that the high order byte would be 0, as well as any other, it seemed logical that this would be the result.
-
Nov 4th, 2012, 05:44 PM
#76
Re: Random BigInteger
No it should be high. What you're failing to take into account is that there are 10 times as many 9865 digit numbers as there are 9864 digit numbers, 100 times as many as as 9863 digit numbers, 1000 times as many as 9862 digit numbers and so on.
Think about it from the other end. In the numbers 0-99 there are just 10 single digit numbers. The average length is therefore marginally less then 2. In 0 - 999 there are 10 single digit numbers, 90 double digits and 900 triple digits. The average length is therefore marginally less than 3. This pattern continues at all scales, so with 9865 digits the average length is marginally less than 9865. This will be reduced somewhat by the minimum number but it is still only a marginal effect over the range.
Last edited by dunfiddlin; Nov 4th, 2012 at 05:49 PM.
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!
-
Nov 4th, 2012, 05:50 PM
#77
Re: Random BigInteger
Originally Posted by dbasnett
Did you try the test code I posted? The results I found seemed to indicate that your method is skewed to the high end of the range, which is what I suspected. Maybe it is an error with how I tested.
When I saw that your method used the larger size only I suspected this would be the result. Since there was only a 1 in 256 chance that the high order byte would be 0, as well as any other, it seemed logical that this would be the result.
I didn't try your test code because I don't think it is useful and in my view you are misinterpreting its results. I checked my function for skewing by dividing the range of actual output values into eight equal segments from minimum to maximum (minimum to minimum + one-eight of the maximum, minimum+one-eighth of maximum to minimum+one-quarter etc.). The results were flat across all eight segments. Here's the test code I used:
Code:
Dim rangeSegment(7) As Integer
iterations = 10000000
minimum = 0
maximum = Long.MaxValue
Dim range = maximum - minimum
For i As Integer = 0 To iterations - 1
Dim bi As BigInteger = RandomBigInteger(minimum, maximum)
Select Case (bi - minimum)
Case Is < range / 8
rangeSegment(0) += 1
Case Is < range * 2 / 8
rangeSegment(1) += 1
Case Is < range * 3 / 8
rangeSegment(2) += 1
Case Is < range * 4 / 8
rangeSegment(3) += 1
Case Is < range * 5 / 8
rangeSegment(4) += 1
Case Is < range * 6 / 8
rangeSegment(5) += 1
Case Is < range * 7 / 8
rangeSegment(6) += 1
Case Else
rangeSegment(7) += 1
End Select
Next
For i As Integer = 0 To rangeSegment.Count - 1
Console.Write("Segment " & i & ": " & rangeSegment(i) & " ; ")
Next
The output was:
Code:
Segment 0: 1249396 ; Segment 1: 1251108 ; Segment 2: 1251514 ; Segment 3: 1251063 ; Segment 4: 1249567 ; Segment 5: 1249511 ; Segment 6: 1249467 ; Segment 7: 1248374
As you can see, the output for each segment from minimum to maximum varies by no more than 0.3 percent. To me this indicates that the output of the method is not skewed. If there are any output values with more than three leading zero bits, they will be included in the first segment.
BB
Last edited by boops boops; Nov 4th, 2012 at 06:12 PM.
-
Nov 5th, 2012, 12:56 PM
#78
Re: Random BigInteger
I stand corrected. Both of your points make sense. I must have fallen into the stupid pit, I certainly can't claim ignorance.
I did take BB's approach and make some changes that allow it to generate the next random big integer in the background. This is only faster if you are continually getting numbers between a fixed range, and isn't all that much faster even then.
Code:
Class RandomBI
Shared _PRNG As New Random
Private minimum As BigInteger = 0
Private maximum As BigInteger = 1
Private newBI(0) As Byte 'next random number
Private nextOne As BigInteger
Private HOMask As Byte 'high order mask
Private thrd As Threading.Thread
Private doCalc As New Threading.AutoResetEvent(False)
Private waitAnswer As New Threading.AutoResetEvent(False)
Public Sub New()
If IsNothing(Me.thrd) Then
Me.thrd = New Threading.Thread(AddressOf Me.NextBIbkg)
Me.thrd.IsBackground = True
Me.thrd.Start()
End If
Me.doCalc.Set()
End Sub
Public Function NextBI(min As BigInteger, max As BigInteger) As BigInteger
If min >= max Then Throw New OverflowException
If min <> Me.minimum OrElse max <> Me.maximum Then
Me.newBI = (max - min).ToByteArray 'set the array size
Me.minimum = min
Me.maximum = max
Me.HOMask = 255 'all ones
Dim mask As Byte
For m As Integer = 7 To 0 Step -1 'create mask for high order bits in high order byte
mask = CByte(1 << m)
If (Me.newBI(Me.newBI.Length - 1) And mask) = mask Then
Exit For
Else
Me.HOMask = Me.HOMask Xor mask
End If
Next
Me.waitAnswer.Reset() 'invalidate current answer if one
Me.doCalc.Set() 'tell bkg to go
End If
Me.waitAnswer.WaitOne() 'wait for answer
Dim bi As BigInteger = Me.nextOne 'get the answer
Me.doCalc.Set() 'tell bkg to compute next one
Return bi
End Function
Private Sub NextBIbkg()
Do
Me.doCalc.WaitOne() 'wait for go
Do
_PRNG.NextBytes(Me.newBI)
Me.newBI(Me.newBI.Length - 1) = Me.newBI(Me.newBI.Length - 1) And Me.HOMask
Me.nextOne = New BigInteger(Me.newBI) + Me.minimum
Loop While Me.nextOne < Me.minimum OrElse Me.nextOne >= Me.maximum
Me.waitAnswer.Set() 'new number calculated
Loop
End Sub
End Class
I used this to test
Code:
Dim bar As New RandomBI
Private Sub Button2_Click(sender As System.Object, e As System.EventArgs) Handles Button2.Click
Dim minimum As BigInteger
Dim maximum As BigInteger
Dim errors As Integer
Dim a As BigInteger = 2 ^ 31 - 1
minimum = BigInteger.Pow(a, 33)
Dim b As Integer = CInt(2 ^ 15)
maximum = BigInteger.Pow(2, b)
'
Dim half As BigInteger = ((maximum - minimum) / 2) + minimum
'
Dim lh As Integer = 0 'lower half
Dim uh As Integer = 0 'upper half
Dim bi As BigInteger
Dim i As Integer
Dim sw As Stopwatch = Stopwatch.StartNew
Debug.WriteLine("")
Dim iterations As Integer = 10000
For i = 1 To iterations
'bi = bar.NextBI(minimum, maximum)
bi = RandomBigInteger(minimum, maximum)
If bi < minimum OrElse bi >= maximum Then
Debug.WriteLine("Error: " & bi.ToString)
errors += 1
Else
'which half?
If bi < half Then lh += 1 Else uh += 1
End If
Next
sw.Stop()
Debug.WriteLine(sw.ElapsedMilliseconds / (i - 1))
End Sub
Last edited by dbasnett; Nov 6th, 2012 at 08:54 AM.
-
Nov 5th, 2012, 02:30 PM
#79
Lively Member
Re: Random BigInteger
This thread is great, eye bleeding, entertaining reading. keep it up
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
|