Page 1 of 2 12 LastLast
Results 1 to 40 of 79

Thread: Random BigInteger

  1. #1

    Thread Starter
    New Member
    Join Date
    Sep 2012
    Posts
    8

    Random BigInteger

    Hi, I was wondering if there's any way to randomly select a BigInteger within a certain range on Visual Basic 2010 (in my case, it's between (2 ^ 31 - 1) ^ 33 and 2 ^ (2 ^ 15)).

  2. #2
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,274

    Re: Random BigInteger

    You can create a BigInteger by passing an array of Bytes to the constructor. You could work out what Bytes represent the limits of your range and then use a Random object to generate the appropriate number of random Bytes. Note that some of the Bytes generated will be able to span the entire 2 - 255 range while others may not, so you may have to use limits on the Next method to control that.

  3. #3
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,274

    Re: Random BigInteger

    Actually, now that I think about it that would probably not really work because the likelihood of getting a low number would be very small because you'd be unlikely to get all zeroes for the higher-order Bytes. What you probably ought to do is to use Random.NextDouble and then scale that value using the length of your range to select a value within it.

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

    Re: Random BigInteger

    Is there a way to randomly choose one of over 10^9500 integers using a single command on a home computer? What do you think?

    You can get a Cray for $200k these days. Maybe you should start saving up?
    As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"

    Reviews: "dunfiddlin likes his DataTables" - jmcilhinney

    Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!

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

    Re: Random BigInteger

    Quote Originally Posted by jmcilhinney View Post
    Actually, now that I think about it that would probably not really work because the likelihood of getting a low number would be very small because you'd be unlikely to get all zeroes for the higher-order Bytes. What you probably ought to do is to use Random.NextDouble and then scale that value using the length of your range to select a value within it.
    He could determine the number of bytes used to generate both bigints and them generate a random number between the 2 (both inclusive). Then all he had to do was to generate random doubles and use bitconverter on them until he had bytes equal to or larger than the number generated first. A bigint constructor would then be used on the resulting byte array.
    As far as I can tell, that would generate all numbers equally likely (but I haven't done the math - it's just a general assessment)

    #EDIT: Dooh - why not just use Random.NextBytes? That would seem like the way to go here.
    Last edited by ThomasJohnsen; Oct 26th, 2012 at 11:50 AM.
    In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)

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

    Re: Random BigInteger

    Quote Originally Posted by jmcilhinney View Post
    Actually, now that I think about it that would probably not really work because the likelihood of getting a low number would be very small because you'd be unlikely to get all zeroes for the higher-order Bytes. What you probably ought to do is to use Random.NextDouble and then scale that value using the length of your range to select a value within it.
    That would still exclude more numbers than it included as there would need to be a massive upscaling which (as we know all too well from image scaling) simply increases the gaps between possible values. Mathematics on this scale is just something for which the PC, even with BIgInteger, is simply not designed.
    As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"

    Reviews: "dunfiddlin likes his DataTables" - jmcilhinney

    Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!

  7. #7
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,274

    Re: Random BigInteger

    Quote Originally Posted by ThomasJohnsen View Post
    #EDIT: Dooh - why not just use Random.NextBytes? That would seem like the way to go here.
    Because, as I said earlier, that range would likely lead to some Bytes that must be zero, some that could be anywhere in the range 0 - 255 and some that could only be some part of that range.

  8. #8
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,274

    Re: Random BigInteger

    Quote Originally Posted by dunfiddlin View Post
    That would still exclude more numbers than it included as there would need to be a massive upscaling which (as we know all too well from image scaling) simply increases the gaps between possible values. Mathematics on this scale is just something for which the PC, even with BIgInteger, is simply not designed.
    Yeah, you're right about the gaps. It might be possible to use an iterative approach, where a Double was used to determine a range and then another random value was generated within that range so on until there were no more gaps between scaled values. Pretty messy though.

  9. #9
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,943

    Re: Random BigInteger

    Quote Originally Posted by jmcilhinney View Post
    Actually, now that I think about it that would probably not really work because the likelihood of getting a low number would be very small because you'd be unlikely to get all zeroes for the higher-order Bytes. What you probably ought to do is to use Random.NextDouble and then scale that value using the length of your range to select a value within it.
    I'm not sure that that is right. Suppose you were to get a random ULong. To get any given single digit number (0-9) would be roughly one in a bajillion, but not because the odds of getting all 0s in the upper 7 bytes plus a nibble were low. If you got a number that low, then all those upper bits would have to be 0, which is highly improbable, but not more improbable that drawing the number 0-9 from the range of 0 - 2^64. Those numbers are very improbable simply because ANY given number is very improbable once the range is very large.
    My usual boring signature: Nothing

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

    Re: Random BigInteger

    why not just use Random.NextBytes? That would seem like the way to go here.
    For the reason that jmc gave earlier. Not all bytes are equal. The chances of getting a string of zeroes in the high valued bytes (say 1-100 in the sequence) is microscopic compared to the probability of it occurring naturally in a true random choice and given that we're talking a range of over 9800 bytes it's going to be massive skewing toward the higher values.
    As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"

    Reviews: "dunfiddlin likes his DataTables" - jmcilhinney

    Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!

  11. #11
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,274

    Re: Random BigInteger

    Quote Originally Posted by Shaggy Hiker View Post
    I'm not sure that that is right. Suppose you were to get a random ULong. To get any given single digit number (0-9) would be roughly one in a bajillion, but not because the odds of getting all 0s in the upper 7 bytes plus a nibble were low. If you got a number that low, then all those upper bits would have to be 0, which is highly improbable, but not more improbable that drawing the number 0-9 from the range of 0 - 2^64. Those numbers are very improbable simply because ANY given number is very improbable once the range is very large.
    Even when I was posting that I was thinking "is that right" but it's 4 AM here and I can't really think too hard on anything. I should be in bed but I thought I'd stay up and play with my shiny new Office 2013 to see what's new.

  12. #12
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,943

    Re: Random BigInteger

    You are a notable insomniac. However, evaluating new software on a lack of sleep is always risky: No, the pink elephant icons are NOT part of the feature set.
    My usual boring signature: Nothing

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

    Re: Random BigInteger

    Quote Originally Posted by Shaggy Hiker View Post
    I'm not sure that that is right. Suppose you were to get a random ULong. To get any given single digit number (0-9) would be roughly one in a bajillion, but not because the odds of getting all 0s in the upper 7 bytes plus a nibble were low. If you got a number that low, then all those upper bits would have to be 0, which is highly improbable, but not more improbable that drawing the number 0-9 from the range of 0 - 2^64. Those numbers are very improbable simply because ANY given number is very improbable once the range is very large.
    Oh pooh! You're right, of course (I've just done the math!). Typical. The one time I agree with jmc and he's wrong!
    As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"

    Reviews: "dunfiddlin likes his DataTables" - jmcilhinney

    Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!

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

    Re: Random BigInteger

    Is the OP asking for numbers between 8.9884656743115795386465259539451e+307 and 1.415461031044954789001553027745e+9864?
    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. #15
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,274

    Re: Random BigInteger

    Quote Originally Posted by dunfiddlin View Post
    Oh pooh! You're right, of course (I've just done the math!). Typical. The one time I agree with jmc and he's wrong!
    And by extension, the only time I've been wrong, obviously.

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

    Re: Random BigInteger

    Ok, I'm getting around .13 secs to fill a 9850 byte array and convert it to a BigInteger so I suppose it's just about practical if you don't overdo it. Of course that doesn't take any account of the need to adjust for ranges such as the one proposed.
    As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"

    Reviews: "dunfiddlin likes his DataTables" - jmcilhinney

    Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!

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

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    Is the OP asking for numbers between 8.9884656743115795386465259539451e+307 and 1.415461031044954789001553027745e+9864?
    Indeed! Makes the lottery look like a coin toss!
    As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"

    Reviews: "dunfiddlin likes his DataTables" - jmcilhinney

    Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!

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

    Re: Random BigInteger

    Why 9850? IF the upper range is 2^32768 it won't take 9850 bytes.
    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. #19
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Jefferson City, MO
    Posts
    9,748

    Re: Random BigInteger

    The minimum number fits in a byte array of 129 bytes and the maximum fits into an array of 4097, if I have done my math correctly. So if we create an array of random length between those values, and then set each bit randomly, is it random?

    Code:
    Imports System.Numerics
    Public Class Form1
        Dim _prng As New Random
        Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
            For x As Integer = 1 To 100
                Debug.WriteLine("")
                Debug.WriteLine(x)
                amThisRandomQ()
            Next
        End Sub
    
        Private Sub amThisRandomQ()
            Dim minBI As New BigInteger(8.98846567431158E+307)
            Dim maxBI As New BigInteger(2)
            maxBI = BigInteger.Pow(maxBI, 32768)
            'Debug.WriteLine(minBI.ToByteArray.Length)
            'Debug.WriteLine(maxBI.ToByteArray.Length)
            Dim foo As New BigInteger
            Dim stpw As New Stopwatch
            Do
                '129 bytes to 4097
                Dim n() As Byte = New Byte(_prng.Next(129, 4098)) {}
                stpw.Reset()
                stpw.Start()
                'what if _prng.NextBytes(n)  see *** near end of for loop
                For y As Integer = 0 To n.Length - 1
                    Dim nb As Byte = CByte(_prng.Next(0, 2))
                    For x As Integer = 1 To 7
                        nb = nb Or CByte(_prng.Next(0, 2) << x)
                    Next
                    '*** what if n(y) = n(y) Xor nb instead of n(y) = nb
                    n(y) = nb
                Next
                stpw.Stop()
                foo = BigInteger.Abs(New BigInteger(n))
            Loop Until foo >= minBI AndAlso foo <= maxBI
            Debug.WriteLine(stpw.Elapsed.ToString)
            Debug.WriteLine(foo.ToString)
        End Sub
    End Class
    Last edited by dbasnett; Oct 26th, 2012 at 01:40 PM.
    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

  20. #20
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,943

    Re: Random BigInteger

    It should be.
    My usual boring signature: Nothing

  21. #21
    Frenzied Member MattP's Avatar
    Join Date
    Dec 2008
    Location
    WY
    Posts
    1,227

    Re: Random BigInteger

    Would you feel bad about creating an F# library and using that in your code?

    Code:
    namespace RandomBigInt
    
    type FsBigInteger() =
        static let internalRandom = new System.Random()
                    
        /// Returns a BigInteger random number of the specified number of bytes.
        static member Random(numBytes:int, rand:System.Random) =
            let r = if rand=null then internalRandom else rand
            let bytes : byte[] = Array.zeroCreate (numBytes+1)
            r.NextBytes(bytes)
            bytes.[numBytes] <- 0uy
            bigint bytes
            
        /// Returns a BigInteger random number from 0 (inclusive) to max (exclusive).
        static member Random(max:bigint, rand:System.Random) =
            let rec getNumBytesInRange num bytes = if max < num then bytes else getNumBytesInRange (num * 256I) bytes+1
            let bytesNeeded = getNumBytesInRange 256I 1
            FsBigInteger.Random(bytesNeeded, rand) % max
    
        /// Returns a BigInteger random number from min (inclusive) to max (exclusive).
        static member Random(min:bigint, max:bigint) =
            FsBigInteger.Random(max - min, internalRandom) + min
    
        /// Returns a BigInteger random number from min (inclusive) to max (exclusive).
        static member Random(min:bigint, max:bigint, rand:System.Random) =
            FsBigInteger.Random(max - min, rand) + min
    vb.net Code:
    1. Imports RandomBigInt
    2. Imports System.Numerics
    3.  
    4. Public Class Form1
    5.  
    6.     Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
    7.  
    8.         Dim min = BigInteger.Pow(BigInteger.Pow(2, 31) - 1, 33)
    9.         Dim max = BigInteger.Pow(2, BigInteger.Pow(2, 15))
    10.  
    11.         Dim r As BigInteger = FsBigInteger.Random(min, max)
    12.  
    13.     End Sub
    14.  
    15. End Class
    This pattern in common to all great programmers I know: they're not experts in something as much as experts in becoming experts in something.

    The best programming advice I ever got was to spend my entire career becoming educable. And I suggest you do the same.

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

    Re: Random BigInteger

    Quote Originally Posted by MattP View Post
    Would you feel bad about creating an F# library and using that in your code?
    As far as I can tell (from a quick glance never having delved into F#) this is similar to the naive approach, like for instance:

    vb.net Code:
    1. Private Function random_pos_bigint(ByVal sMax As BigInteger) As BigInteger
    2.  
    3.         Static rnd As New Random
    4.  
    5.         If sMax.Sign <> 1 Then Throw New ArgumentOutOfRangeException("sMax", "Parameter must be positive.")
    6.  
    7.         Dim vMaxBytes() As Byte = sMax.ToByteArray
    8.         Dim vBuffer(vMaxBytes.Length) As Byte 'Array one larger in order to have leading 0 at pos 0
    9.         Dim i As Integer = vMaxBytes.Length - 1 'Index of high-order byte in vMaxBytes
    10.  
    11.         'Generate random bytes in the buffer.
    12.         rnd.NextBytes(vBuffer)
    13.  
    14.         'Zero high-order byte to indicate positive bigint
    15.         vBuffer(vMaxBytes.Length) = 0
    16.  
    17.         'Remove optional positive sign and all possible leading zeros.
    18.         While vMaxBytes(i) = 0
    19.  
    20.             vBuffer(i) = 0
    21.             i -= 1
    22.  
    23.         End While
    24.  
    25.         'Highest-order byte is generated randomly.
    26.         vBuffer(i) = Convert.ToByte(rnd.Next(vMaxBytes(i)))
    27.  
    28.         Return New BigInteger(vBuffer)
    29.  
    30.     End Function

    It has the problem of not being able to generate all bigintegers with even likelyhood, since the highest order byte is generated non-inclusive (ie. generating random number in range 0 to 1000 will generate number in the range 0 to 767 with even likelyhood and never integers larger than 767). Adding one (ie. making the high-order byte inclusive) will ofc generate integers in the range 0 to 1024 with even likelyhood when asked for integers in range 0 to 1000.
    But F# may be a solution - like I said I cannot really determine if your code accounts for that or not, since I have no experience using F#.

    Tom

    #EDIT: I tried a naive fix (on my naive sub) and replaced 'vBuffer(i) = Convert.ToByte(rnd.Next(vMaxBytes(i)))' (exclusive) with:
    vb.net Code:
    1. vBuffer(i) = Convert.ToByte(rnd.Next(vMaxBytes(i) + 1))
    2.  
    3.         While vBuffer(i) = vMaxBytes(i) AndAlso i > 0
    4.  
    5.             i -= 1
    6.  
    7.             vBuffer(i) = Convert.ToByte(rnd.Next(vMaxBytes(i) + 1))
    8.  
    9.         End While
    and it still dosen't generate numbers with equal randomness. The fewer combinations available with a randomly selected high-order byte equal to the initial high-order byte, makes my 'random' function favor those slightly. This effect could be reduced by randomizing over multiple high-order bytes, but McIlhinney was right in his initial assumption, that generating a random-function for big integers isn't trivial (unless ofc. Matt's solution works, in which case the problem has already been solved).
    Last edited by ThomasJohnsen; Oct 26th, 2012 at 03:05 PM.
    In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)

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

    Re: Random BigInteger

    Quote Originally Posted by Shaggy Hiker View Post
    It should be.
    The problem I see is testing the randomness because of the size of the numbers. Maybe Knuth's TAOCP will shed some light on this.

    @ThomasJohnsen - You said "...and it still dosen't generate numbers with equal randomness." How are you checking?
    Last edited by dbasnett; Oct 26th, 2012 at 03:39 PM.
    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. #24
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,943

    Re: Random BigInteger

    With a range that big, checking exhaustively should be pretty nearly impossible.
    My usual boring signature: Nothing

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

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    @ThomasJohnsen - You said "...and it still dosen't generate numbers with equal randomness." How are you checking?
    I wasn't talking about your code or Matt's code, but my own sad version. Generating alot of random numbers within a small range made it clear really quickly, that my algorithm is flawed. I tried a couple of different versions of it, but every one was flawed. The problem lies in the highest byte. To illustrate consider standard base-10 notation and let us assume WLOG, that we are able to generate true random numbers in the range 0-9 (one such random digit denoted {R}), and also in any range 0 - x, x in {1, ..., 9} denoted {x}.

    If we define Random(1000) = {R}{R}{R}, we would get equally distributed random numbers between 0 and 999 each equally likely.

    But consider Random(44)

    Defining it as Random(44) = {4}{4} will clearly lead to gaps (ie. never produce 38 for instance).

    Thus we might choose to define it as:
    Let a = {4}
    If a = 4 then (*) Random(44) = a{4} else (**) Random(44) = a{9}

    Each of a in {0, 1, 2, 3, 4} will be equally likely meaning that (*) a{4} will be chosen in 20% of the traverses leading to a 4% chance of Random(44) generating each of {40, 41, 42, 43, 44}. But (**) a{9} will be chosen in 80% of the traverses leading to a 2% chance of Random(44) generating each of {0, 1, ..., 39}, thus making numbers with high-order digit of 4 twice as likely to be generated.

    I tried various variations relying on mod and similar, but wasn't able to create code for a version with a uniform probability for each number within the range.

    #EDIT: Your bit version should exhibit the same problems as my byte version or the example base-10 version. The highest order bit/byte/digit will be generated equally likely as the other bits/bytes/digits but have a smaller range of outcomes, thus leading to a higher chance of those outcomes (though with extremely large numbers and a large base of maybe 64 bits, the difference may not be all that noticeable).


    #EDIT2: The best version, I was able to come up with (and it seems to generate true random numbers - an induction proof based on the number of digits in a base B appears to be at least semi-doable (the fact that (1/dn)^i converges to zero for i increasing is key)), is rather ugly:
    vb.net Code:
    1. Private Function random_pos_bigint(ByVal sMax As BigInteger) As BigInteger
    2.  
    3.         Static rnd As New Random
    4.  
    5.         If sMax.Sign <> 1 Then Throw New ArgumentOutOfRangeException("sMax", "Parameter must be positive.")
    6.  
    7.         Dim vMaxBytes() As Byte = sMax.ToByteArray
    8.         Dim vBuffer(vMaxBytes.Length) As Byte 'Array one larger in order to have leading 0 at pos 0
    9.         Dim rVal As BigInteger
    10.  
    11.         'Fill buffer with random bytes.
    12.         rnd.NextBytes(vBuffer)
    13.  
    14.         'Zero highest-order byte to indicate positive bigint
    15.         vBuffer(vMaxBytes.Length) = 0
    16.  
    17.         'Eliminate all possible leading zeros
    18.         i = vMaxBytes.Length - 1
    19.         While vMaxBytes(i) = 0
    20.             vBuffer(i) = 0
    21.             i -= 1
    22.         End While
    23.  
    24.         'High-order byte is randomly generated between 0 and the high-order byte of sMax (inclusive)
    25.         vBuffer(i) = rnd.Next(vMaxBytes(i) + 1)
    26.  
    27.         'Generate a bigint from the buffer.
    28.         rVal = New BigInteger(vBuffer)
    29.  
    30.         'If the randomly generated bigint is >= sMax a new is generated recursively.
    31.         If rVal.CompareTo(sMax) > -1 Then Return random_pos_bigint(sMax)
    32.  
    33.         Return rVal
    34.  
    35.     End Function
    or in words:
    Random(dn...d2d1d0) on a number in base B with digits di in {0, 1, ..., B-1} and WLOG dn > 0, is defined by
    Code:
    While True
       ai = Random(B) for i < n
       an = Random(dn + 1)
    
       If an...a2a1a0 < dn...d2d1d0 Then Return an...a2a1a0
    End While
    Last edited by ThomasJohnsen; Oct 27th, 2012 at 03:17 AM.
    In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)

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

    Re: Random BigInteger

    "Your bit version should exhibit the same problems as my byte version or the example base-10 version. The highest order bit/byte/digit will be generated equally likely as the other bits/bytes/digits but have a smaller range of outcomes, thus leading to a higher chance of those outcomes", may be true, but it doesn't look to be the case:

    Code:
    Imports System.Numerics
    Public Class Form1
        Dim _prng As New Random
        Const test As Integer = 44
        Dim cts(test) As Integer
        'Dim minBI As New BigInteger(8.98846567431158E+307) '129 bytes
        'Dim maxBI As New BigInteger(BigInteger.Pow(New BigInteger(2), 32768)) '4097 bytes)
        Dim minBI As New BigInteger(0)
        Dim maxBI As New BigInteger(test)
        '
        Dim aMinL As Integer = minBI.ToByteArray.Length
        Dim aMaxL As Integer = maxBI.ToByteArray.Length
    
        Private Sub Form1_Shown(sender As Object, e As System.EventArgs) Handles Me.Shown
            If aMinL = 0 Then aMinL = 1
            Debug.WriteLine(minBI.ToString)
            Debug.WriteLine(maxBI.ToString)
        End Sub
    
        Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
            Debug.WriteLine(DateTime.Now.ToLongTimeString)
            If CheckBox1.Checked Then Array.Clear(cts, 0, cts.Length)
            For x As Integer = 1 To 1000
                bigIrand()
            Next
            For x As Integer = 0 To cts.Length - 1
                Debug.WriteLine(x & "  " & cts(x))
            Next
            Debug.WriteLine("")
        End Sub
    
        Private Sub bigIrand()
            Dim foo As New BigInteger
            Do
                Dim n() As Byte = New Byte(_prng.Next(aMinL, aMaxL + 1)) {}
                'what if _prng.NextBytes(n)  see *** near end of for loop
                For y As Integer = 0 To n.Length - 1
                    Dim nb As Byte = CByte(_prng.Next(0, 2))
                    For x As Integer = 1 To 7
                        nb = nb Or CByte(_prng.Next(0, 2) << x)
                    Next
                    '*** what if n(y) = n(y) Xor nb instead of n(y) = nb
                    n(y) = nb
                Next
                foo = BigInteger.Abs(New BigInteger(n))
            Loop Until foo >= minBI AndAlso foo <= maxBI
            cts(CInt(foo)) += 1
        End Sub
    End Class
    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

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

    Re: Random BigInteger

    You are absolutely right - I failed to look properly through your code before making the remark.

    There is a question, I'd like to ask though out of curiosity:
    I have looked at this for a while:
    Code:
                Dim n() As Byte = New Byte(_prng.Next(aMinL, aMaxL + 1)) {}
                'what if _prng.NextBytes(n)  see *** near end of for loop
                For y As Integer = 0 To n.Length - 1
                    Dim nb As Byte = CByte(_prng.Next(0, 2))
                    For x As Integer = 1 To 7
                        nb = nb Or CByte(_prng.Next(0, 2) << x)
                    Next
                    '*** what if n(y) = n(y) Xor nb instead of n(y) = nb
                    n(y) = nb
                Next
    and it seems to me to be completely equivalent to using
    Code:
    Dim n() As Byte = New Byte(_prng.Next(aMinL, aMaxL + 1)) {}
    _prng.NextBytes(n)
    though your comments suggest otherwise. I fail to see how taking random bits on a by 8 basis is any different than taking a random byte, but there may be something I am missing. Using the latter gives completely equivalent statistical data in the examples, I tried.


    #EDIT: And I ofc forgot to appologize, which was the intention of this post:

    My appologies for making a rash statement about your code before looking properly through it .
    Last edited by ThomasJohnsen; Oct 27th, 2012 at 02:46 PM.
    In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)

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

    Re: Random BigInteger

    I don't know that setting the bits individually makes any difference whatsoever. Earlier in the thread I think I interpreted something someone said to mean that it didn't produce a random sequence. The issue is that with numbers of the magnitude that the OP is talking about it would be hard to sample a large enough set of numbers to determine is what anyone here is proposing is sound, IMHO.

    No apology required. Your willingness to re-evaluate your statement said volumes.
    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

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

    Re: Random BigInteger

    Quote Originally Posted by dbasnett View Post
    I don't know that setting the bits individually makes any difference whatsoever. Earlier in the thread I think I interpreted something someone said to mean that it didn't produce a random sequence. The issue is that with numbers of the magnitude that the OP is talking about it would be hard to sample a large enough set of numbers to determine is what anyone here is proposing is sound, IMHO.
    If the random number generator is as near true random as possible then you don't need a large set of numbers to sample (or indeed any set at all) as the math is invariant. The problem of the non-zero start to the range could potentially be a problem simply because it's a bit of a swine to work out which byte marks the minimum value (especially in base 255!) but it's not insurmountable. After that it's exactly the same principle for a 9000+ digit number and a two digit number.
    As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"

    Reviews: "dunfiddlin likes his DataTables" - jmcilhinney

    Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!

  30. #30
    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
    If the random number generator is as near true random as possible then you don't need a large set of numbers to sample (or indeed any set at all) as the math is invariant. The problem of the non-zero start to the range could potentially be a problem simply because it's a bit of a swine to work out which byte marks the minimum value (especially in base 255!) but it's not insurmountable. After that it's exactly the same principle for a 9000+ digit number and a two digit number.
    So there are some few number of cases out of a 'bajillion' that are at issue? Did whatever number generated using whatever random biginteger method happen to be the <min or >max of the desired range? The method I chose was to simply check the number, and if it fell outside the range, regenerate it, which would work for other methods. I have no reason to believe that what ThomasJohnsen pointed out (using .NextBytes) would be sufficient.

    Code:
        Dim _prng As New Random
        Dim minBI As New BigInteger(8.98846567431158E+307) '129 bytes
        Dim maxBI As New BigInteger
        '
        Dim aMinL As Integer
        Dim aMaxL As Integer
    
        Private Sub Form1_Shown(sender As Object, e As System.EventArgs) Handles Me.Shown
            maxBI = New BigInteger(2)
            maxBI = BigInteger.Pow(maxBI, 32768)
            aMinL = minBI.ToByteArray.Length
            aMaxL = maxBI.ToByteArray.Length '4097 bytes
            If aMinL = 0 Then aMinL = 1
        End Sub
    
        Private Function bigIrand() As BigInteger
            Dim foo As New BigInteger
            Dim retry As Integer = 0
            Do
                Dim n() As Byte = New Byte(_prng.Next(aMinL, aMaxL + 1)) {}
    
                _prng.NextBytes(n) 'as ThomasJohnsen pointed out this one statement should be sufficient 
    
                'For y As Integer = 0 To n.Length - 1
                '    Dim nb As Byte = CByte(_prng.Next(0, 2))
                '    For x As Integer = 1 To 7
                '        nb = nb Or CByte(_prng.Next(0, 2) << x)
                '    Next
                '    n(y) = nb
                '    'foo = BigInteger.Abs(New BigInteger(n))
                '    'If foo > maxBI Then
                '    '    n(y) = 0
                '    '    Exit For
                '    'End If
                'Next
                foo = BigInteger.Abs(New BigInteger(n))
                retry += 1
            Loop Until foo >= minBI AndAlso foo <= maxBI 'if not in range regenerate
            If retry > 1 Then Debug.WriteLine(">>>>>>>>>>>>>>>>>>>>")
            Return foo
        End Function
    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

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

    Re: Random BigInteger

    The lower bound of the range is a 308 digit figure. The probability of getting into an loop where no acceptable number is generated for several thousand cycles is significantly higher than is acceptable given that generating any number at all takes around .1 seconds.
    As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"

    Reviews: "dunfiddlin likes his DataTables" - jmcilhinney

    Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!

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

    Re: Random BigInteger

    Quote Originally Posted by dunfiddlin View Post
    The lower bound of the range is a 308 digit figure. The probability of getting into an loop where no acceptable number is generated for several thousand cycles is significantly higher than is acceptable given that generating any number at all takes around .1 seconds.
    There never has to be any lower bound ofc - wlog generating a posive random bigint suffices, as Matt's F# library demonstrates. But I agree that 'loop until a successful solution is found' is not a viable solution to this problem, which is why I referred to my version of it as ugly. It is a useable solution though, and hopefully the OP dosen't have to generate too many random bigints in a great hurry .
    In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)

  33. #33
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,943

    Re: Random BigInteger

    Did the OP ever come back? It looks like we've just been talking amongst ourselves. If that is the case, I prefer the original suggestion by JMC, with a slight modification. When the range is that big, what's a few extra bits? After all, we have no idea what the OP really wants, and whether or not there is any wiggle room. Is there a reason that the number range is exactly as it is? Could it be a few bits larger on both the lower and upper bound such that the true range could be an even multiple of bytes? If that's the case, I'd create the proper number of random bytes in an array of bytes, and use that.
    My usual boring signature: Nothing

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

    Re: Random BigInteger

    Quote Originally Posted by Shaggy Hiker View Post
    ...I prefer the original suggestion by JMC, with a slight modification. When the range is that big, what's a few extra bits? After all, we have no idea what the OP really wants, and whether or not there is any wiggle room.
    I can see one problem - the wiggle room needed would be to avoid the looping (ie. to ensure that the bigint constructed by the randomly generated bytes never gets bigger than max and smaller than min), which means adding bits on top of a very large number. That kind of wiggle-room could lead to max suddenly being many times larger.

    #EDIT: ie. the min would need to be scaled down to nearest whole byte and the new max would be min + the gap in bytes between min and max filled with &hff.
    Last edited by ThomasJohnsen; Oct 29th, 2012 at 12:31 PM.
    In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)

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

    Re: Random BigInteger

    Wow, on second look there were several errors in my code. This looks a lot better, does not seem to ever regenerate, and is fairly fast(.04 ms. / number). I left the do loop because I don't intend to sample this in any meaningful way.

    Code:
    Imports System.Numerics
    Public Class Form1
        Dim _prng As New Random
        Dim minBI As New BigInteger(8.98846567431158E+307) '129 bytes
        Dim maxBI As New BigInteger
        '
        Dim aMinL As Integer
        Dim aMaxL As Integer
    
        Private Sub Form1_Shown(sender As Object, e As System.EventArgs) Handles Me.Shown
            maxBI = New BigInteger(2)
            maxBI = BigInteger.Pow(maxBI, 32768)
            aMinL = minBI.ToByteArray.Length
            aMaxL = maxBI.ToByteArray.Length '4097 bytes byte(4096)=1, remaining bytes = 0
            Debug.WriteLine("")
        End Sub
    
        Private Function bigIrand() As BigInteger
            'min as array
            ' n(128)  0
            ' n(127)  128
            ' n(126)  0
            ' n(125)  0
    
            'max as array
            ' n(4096)  1
            ' n(4095)  0
            ' n(4094)  0
            ' n(4093)  0
    
            Dim foo As New BigInteger
            Dim retry As Integer = 0
            Do
                retry += 1
                If retry > 1 Then
                    Stop
                    Debug.WriteLine(">>>>>>>>>>>>>>>>>>>>")
                End If
                Dim n() As Byte = New Byte(_prng.Next(aMinL - 1, aMaxL)) {}
    
                _prng.NextBytes(n) 'get bytes for the random big integer as suggested by ThomasJohnsen
    
                'special case max / min buffer lengths
                If n.Length = aMaxL OrElse n.Length = aMinL Then
                    If n.Length = aMaxL Then
                        Dim nb As Byte = 0
                        For y As Integer = 0 To n.Length - 2
                            nb = nb Or n(y)
                        Next
                        If nb = 0 Then
                            n(aMaxL - 1) = 1
                        Else
                            n(aMaxL - 1) = 0
                        End If
                    Else
                        n(aMinL - 1) = 0
                        n(aMinL - 2) = CByte(_prng.Next(128, 256))
                    End If
                End If
                foo = BigInteger.Abs(New BigInteger(n))
            Loop Until foo >= minBI AndAlso foo <= maxBI 'if not in range regenerate
            Return foo
        End Function
    
        Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
            Const tries As Integer = 100000
            Dim stpw As New Stopwatch
            stpw.Reset()
            stpw.Start()
            For x As Integer = 1 To tries
                bigIrand()
            Next
            stpw.Stop()
            Debug.WriteLine("fini " & (stpw.ElapsedMilliseconds / tries).ToString)
        End Sub
    End Class
    edit: Changed
    n(aMaxL - 1) = CByte(_prng.Next(0, 2))
    to
    n(aMaxL - 1) = 1

    Another DUH!
    Last edited by dbasnett; Oct 29th, 2012 at 01:40 PM.
    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. #36
    Fanatic Member ThomasJohnsen's Avatar
    Join Date
    Jul 2010
    Location
    Denmark
    Posts
    528

    Re: Random BigInteger

    Computers today are impressively fast - I tried comparing my algorithm to yours, and not surprisingly it was twice as slow since I have the overhead of parameters and the need to call BigInteger.Add(random_pos_bigint(BigInteger.Subtract(maxBI, minBI)), minBI) on each iteration, but still: try printing out a single one of those numbers. Amazing that all that can be accomplished 100000 times with memory allocation and everything within just a few seconds.
    In truth, a mature man who uses hair-oil, unless medicinally , that man has probably got a quoggy spot in him somewhere. As a general rule, he can't amount to much in his totality. (Melville: Moby Dick)

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

    Re: Random BigInteger

    When I was debugging I was looking at them in the debugger, and finally wondered why This was a fun and distracting exercise.
    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

  38. #38
    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

    Code:
    Imports System.Numerics
    Public Class Form1
        Dim _prng As New Random
        Dim minBI As New BigInteger(8.98846567431158E+307) '129 bytes
        Dim maxBI As New BigInteger
        '
        Dim aMinL As Integer
        Dim aMaxL As Integer
    
        Private Sub Form1_Shown(sender As Object, e As System.EventArgs) Handles Me.Shown
            maxBI = New BigInteger(2)
            maxBI = BigInteger.Pow(maxBI, 32768)
            aMinL = minBI.ToByteArray.Length
            aMaxL = maxBI.ToByteArray.Length '4097 bytes byte(4096)=1, remaining bytes = 0
            Debug.WriteLine("")
        End Sub
    
        Private Function bigIrand() As BigInteger
            'min as array
            ' n(128)  0
            ' n(127)  128
            ' n(126)  0
            ' n(125)  0
    
            'max as array
            ' n(4096)  1
            ' n(4095)  0
            ' n(4094)  0
            ' n(4093)  0
    
            Dim foo As New BigInteger
            Dim retry As Integer = 0
            Do
                retry += 1
                If retry > 1 Then
                    Stop
                    Debug.WriteLine(">>>>>>>>>>>>>>>>>>>>")
                End If
                Dim n() As Byte = New Byte(_prng.Next(aMinL - 1, aMaxL)) {}
    
                _prng.NextBytes(n) 'get bytes for the random big integer as suggested by ThomasJohnsen
    
                'special case max / min buffer lengths
                If n.Length = aMaxL OrElse n.Length = aMinL Then
                    If n.Length = aMaxL Then
                        Dim nb As Byte = 0
                        For y As Integer = 0 To n.Length - 2
                            nb = nb Or n(y)
                        Next
                        If nb = 0 Then
                            n(aMaxL - 1) = 1
                        Else
                            n(aMaxL - 1) = 0
                        End If
                    Else
                        n(aMinL - 1) = 0
                        n(aMinL - 2) = CByte(_prng.Next(128, 256))
                    End If
                End If
                foo = BigInteger.Abs(New BigInteger(n))
            Loop Until foo >= minBI AndAlso foo <= maxBI 'if not in range regenerate
            Return foo
        End Function
    
        Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
            Const tries As Integer = 100000
            Dim stpw As New Stopwatch
            stpw.Reset()
            stpw.Start()
            For x As Integer = 1 To tries
                bigIrand()
            Next
            stpw.Stop()
            Debug.WriteLine("fini " & (stpw.ElapsedMilliseconds / tries).ToString)
        End Sub
    End Class
    Hi DBasnett, I would like to suggest what might be a minor improvement (if I'm not getting it wrong altogether).
    Code:
    Dim diffBI As BigInteger = maxBI - minBI
    Do
    '.....
    'get a random value foo of the same bit length of diffBI, in the way you are doing it now.
    '.....
    Loop Until  foo <= diffBI
    Return foo + minBI
    It reduces the amount of randomization needed, although not by much if the minimum is much smaller than the maximum. And it needs only one BigInteger comparison in the Loop instruction. Or not?

    BB

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

    Re: Random BigInteger

    I've never seen you guys have so much fun with a question
    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

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

    Re: Random BigInteger

    Quote Originally Posted by Niya View Post
    I've never seen you guys have so much fun with a question
    Well it's proper 'computing', ain't it. Makes a change from re-inventing the wheel which is pretty much all we do the rest of the time!
    As the 6-dimensional mathematics professor said to the brain surgeon, "It ain't Rocket Science!"

    Reviews: "dunfiddlin likes his DataTables" - jmcilhinney

    Please be aware that whilst I will read private messages (one day!) I am unlikely to reply to anything that does not contain offers of cash, fame or marriage!

Page 1 of 2 12 LastLast

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