Page 2 of 2 FirstFirst 12
Results 41 to 79 of 79

Thread: Random BigInteger

  1. #41
    Angel of Code Niya's Avatar
    Join Date
    Nov 2011
    Posts
    8,598

    Re: Random BigInteger

    Now I know what to do if I ever throw a party for you guys....Eats, drinks and pioneering questions
    Treeview with NodeAdded/NodesRemoved events | BlinkLabel control | Calculate Permutations | Object Enums | ComboBox with centered items | .Net Internals article(not mine) | Wizard Control | Understanding Multi-Threading | Simple file compression | Demon Arena

    Copy/move files using Windows Shell | I'm not wanted

    C++ programmers will dismiss you as a cretinous simpleton for your inability to keep track of pointers chained 6 levels deep and Java programmers will pillory you for buying into the evils of Microsoft. Meanwhile C# programmers will get paid just a little bit more than you for writing exactly the same code and VB6 programmers will continue to whitter on about "footprints". - FunkyDexter

    There's just no reason to use garbage like InputBox. - jmcilhinney

    The threads I start are Niya and Olaf free zones. No arguing about the benefits of VB6 over .NET here please. Happiness must reign. - yereverluvinuncleber

  2. #42
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Quote Originally Posted by Niya View Post
    I've never seen you guys have so much fun with a question
    ...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 .
    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)

  3. #43
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    Re: Random BigInteger

    Quote Originally Posted by ThomasJohnsen View Post
    and lean back while someone struggles to implement Sin with 10,000 decimals .
    Wouldn't that be eighth deadly Sin? BB

  4. #44
    Angel of Code Niya's Avatar
    Join Date
    Nov 2011
    Posts
    8,598

    Re: Random BigInteger

    Quote Originally Posted by ThomasJohnsen View Post
    ...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
    Treeview with NodeAdded/NodesRemoved events | BlinkLabel control | Calculate Permutations | Object Enums | ComboBox with centered items | .Net Internals article(not mine) | Wizard Control | Understanding Multi-Threading | Simple file compression | Demon Arena

    Copy/move files using Windows Shell | I'm not wanted

    C++ programmers will dismiss you as a cretinous simpleton for your inability to keep track of pointers chained 6 levels deep and Java programmers will pillory you for buying into the evils of Microsoft. Meanwhile C# programmers will get paid just a little bit more than you for writing exactly the same code and VB6 programmers will continue to whitter on about "footprints". - FunkyDexter

    There's just no reason to use garbage like InputBox. - jmcilhinney

    The threads I start are Niya and Olaf free zones. No arguing about the benefits of VB6 over .NET here please. Happiness must reign. - yereverluvinuncleber

  5. #45
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    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)

  6. #46
    Angel of Code Niya's Avatar
    Join Date
    Nov 2011
    Posts
    8,598

    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.
    Treeview with NodeAdded/NodesRemoved events | BlinkLabel control | Calculate Permutations | Object Enums | ComboBox with centered items | .Net Internals article(not mine) | Wizard Control | Understanding Multi-Threading | Simple file compression | Demon Arena

    Copy/move files using Windows Shell | I'm not wanted

    C++ programmers will dismiss you as a cretinous simpleton for your inability to keep track of pointers chained 6 levels deep and Java programmers will pillory you for buying into the evils of Microsoft. Meanwhile C# programmers will get paid just a little bit more than you for writing exactly the same code and VB6 programmers will continue to whitter on about "footprints". - FunkyDexter

    There's just no reason to use garbage like InputBox. - jmcilhinney

    The threads I start are Niya and Olaf free zones. No arguing about the benefits of VB6 over .NET here please. Happiness must reign. - yereverluvinuncleber

  7. #47
    PowerPoster dunfiddlin's Avatar
    Join Date
    Jun 2012
    Posts
    8,245

    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!

  8. #48
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Quote Originally Posted by Niya View Post
    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)

  9. #49
    Angel of Code Niya's Avatar
    Join Date
    Nov 2011
    Posts
    8,598

    Re: Random BigInteger

    Quote Originally Posted by ThomasJohnsen View Post
    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
    Treeview with NodeAdded/NodesRemoved events | BlinkLabel control | Calculate Permutations | Object Enums | ComboBox with centered items | .Net Internals article(not mine) | Wizard Control | Understanding Multi-Threading | Simple file compression | Demon Arena

    Copy/move files using Windows Shell | I'm not wanted

    C++ programmers will dismiss you as a cretinous simpleton for your inability to keep track of pointers chained 6 levels deep and Java programmers will pillory you for buying into the evils of Microsoft. Meanwhile C# programmers will get paid just a little bit more than you for writing exactly the same code and VB6 programmers will continue to whitter on about "footprints". - FunkyDexter

    There's just no reason to use garbage like InputBox. - jmcilhinney

    The threads I start are Niya and Olaf free zones. No arguing about the benefits of VB6 over .NET here please. Happiness must reign. - yereverluvinuncleber

  10. #50
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    Re: Random BigInteger

    Quote Originally Posted by boops boops View Post
    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  11. #51
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    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:
    1. 'Generate 100 random (and small) bigintegers to test out bigIrand
    2.         For i As Integer = 1 To 100
    3.  
    4.             Dim bufmin(_prng.Next(3, 16)) As Byte
    5.             Dim bufmax(_prng.Next(17, 40)) As Byte
    6.  
    7.             _prng.NextBytes(bufmin)
    8.             _prng.NextBytes(bufmax)
    9.  
    10.             minBI = BigInteger.Abs(New BigInteger(bufmin))
    11.             maxBI = BigInteger.Abs(New BigInteger(bufmax))
    12.  
    13.             aMinL = minBI.ToByteArray.Length
    14.             aMaxL = maxBI.ToByteArray.Length
    15.  
    16.             'Get 100 random bigintegers from bigIrand between min and max
    17.             For j = 1 To 100
    18.  
    19.                 bigIrand()
    20.  
    21.             Next
    22.  
    23.         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)

  12. #52
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  13. #53
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    @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)

  14. #54
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  15. #55
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    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)

  16. #56
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    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
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  17. #57
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    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:
    1. Private Function RandomBigInteger(minimum As BigInteger, maximum As BigInteger) As BigInteger
    2.         Dim biDiff As BigInteger = maximum - minimum
    3.         If biDiff < 0 Then Throw New Exception("Maximum must be more than minimum!")
    4.  
    5.         Dim biResult As BigInteger
    6.         Dim diffBytes() As Byte = biDiff.ToByteArray
    7.         Dim count As Integer = diffBytes.Count
    8.         Dim resultBytes(count - 1) As Byte
    9.  
    10.         Do
    11.             'Get a random byte array of the same length as the diffBytes:
    12.             _random.NextBytes(resultBytes)
    13.  
    14.             'zeroise bits in the most significant byte which are leading zeros in diffBytes:
    15.             For i As Integer = 7 To 0 Step -1
    16.                 Dim bitmask = 1 << i
    17.                 If (diffBytes.Last And bitmask) = bitmask Then
    18.                                         'If the tested bit is 1, there are no more leading zeros:
    19.                     Exit For
    20.                 Else
    21.                                         'Zeroize the tested byte:
    22.                     resultBytes(count - 1) = CByte(resultBytes.Last And (Not bitmask))
    23.  
    24.                 End If
    25.             Next
    26.  
    27.             biResult = New BigInteger(resultBytes)
    28.             _loopCount += 1
    29.  
    30.         Loop Until biResult < biDiff
    31.  
    32.         Return biResult + minimum
    33.     End Function

    Here's a test sub I have been using.
    vb.net Code:
    1. Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
    2.         _loopCount = 0
    3.         Dim minimum As BigInteger
    4.         Dim maximum As BigInteger
    5.         Dim errors As Integer
    6.         Dim positives As Integer
    7.         Dim negatives As Integer
    8.         Dim total As BigInteger
    9.         Dim average As BigInteger
    10.  
    11.         'OP's test limits:
    12.         Dim a As BigInteger = 2 ^ 31 - 1
    13.         minimum = BigInteger.Pow(a, 33)
    14.         Dim b As Integer = CInt(2 ^ 15)
    15.         maximum = BigInteger.Pow(2, b)
    16.        
    17.         'alternative test limits:
    18.         minimum = Long.MinValue
    19.         maximum = Long.MaxValue
    20.         'minimum = 0
    21.         'maximum = &H899999
    22.  
    23.         Dim iterations As Integer = 999999
    24.  
    25.         Dim sw As Stopwatch = Stopwatch.StartNew
    26.         For i As Integer = 0 To iterations - 1
    27.             Dim bi As BigInteger = RandomBigInteger(minimum, maximum)
    28.             'Console.WriteLine(bi.ToString) '(Comment this line out when performance testing.)
    29.             If bi < minimum OrElse bi >= maximum Then
    30.                 Console.WriteLine("Error: " & bi.ToString)
    31.                 errors += 1
    32.             Else
    33.                 total += bi
    34.             End If
    35.             If bi >= 0 Then positives += 1 Else negatives += 1
    36.  
    37.         Next
    38.         Console.WriteLine("Loop count per biginteger : " & (_loopCount / iterations).ToString())
    39.         Console.WriteLine((1000 * sw.ElapsedTicks / Stopwatch.Frequency / iterations).ToString("N3") _
    40.            & " average milliseconds per random biginteger")
    41.         Console.WriteLine("Out-of-range errors : " & errors)
    42.         Console.WriteLine("Positives : " & positives)
    43.         Console.WriteLine("Negatives : " & negatives)
    44.         average = BigInteger.Divide(total, iterations - errors)
    45.         Console.WriteLine("Average: " & average.ToString)
    46.         Console.WriteLine("Average as % of maximum: " & (CDec(average) / CDec(maximum)).ToString("P2"))
    47.     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.

  18. #58
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  19. #59
    PowerPoster dunfiddlin's Avatar
    Join Date
    Jun 2012
    Posts
    8,245

    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!

  20. #60
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    Re: Random BigInteger

    Quote Originally Posted by dunfiddlin View Post
    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  21. #61
    PowerPoster dunfiddlin's Avatar
    Join Date
    Jun 2012
    Posts
    8,245

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    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!

  22. #62
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Quote Originally Posted by boops boops View Post
    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)

  23. #63
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    Re: Random BigInteger

    Quote Originally Posted by dunfiddlin View Post
    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  24. #64
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    Re: Random BigInteger

    Quote Originally Posted by ThomasJohnsen View Post
    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  25. #65
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    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

  26. #66
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Quote Originally Posted by boops boops View Post
    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:
    1. Private Function RandomBigInteger_Max(maximum As BigInteger) As BigInteger
    2.         If maximum <= 0 Then Throw New Exception("Maximum must be positive!")
    3.  
    4.         Dim maxBytes() As Byte = maximum.ToByteArray
    5.         Dim count As Integer = maxBytes.Count
    6.         Dim resultBytes(count - 1) As Byte
    7.  
    8.         'Get a random byte array of the same length as the maxBytes:
    9.         _random.NextBytes(resultBytes)
    10.  
    11.         'zeroise bits in the most significant byte which are leading zeros in maxBytes:
    12.         For i As Integer = 7 To 0 Step -1
    13.             Dim bitmask = 1 << i
    14.             If (maxBytes.Last And bitmask) = bitmask Then
    15.                 'If the tested bit is 1, there are no more leading zeros:
    16.                 Exit For
    17.             Else
    18.                 'Zeroize the tested byte:
    19.                 resultBytes(count - 1) = CByte(resultBytes.Last And (Not bitmask))
    20.             End If
    21.         Next
    22.  
    23.         Return New BigInteger(resultBytes)
    24.     End Function
    25.     Private Function RandomBigInteger_Gen(minimum As BigInteger, maximum As BigInteger) As BigInteger
    26.  
    27.         Dim biDiff As BigInteger = maximum - minimum
    28.         If biDiff < 0 Then Throw New Exception("Maximum must be more than minimum!")
    29.  
    30.         Return BigInteger.Add(RandomBigInteger_Max(biDiff), minimum)
    31.  
    32.     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)

  27. #67
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    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

  28. #68
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Quote Originally Posted by boops boops View Post
    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)

  29. #69
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  30. #70
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    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

  31. #71
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Quote Originally Posted by boops boops View Post
    @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)

  32. #72
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    Re: Random BigInteger

    Quote Originally Posted by boops boops View Post
    @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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  33. #73
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    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+.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  34. #74
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    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

  35. #75
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    Re: Random BigInteger

    Quote Originally Posted by boops boops View Post
    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  36. #76
    PowerPoster dunfiddlin's Avatar
    Join Date
    Jun 2012
    Posts
    8,245

    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!

  37. #77
    PowerPoster boops boops's Avatar
    Join Date
    Nov 2008
    Location
    Holland/France
    Posts
    3,201

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    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

  38. #78
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  39. #79
    Lively Member claws135's Avatar
    Join Date
    Oct 2012
    Posts
    106

    Re: Random BigInteger

    This thread is great, eye bleeding, entertaining reading. keep it up

Page 2 of 2 FirstFirst 12

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
  •  



Click Here to Expand Forum to Full Width