README
¶
Quadratic Residue Pseudo-Random Number Generator
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.
Installation
go get -u github.com/mattwiller/qrprng
Usage
As rand.Source
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.
Random sequence access
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)
Custom generator
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]
License
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.
Documentation
¶
Index ¶
Constants ¶
const ( INT63_MASK = (1 << 63) - 1 // Largest prime (3 mod 4) less than 2^64, permutes [0, 2^64-189) DEFAULT_PRIME = uint64(math.MaxUint64 - 188) DEFAULT_INTERMEDIATE_OFFSET = 5_577_006_791_947_779_410 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type QuadraticResiduePRNG ¶
type QuadraticResiduePRNG struct {
// contains filtered or unexported fields
}
QuadraticResiduePRNG is a thread-unsafe PRNG based on Preshing's method using quadratic residues. The PRNG has the unique advantage of generating a permutation: when `offset` is 0, the output will cycle through all numbers less than `prime` without repeats (until all have been output and the cycle restarts). It implements both rand.Source and rand.Source64, and can be used via rand.New() to generate various random data.
func Default ¶
func Default() *QuadraticResiduePRNG
Default returns a new PRNG instance suitable for general-purpose use. It uses the largest possible prime to permute 99.999999999999999% of possible uint64 values.
func New ¶
func New(prime, intermediateOffset, offset uint64) (*QuadraticResiduePRNG, error)
New creates a new PRNG instance with the given parameters, which are validated for correctness before creation. The chosen prime must be 3 mod 4, and the intermediate offset (seed) can be any number less than the prime. The offset will be added to all output, effectively placing a floor on the output values.
func (*QuadraticResiduePRNG) Index ¶
func (prng *QuadraticResiduePRNG) Index(i uint64) (uint64, error)
Index generates the ith element of the permutation described by the generator. If i >= prime, then an error is returned. However, it can be ignored if desired; the sequence will simply cycle.
func (*QuadraticResiduePRNG) Int63 ¶
func (prng *QuadraticResiduePRNG) Int63() int64
func (*QuadraticResiduePRNG) Seed ¶
func (prng *QuadraticResiduePRNG) Seed(seed int64)
Seed changes the seed of the PRNG instance and resets the internal state of the generator.
func (*QuadraticResiduePRNG) Uint64 ¶
func (prng *QuadraticResiduePRNG) Uint64() uint64
Source Files