Documentation ¶
Overview ¶
Package apophenia provides seekable pseudo-random numbers, allowing reproducibility of pseudo-random results regardless of the order they're generated in.
Index ¶
- type Permutation
- type Sequence
- type SequenceClass
- type Uint128
- func (u *Uint128) Add(value Uint128)
- func (u *Uint128) And(value Uint128)
- func (u *Uint128) Bit(n uint64) uint64
- func (u *Uint128) Inc()
- func (u *Uint128) Mask(n uint64)
- func (u *Uint128) Not()
- func (u *Uint128) Or(value Uint128)
- func (u *Uint128) RotateLeft(n uint64)
- func (u *Uint128) RotateRight(n uint64)
- func (u *Uint128) ShiftLeft(n uint64)
- func (u *Uint128) ShiftRight(n uint64)
- func (u *Uint128) ShiftRightCarry(n uint64) (out Uint128, carry uint64)
- func (u Uint128) String() string
- func (u *Uint128) Sub(value Uint128)
- func (u *Uint128) Xor(value Uint128)
- type Weighted
- type Zipf
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Permutation ¶
type Permutation struct {
// contains filtered or unexported fields
}
PermutationGenerator provides a way to pass integer IDs through a permutation map that is pseudorandom but repeatable. This could be done with `rand.Perm`, but that would require storing a slice of `[Items]int64`, which we want to avoid for large values of Items.
Not actually cryptographically secure.
This implementation is based on: http://arxiv.org/abs/1208.1176v2
This simulates the results of a shuffle in a way allowing a lookup of the results of the shuffle for any given position, in time proportional to a number of "rounds", each of which is 50% likely to swap a slot with another slot. The number of rounds needed to achieve a reasonable probability of safety is `log(N)*6` or so.
Each permutation is fully defined by a "key", consisting of:
- A key "KF" naming a value in [0,max) for each round.
- A series of round functions mapping values in [0,max) to bits, one for each round.
I refer to these as K[r] and F[r]. Thus, K[0] is the index used to compute swap operations four round 0, and F[0] is the series of bits used to determine whether a swap is performed, with F[0][0] being the swap decision for slot 0 in round 0. (Except it probably isn't, because the swap decision is actually made based on the highest index in a pair, to ensure that a swap between A and B always uses the same decision bit.)
K values are generated using the SequencePermutationK range of offsets, with the provided seed, and iteration id 0.
F values are generated using the SequencePermutationF range of offsets, with the provided seed, and iteration ID corresponding to the current round.
For F values, we set byte 8 of the plain text to 0x00, and use encoding/binary to dump the slot number into the first 8 bytes. This yields 128 values, which we treat as the values for the first 128 rounds, and then recycle for rounds 129+ if those exist. This is not very secure, but we're already at 1/2^128 chances by that time and don't care. We could probably trim rounds to 64 or so and not lose much data.
func NewPermutation ¶
func NewPermutation(max int64, seed uint32, src Sequence) (*Permutation, error)
NewPermutation creates a Permutation which generates values in [0,max), from a given Sequence and seed value.
The seed parameter selects different shuffles, and is useful if you need to generate multiple distinct shuffles from the same underlying sequence. Treat it as a secondary seed.
func (*Permutation) Next ¶
func (p *Permutation) Next() (ret int64)
Next generates the next value from the permutation.
func (*Permutation) Nth ¶
func (p *Permutation) Nth(n int64) (ret int64)
Nth generates the Nth value from the permutation. For instance, given a new permutation, calling Next once produces the same value you'd get from calling Nth(0). Seeking using Nth changes the offset that Next counts from; after calling Nth(x), you would get the same result from Next() that you would from Nth(x+1).
Negative offsets count from the end; if p.max is 10, then Nth(9) and Nth(-1) produce the same value.
type Sequence ¶
Sequence represents a specific deterministic but pseudo-random-ish series of bits. A Sequence can be used as a `rand.Source` or `rand.Source64` for `math/rand`.
func NewSequence ¶
NewSequence generates a sequence initialized with the given seed.
type SequenceClass ¶
type SequenceClass uint8
SequenceClass denotes one of the sequence types, which are used to allow sequences to avoid hitting each other's pseudo-random results.
const ( // SequenceDefault is the zero value, used if you didn't think to pick one. SequenceDefault SequenceClass = iota // SequencePermutationK is the K values for the permutation algorithm. SequencePermutationK // SequencePermutationF is the F values for the permutation algorithm. SequencePermutationF // SequenceWeighted is used to generate weighted values for a given // position. SequenceWeighted // SequenceLinear is the random numbers for U%N type usage. SequenceLinear // SequenceZipfU is the random numbers for the Zipf computations. SequenceZipfU // SequenceRandSource is used by default when a Sequence is being // used as a rand.Source. SequenceRandSource // SequenceUser1 is eserved for non-apophenia package usage. SequenceUser1 // SequenceUser2 is reserved for non-apophenia package usage. SequenceUser2 )
type Uint128 ¶
type Uint128 struct {
Lo, Hi uint64 // low-order and high-order uint64 words. Value is “(Hi << 64) | Lo`.
}
Uint128 is a pair of uint64, treated as a single object to simplify calling conventions. It's a struct rather than an array for two reasons:
1. The go compiler seems better at this.
2. [0] and [1] are ambiguous, .Lo and .Hi aren't.
func OffsetFor ¶
func OffsetFor(class SequenceClass, seed uint32, iter uint32, id uint64) Uint128
OffsetFor determines the Uint128 offset for a given class/seed/iteration/id.
func (*Uint128) RotateLeft ¶
RotateLeft rotates u left by n bits.
func (*Uint128) RotateRight ¶
RotateRight rotates u right by n bits.
func (*Uint128) ShiftRight ¶
ShiftRight shifts u right by n bits.
func (*Uint128) ShiftRightCarry ¶
ShiftRightCarry returns both the shifted value and the bits that were shifted out. Useful for when you want both x%N and x/N for N a power of 2. Only sane if bits <= 64.
type Weighted ¶
type Weighted struct {
// contains filtered or unexported fields
}
Weighted provides a generator which produces weighted bits -- bits with a specified probability of being set, as opposed to random values weighted a given way. Bit density is specified as N/M, with M a (positive) power of 2, and N an integer between 0 and M.
The underlying generator can produce 1<<128 128-bit values, but the iterative process requires `log2(densityScale)` 128-bit values from the source per 128-bit output, so the top 7 bits of the address are used as an iteration counter. Thus, Weighted.Bit can produce 2^128 distinct values, but if the offset provided to Weighted.Bits is over 2^121, there will be overlap between the source values used for those bits, and source values used (for different iterations) for other offsets.
func NewWeighted ¶
NewWeighted yields a new Weighted using the given sequence as a source of seekable pseudo-random bits.
type Zipf ¶
type Zipf struct {
// contains filtered or unexported fields
}
Zipf produces a series of values following a Zipf distribution. It is initialized with values q, v, and max, and produces values in the range [0,max) such that the probability of a value k is proportional to (v+k) ** -q. The input value v must be >= 1, and q must be > 1.
This is based on the same paper used for the golang stdlib Zipf distribution:
"Rejection-Inversion to Generate Variates from Monotone Discrete Distributions" W.Hormann, G.Derflinger [1996] http://eeyore.wu-wien.ac.at/papers/96-04-04.wh-der.ps.gz
This implementation differs from stdlib's in that it is seekable; you can get the Nth value in a theoretical series of results in constant time, without having to generate the whole series linearly, and that we used the names q and v rather than s and v.
func NewZipf ¶
NewZipf returns a new Zipf object with the specified q, v, and max, and with its random source seeded in some way by seed. The sequence of values returned is consistent for a given set of inputs. The seed parameter can select one of multiple sub-sequences of the given sequence.