Posts in this series:

- Generating random numbers, part 1 – using a coin to choose a day of the week
- Generating random numbers, part 2 – using a coin to choose a weekday
- Generating random numbers, part 3 – generate a random integer using random bits
- This one

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* = `max`

– `min`

, 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* = ⌊ log_{2} *N* ⌋ so 2* ^{d}* <=

*N*<= 2

^{d + 1}– 1. Note that

*d*+ 1 is the number of bits in

*N*. We expect the following entropy usage from each algorithm:

N | Bits of entropy used | |
---|---|---|

Naïve | Better | |

2^{d} | 2d + 2 | d |

2^{d} + 1 | 2d + 2 | d + 4 |

… | … | … |

2^{d + 1} – 1 | d + 1 | d + 1 |

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

`Get-BitsOfEntropyUsed`

and `Clear-BitsOfEntropyUsed`

allow measuring this in testing. Here are some results with *N* = 2^{6} = 64 to 2^{7} = 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

.\Tests.ps1

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

And here are some results with N = 2^{30} = 1073741824 to 2^{31} = 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

.\Tests.ps1

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

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