Generating random numbers, part 4 – generate a random System.Numerics.BigInteger using System.Random

Posts in this series:

This is a PowerShell implementation of the two algorithms described in part 3. System.Random is the source of entropy. I return a System.Numerics.BigInteger X such that min <= X < max for a given min and max. To simplify things I define N = maxmin, generate a random number such that 0 <= X < N, and then return X + min at the end.

Here’s an example invocation:

5694168000071045347676722039165259190054180319143041473488317085119130071360

.\random-biginteger.ps1 -min 0 -max ([System.Numerics.BigInteger]::Pow(2, 255) – 19)

Helper function Get-RandomBit keeps a reservoir of 8 random bits from System.Random and hands them out one at a time, replenishing it as necessary.

Get-RandomBigIntegerNaive uses the “naïve algorithm” of building the whole X and then comparing it to N at the end.

Get-RandomBigInteger uses the “better algorithm” of building X a bit at a time, comparing against the corresponding bit of N as we go, until it’s clear whether the ultimate X will be < N or >= N.

As a performance optimization, Get-RandomBigInteger switches from operating on individual bits to operating on whole byte sequences as soon as it can. Helper function Get-RandomBytes simplifies this. Unfortunately PowerShell does not support assigning to array slices. I didn’t bother with this performance optimization in the naïve algorithm.

Let d = ⌊ log2 N ⌋ so 2d <= N <= 2d + 1 – 1. Note that d + 1 is the number of bits in N. We expect the following entropy usage from each algorithm:

NBits of entropy used
NaïveBetter
2d2d + 2d
2d + 12d + 2d + 4
2d + 1 – 1d + 1d + 1

It is possible to improve the performance of the naïve algorithm to use only d bits of entropy in the 2d case, instead of 2d + 2. I didn’t bother.

Get-BitsOfEntropyUsed and Clear-BitsOfEntropyUsed allow measuring this in testing. Here are some results with N = 26 = 64 to 27 = 128, showing the transition from d = 6 to d = 7. Other than the power of 2 at the beginning and the end, we expect the naïve algorithm to gradually ramp down from 2(6) + 2 = 14 to 6 + 1 = 7, and we expect the better algorithm to gradually ramp down from 6 + 4 = 10 to 6 + 1 = 7.

Flips per integer 64: naive 58.919, better 6
Flips per integer 65: naive 13.832, better 9.816
Flips per integer 66: naive 13.755, better 9.571
Flips per integer 67: naive 13.349, better 9.616
Flips per integer 68: naive 13.286, better 9.575
Flips per integer 69: naive 12.719, better 9.506
Flips per integer 70: naive 12.782, better 9.299
Flips per integer 71: naive 12.138, better 9.117
Flips per integer 72: naive 12.803, better 8.978
Flips per integer 73: naive 12.033, better 8.966
Flips per integer 74: naive 12.138, better 9.085
Flips per integer 75: naive 12.187, better 8.855
Flips per integer 76: naive 12.026, better 8.725
Flips per integer 77: naive 11.564, better 8.592
Flips per integer 78: naive 11.62, better 8.595
Flips per integer 79: naive 11.347, better 8.362
Flips per integer 80: naive 10.857, better 8.476
Flips per integer 81: naive 11.361, better 8.793
Flips per integer 82: naive 10.955, better 8.59
Flips per integer 83: naive 10.325, better 8.444
Flips per integer 84: naive 10.64, better 8.433
Flips per integer 85: naive 10.276, better 8.334
Flips per integer 86: naive 10.682, better 8.244
Flips per integer 87: naive 10.059, better 8.12
Flips per integer 88: naive 10.276, better 8.024
Flips per integer 89: naive 10.087, better 8.183
Flips per integer 90: naive 9.905, better 8.017
Flips per integer 91: naive 10.024, better 8.015
Flips per integer 92: naive 10.087, better 8.006
Flips per integer 93: naive 9.723, better 7.909
Flips per integer 94: naive 9.716, better 7.804
Flips per integer 95: naive 9.107, better 7.81
Flips per integer 96: naive 8.939, better 7.668
Flips per integer 97: naive 9.373, better 8.196
Flips per integer 98: naive 9.072, better 7.969
Flips per integer 99: naive 9.086, better 8.208
Flips per integer 100: naive 8.939, better 8.085
Flips per integer 101: naive 8.792, better 8.095
Flips per integer 102: naive 8.687, better 7.929
Flips per integer 103: naive 8.743, better 7.849
Flips per integer 104: naive 8.575, better 7.785
Flips per integer 105: naive 8.421, better 7.769
Flips per integer 106: naive 8.498, better 7.72
Flips per integer 107: naive 8.435, better 7.66
Flips per integer 108: naive 8.288, better 7.656
Flips per integer 109: naive 8.26, better 7.577
Flips per integer 110: naive 8.148, better 7.507
Flips per integer 111: naive 8.057, better 7.497
Flips per integer 112: naive 8.127, better 7.432
Flips per integer 113: naive 7.931, better 7.7
Flips per integer 114: naive 7.791, better 7.541
Flips per integer 115: naive 7.805, better 7.523
Flips per integer 116: naive 7.721, better 7.479
Flips per integer 117: naive 7.693, better 7.461
Flips per integer 118: naive 7.567, better 7.386
Flips per integer 119: naive 7.518, better 7.323
Flips per integer 120: naive 7.336, better 7.272
Flips per integer 121: naive 7.35, better 7.297
Flips per integer 122: naive 7.364, better 7.327
Flips per integer 123: naive 7.322, better 7.145
Flips per integer 124: naive 7.273, better 7.155
Flips per integer 125: naive 7.168, better 7.143
Flips per integer 126: naive 7.133, better 7.084
Flips per integer 127: naive 7.042, better 7.042
Flips per integer 128: naive 16.208, better 7

.\Tests.ps1

And here are some results with N = 230 = 1073741824 to 231 = 2147483648. We expect the naïve algorithm to gradually ramp down from 2(30) + 2 = 62 to 30 + 1 = 31, and we expect the better algorithm to gradually ramp down from 30 + 4 = 34 to 30 + 1 = 31.

Flips per integer 1073741824: naive 60.605, better 30
Flips per integer 1073741825: naive 62.031, better 33.81
Flips per integer 1073741826: naive 62, better 34.251
Flips per integer 1073741827: naive 61.597, better 33.896
Flips per integer 1073741828: naive 61.132, better 33.944
Flips per integer 1073741829: naive 62.899, better 33.932

Flips per integer 2147483643: naive 31, better 31
Flips per integer 2147483644: naive 31, better 31
Flips per integer 2147483645: naive 31, better 31
Flips per integer 2147483646: naive 31, better 31
Flips per integer 2147483647: naive 31, better 31
Flips per integer 2147483648: naive 63.552, better 31

.\Tests.ps1

4 thoughts on “Generating random numbers, part 4 – generate a random System.Numerics.BigInteger using System.Random

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s