A pseudo-random sequence generator for Go using Preshing's method, based on computing quadratic residues modulo some prime number p:
n ≡ x² (mod p)
The PRNG is reasonably fast: only about 50% slower than the default source in math/rand
. However, it also has the
added advantage that it produces a permuted sequence with no repeated values, which may be desirable in some contexts.
go get -u github.com/mattwiller/qrprng
For general-purpose use, the PRNG can be used as a source for all the functionality offered by math.Rand
:
rng := rand.New(qrprng.Default())
rng.Seed(0xb0a710ad)
normDistDecimal := rng.NormFloat64()
Although the generator only produces uint64
values directly, this allows it to be used in many different ways.
The generator can calculate any term of the sequence in constant time as a uint64
:
rng := qrprng.Default()
n, _ := rng.Index(7_648_235_472)
The parameters of the PRNG are fully customizable, and can use any prime p where p ≡ 3 (mod 4):
p := unit64(11)
rng, _ := qrprng.New(p, 0, 0)
permutation := make([]uint64, p)
for i := uint64(0); i < p; i++ {
permutation[i], _ = rng.Index(i)
}
fmt.Printf(permutation)
// [8 6 4 7 9 3 2 0 5 1 10]
goos: darwin
goarch: amd64
pkg: github.com/mattwiller/qrprng
cpu: Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz
BenchmarkUInt64-16 60565976 20.61 ns/op 0 B/op 0 allocs/op
BenchmarkDefault-16 55240932 21.19 ns/op 0 B/op 0 allocs/op
BenchmarkStdLib-16 88121001 14.28 ns/op 0 B/op 0 allocs/op
BenchmarkStdLibWithQRPRNGSource-16 54257300 21.04 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/mattwiller/qrprng 12.468s
Copyright 2022 Matthew Willer
Licensed under the MIT License. Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.