diff options
Diffstat (limited to 'src/math/rand/v2')
| -rw-r--r-- | src/math/rand/v2/auto_test.go | 40 | ||||
| -rw-r--r-- | src/math/rand/v2/chacha8.go | 46 | ||||
| -rw-r--r-- | src/math/rand/v2/chacha8_test.go | 531 | ||||
| -rw-r--r-- | src/math/rand/v2/example_test.go | 142 | ||||
| -rw-r--r-- | src/math/rand/v2/exp.go | 222 | ||||
| -rw-r--r-- | src/math/rand/v2/export_test.go | 13 | ||||
| -rw-r--r-- | src/math/rand/v2/normal.go | 157 | ||||
| -rw-r--r-- | src/math/rand/v2/pcg.go | 121 | ||||
| -rw-r--r-- | src/math/rand/v2/pcg_test.go | 79 | ||||
| -rw-r--r-- | src/math/rand/v2/race_test.go | 44 | ||||
| -rw-r--r-- | src/math/rand/v2/rand.go | 363 | ||||
| -rw-r--r-- | src/math/rand/v2/rand_test.go | 787 | ||||
| -rw-r--r-- | src/math/rand/v2/regress_test.go | 563 | ||||
| -rw-r--r-- | src/math/rand/v2/zipf.go | 77 |
14 files changed, 3185 insertions, 0 deletions
diff --git a/src/math/rand/v2/auto_test.go b/src/math/rand/v2/auto_test.go new file mode 100644 index 0000000..f689733 --- /dev/null +++ b/src/math/rand/v2/auto_test.go @@ -0,0 +1,40 @@ +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand_test + +import ( + . "math/rand/v2" + "testing" +) + +// This test is first, in its own file with an alphabetically early name, +// to try to make sure that it runs early. It has the best chance of +// detecting deterministic seeding if it's the first test that runs. + +func TestAuto(t *testing.T) { + // Pull out 10 int64s from the global source + // and then check that they don't appear in that + // order in the deterministic seeded result. + var out []int64 + for i := 0; i < 10; i++ { + out = append(out, Int64()) + } + + // Look for out in seeded output. + // Strictly speaking, we should look for them in order, + // but this is good enough and not significantly more + // likely to have a false positive. + r := New(NewPCG(1, 0)) + found := 0 + for i := 0; i < 1000; i++ { + x := r.Int64() + if x == out[found] { + found++ + if found == len(out) { + t.Fatalf("found unseeded output in Seed(1) output") + } + } + } +} diff --git a/src/math/rand/v2/chacha8.go b/src/math/rand/v2/chacha8.go new file mode 100644 index 0000000..6b9aa72 --- /dev/null +++ b/src/math/rand/v2/chacha8.go @@ -0,0 +1,46 @@ +// Copyright 2023 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand + +import "internal/chacha8rand" + +// A ChaCha8 is a ChaCha8-based cryptographically strong +// random number generator. +type ChaCha8 struct { + state chacha8rand.State +} + +// NewChaCha8 returns a new ChaCha8 seeded with the given seed. +func NewChaCha8(seed [32]byte) *ChaCha8 { + c := new(ChaCha8) + c.state.Init(seed) + return c +} + +// Seed resets the ChaCha8 to behave the same way as NewChaCha8(seed). +func (c *ChaCha8) Seed(seed [32]byte) { + c.state.Init(seed) +} + +// Uint64 returns a uniformly distributed random uint64 value. +func (c *ChaCha8) Uint64() uint64 { + for { + x, ok := c.state.Next() + if ok { + return x + } + c.state.Refill() + } +} + +// UnmarshalBinary implements the encoding.BinaryUnmarshaler interface. +func (c *ChaCha8) UnmarshalBinary(data []byte) error { + return chacha8rand.Unmarshal(&c.state, data) +} + +// MarshalBinary implements the encoding.BinaryMarshaler interface. +func (c *ChaCha8) MarshalBinary() ([]byte, error) { + return chacha8rand.Marshal(&c.state), nil +} diff --git a/src/math/rand/v2/chacha8_test.go b/src/math/rand/v2/chacha8_test.go new file mode 100644 index 0000000..2c55b47 --- /dev/null +++ b/src/math/rand/v2/chacha8_test.go @@ -0,0 +1,531 @@ +// Copyright 2023 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand_test + +import ( + . "math/rand/v2" + "testing" +) + +func TestChaCha8(t *testing.T) { + p := NewChaCha8(chacha8seed) + for i, x := range chacha8output { + if u := p.Uint64(); u != x { + t.Errorf("ChaCha8 #%d = %#x, want %#x", i, u, x) + } + } + + p.Seed(chacha8seed) + for i, x := range chacha8output { + if u := p.Uint64(); u != x { + t.Errorf("ChaCha8 #%d = %#x, want %#x", i, u, x) + } + } +} + +func TestChaCha8Marshal(t *testing.T) { + p := NewChaCha8(chacha8seed) + for i, x := range chacha8output { + enc, err := p.MarshalBinary() + if err != nil { + t.Fatalf("#%d: MarshalBinary: %v", i, err) + } + if string(enc) != chacha8marshal[i] { + t.Fatalf("#%d: MarshalBinary=%q, want %q", i, enc, chacha8marshal[i]) + } + *p = ChaCha8{} + if err := p.UnmarshalBinary(enc); err != nil { + t.Fatalf("#%d: UnmarshalBinary: %v", i, err) + } + if u := p.Uint64(); u != x { + t.Errorf("ChaCha8 #%d = %#x, want %#x", i, u, x) + } + } +} + +func BenchmarkChaCha8(b *testing.B) { + p := NewChaCha8([32]byte{1, 2, 3, 4, 5}) + var t uint64 + for n := b.N; n > 0; n-- { + t += p.Uint64() + } + Sink = t +} + +// Golden output test to make sure algorithm never changes, +// so that its use in math/rand/v2 stays stable. + +var chacha8seed = [32]byte([]byte("ABCDEFGHIJKLMNOPQRSTUVWXYZ123456")) + +var chacha8output = []uint64{ + 0xb773b6063d4616a5, 0x1160af22a66abc3c, 0x8c2599d9418d287c, 0x7ee07e037edc5cd6, + 0xcfaa9ee02d1c16ad, 0x0e090eef8febea79, 0x3c82d271128b5b3e, 0x9c5addc11252a34f, + 0xdf79bb617d6ceea6, 0x36d553591f9d736a, 0xeef0d14e181ee01f, 0x089bfc760ae58436, + 0xd9e52b59cc2ad268, 0xeb2fb4444b1b8aba, 0x4f95c8a692c46661, 0xc3c6323217cae62c, + 0x91ebb4367f4e2e7e, 0x784cf2c6a0ec9bc6, 0x5c34ec5c34eabe20, 0x4f0a8f515570daa8, + 0xfc35dcb4113d6bf2, 0x5b0da44c645554bc, 0x6d963da3db21d9e1, 0xeeaefc3150e500f3, + 0x2d37923dda3750a5, 0x380d7a626d4bc8b0, 0xeeaf68ede3d7ee49, 0xf4356695883b717c, + 0x846a9021392495a4, 0x8e8510549630a61b, 0x18dc02545dbae493, 0x0f8f9ff0a65a3d43, + 0xccf065f7190ff080, 0xfd76d1aa39673330, 0x95d232936cba6433, 0x6c7456d1070cbd17, + 0x462acfdaff8c6562, 0x5bafab866d34fc6a, 0x0c862f78030a2988, 0xd39a83e407c3163d, + 0xc00a2b7b45f22ebf, 0x564307c62466b1a9, 0x257e0424b0c072d4, 0x6fb55e99496c28fe, + 0xae9873a88f5cd4e0, 0x4657362ac60d3773, 0x1c83f91ecdf23e8e, 0x6fdc0792c15387c0, + 0x36dad2a30dfd2b5c, 0xa4b593290595bdb7, 0x4de18934e4cc02c5, 0xcdc0d604f015e3a7, + 0xfba0dbf69ad80321, 0x60e8bea3d139de87, 0xd18a4d851ef48756, 0x6366447c2215f34a, + 0x05682e97d3d007ee, 0x4c0e8978c6d54ab2, 0xcf1e9f6a6712edc2, 0x061439414c80cfd3, + 0xd1a8b6e2745c0ead, 0x31a7918d45c410e8, 0xabcc61ad90216eec, 0x4040d92d2032a71a, + 0x3cd2f66ffb40cd68, 0xdcd051c07295857a, 0xeab55cbcd9ab527e, 0x18471dce781bdaac, + 0xf7f08cd144dc7252, 0x5804e0b13d7f40d1, 0x5cb1a446e4b2d35b, 0xe6d4a728d2138a06, + 0x05223e40ca60dad8, 0x2d61ec3206ac6a68, 0xab692356874c17b8, 0xc30954417676de1c, + 0x4f1ace3732225624, 0xfba9510813988338, 0x997f200f52752e11, 0x1116aaafe86221fa, + 0x07ce3b5cb2a13519, 0x2956bc72bc458314, 0x4188b7926140eb78, 0x56ca6dbfd4adea4d, + 0x7fe3c22349340ce5, 0x35c08f9c37675f8a, 0x11e1c7fbef5ed521, 0x98adc8464ec1bc75, + 0xd163b2c73d1203f8, 0x8c761ee043a2f3f3, 0x24b99d6accecd7b7, 0x793e31aa112f0370, + 0x8e87dc2a19285139, 0x4247ae04f7096e25, 0x514f3122926fe20f, 0xdc6fb3f045d2a7e9, + 0x15cb30cecdd18eba, 0xcbc7fdecf6900274, 0x3fb5c696dc8ba021, 0xd1664417c8d274e6, + 0x05f7e445ea457278, 0xf920bbca1b9db657, 0x0c1950b4da22cb99, 0xf875baf1af09e292, + 0xbed3d7b84250f838, 0xf198e8080fd74160, 0xc9eda51d9b7ea703, 0xf709ef55439bf8f6, + 0xd20c74feebf116fc, 0x305668eb146d7546, 0x829af3ec10d89787, 0x15b8f9697b551dbc, + 0xfc823c6c8e64b8c9, 0x345585e8183b40bc, 0x674b4171d6581368, 0x1234d81cd670e9f7, + 0x0e505210d8a55e19, 0xe8258d69eeeca0dc, 0x05d4c452e8baf67e, 0xe8dbe30116a45599, + 0x1cf08ce1b1176f00, 0xccf7d0a4b81ecb49, 0x303fea136b2c430e, 0x861d6c139c06c871, + 0x5f41df72e05e0487, 0x25bd7e1e1ae26b1d, 0xbe9f4004d662a41d, 0x65bf58d483188546, + 0xd1b27cff69db13cc, 0x01a6663372c1bb36, 0x578dd7577b727f4d, 0x19c78f066c083cf6, + 0xdbe014d4f9c391bb, 0x97fbb2dd1d13ffb3, 0x31c91e0af9ef8d4f, 0x094dfc98402a43ba, + 0x069bd61bea37b752, 0x5b72d762e8d986ca, 0x72ee31865904bc85, 0xd1f5fdc5cd36c33e, + 0xba9b4980a8947cad, 0xece8f05eac49ab43, 0x65fe1184abae38e7, 0x2d7cb9dea5d31452, + 0xcc71489476e467e3, 0x4c03a258a578c68c, 0x00efdf9ecb0fd8fc, 0x9924cad471e2666d, + 0x87f8668318f765e9, 0xcb4dc57c1b55f5d8, 0xd373835a86604859, 0xe526568b5540e482, + 0x1f39040f08586fec, 0xb764f3f00293f8e6, 0x049443a2f6bd50a8, 0x76fec88697d3941a, + 0x3efb70d039bae7a2, 0xe2f4611368eca8a8, 0x7c007a96e01d2425, 0xbbcce5768e69c5bf, + 0x784fb4985c42aac3, 0xf72b5091aa223874, 0x3630333fb1e62e07, 0x8e7319ebdebbb8de, + 0x2a3982bca959fa00, 0xb2b98b9f964ba9b3, 0xf7e31014adb71951, 0xebd0fca3703acc82, + 0xec654e2a2fe6419a, 0xb326132d55a52e2c, 0x2248c57f44502978, 0x32710c2f342daf16, + 0x0517b47b5acb2bec, 0x4c7a718fca270937, 0xd69142bed0bcc541, 0xe40ebcb8ff52ce88, + 0x3e44a2dbc9f828d4, 0xc74c2f4f8f873f58, 0x3dbf648eb799e45b, 0x33f22475ee0e86f8, + 0x1eb4f9ee16d47f65, 0x40f8d2b8712744e3, 0xb886b4da3cb14572, 0x2086326fbdd6f64d, + 0xcc3de5907dd882b9, 0xa2e8b49a5ee909df, 0xdbfb8e7823964c10, 0x70dd6089ef0df8d5, + 0x30141663cdd9c99f, 0x04b805325c240365, 0x7483d80314ac12d6, 0x2b271cb91aa7f5f9, + 0x97e2245362abddf0, 0x5a84f614232a9fab, 0xf71125fcda4b7fa2, 0x1ca5a61d74b27267, + 0x38cc6a9b3adbcb45, 0xdde1bb85dc653e39, 0xe9d0c8fa64f89fd4, 0x02c5fb1ecd2b4188, + 0xf2bd137bca5756e5, 0xadefe25d121be155, 0x56cd1c3c5d893a8e, 0x4c50d337beb65bb9, + 0x918c5151675cf567, 0xaba649ffcfb56a1e, 0x20c74ab26a2247cd, 0x71166bac853c08da, + 0xb07befe2e584fc5d, 0xda45ff2a588dbf32, 0xdb98b03c4d75095e, 0x60285ae1aaa65a4c, + 0xf93b686a263140b8, 0xde469752ee1c180e, 0xcec232dc04129aae, 0xeb916baa1835ea04, + 0xd49c21c8b64388ff, 0x72a82d9658864888, 0x003348ef7eac66a8, 0x7f6f67e655b209eb, + 0x532ffb0b7a941b25, 0xd940ade6128deede, 0xdf24f2a1af89fe23, 0x95aa3b4988195ae0, + 0x3da649404f94be4a, 0x692dad132c3f7e27, 0x40aee76ecaaa9eb8, 0x1294a01e09655024, + 0x6df797abdba4e4f5, 0xea2fb6024c1d7032, 0x5f4e0492295489fc, 0x57972914ea22e06a, + 0x9a8137d133aad473, 0xa2e6dd6ae7cdf2f3, 0x9f42644f18086647, 0x16d03301c170bd3e, + 0x908c416fa546656d, 0xe081503be22e123e, 0x077cf09116c4cc72, 0xcbd25cd264b7f229, + 0x3db2f468ec594031, 0x46c00e734c9badd5, 0xd0ec0ac72075d861, 0x3037cb3cf80b7630, + 0x574c3d7b3a2721c6, 0xae99906a0076824b, 0xb175a5418b532e70, 0xd8b3e251ee231ddd, + 0xb433eec25dca1966, 0x530f30dc5cff9a93, 0x9ff03d98b53cd335, 0xafc4225076558cdf, + 0xef81d3a28284402a, 0x110bdbf51c110a28, 0x9ae1b255d027e8f6, 0x7de3e0aa24688332, + 0xe483c3ecd2067ee2, 0xf829328b276137e6, 0xa413ccad57562cad, 0xe6118e8b496acb1f, + 0x8288dca6da5ec01f, 0xa53777dc88c17255, 0x8a00f1e0d5716eda, 0x618e6f47b7a720a8, + 0x9e3907b0c692a841, 0x978b42ca963f34f3, 0x75e4b0cd98a7d7ef, 0xde4dbd6e0b5f4752, + 0x0252e4153f34493f, 0x50f0e7d803734ef9, 0x237766a38ed167ee, 0x4124414001ee39a0, + 0xd08df643e535bb21, 0x34f575b5a9a80b74, 0x2c343af87297f755, 0xcd8b6d99d821f7cb, + 0xe376fd7256fc48ae, 0xe1b06e7334352885, 0xfa87b26f86c169eb, 0x36c1604665a971de, + 0xdba147c2239c8e80, 0x6b208e69fc7f0e24, 0x8795395b6f2b60c3, 0x05dabee9194907f4, + 0xb98175142f5ed902, 0x5e1701e2021ddc81, 0x0875aba2755eed08, 0x778d83289251de95, + 0x3bfbe46a039ecb31, 0xb24704fce4cbd7f9, 0x6985ffe9a7c91e3d, 0xc8efb13df249dabb, + 0xb1037e64b0f4c9f6, 0x55f69fd197d6b7c3, 0x672589d71d68a90c, 0xbebdb8224f50a77e, + 0x3f589f80007374a7, 0xd307f4635954182a, 0xcff5850c10d4fd90, 0xc6da02dfb6408e15, + 0x93daeef1e2b1a485, 0x65d833208aeea625, 0xe2b13fa13ed3b5fa, 0x67053538130fb68e, + 0xc1042f6598218fa9, 0xee5badca749b8a2e, 0x6d22a3f947dae37d, 0xb62c6d1657f4dbaf, + 0x6e007de69704c20b, 0x1af2b913fc3841d8, 0xdc0e47348e2e8e22, 0x9b1ddef1cf958b22, + 0x632ed6b0233066b8, 0xddd02d3311bed8f2, 0xf147cfe1834656e9, 0x399aaa49d511597a, + 0x6b14886979ec0309, 0x64fc4ac36b5afb97, 0xb82f78e07f7cf081, 0x10925c9a323d0e1b, + 0xf451c79ee13c63f6, 0x7c2fc180317876c7, 0x35a12bd9eecb7d22, 0x335654a539621f90, + 0xcc32a3f35db581f0, 0xc60748a80b2369cb, 0x7c4dd3b08591156b, 0xac1ced4b6de22291, + 0xa32cfa2df134def5, 0x627108918dea2a53, 0x0555b1608fcb4ff4, 0x143ee7ac43aaa33c, + 0xdae90ce7cf4fc218, 0x4d68fc2582bcf4b5, 0x37094e1849135d71, 0xf7857e09f3d49fd8, + 0x007538c503768be7, 0xedf648ba2f6be601, 0xaa347664dd72513e, 0xbe63893c6ef23b86, + 0x130b85710605af97, 0xdd765c6b1ef6ab56, 0xf3249a629a97dc6b, 0x2a114f9020fab8e5, + 0x5a69e027cfc6ad08, 0x3c4ccb36f1a5e050, 0x2e9e7d596834f0a5, 0x2430be6858fce789, + 0xe90b862f2466e597, 0x895e2884f159a9ec, 0x26ab8fa4902fcb57, 0xa6efff5c54e1fa50, + 0x333ac4e5811a8255, 0xa58d515f02498611, 0xfe5a09dcb25c6ef4, 0x03898988ab5f5818, + 0x289ff6242af6c617, 0x3d9dd59fd381ea23, 0x52d7d93d8a8aae51, 0xc76a123d511f786f, + 0xf68901edaf00c46c, 0x8c630871b590de80, 0x05209c308991e091, 0x1f809f99b4788177, + 0x11170c2eb6c19fd8, 0x44433c779062ba58, 0xc0acb51af1874c45, 0x9f2e134284809fa1, + 0xedb523bd15c619fa, 0x02d97fd53ecc23c0, 0xacaf05a34462374c, 0xddd9c6d34bffa11f, +} + +var chacha8marshal = []string{ + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x00ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x01ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x02ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x03ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x04ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x05ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x06ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\aABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\bABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\tABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\nABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\vABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\fABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\rABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x0eABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x0fABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x10ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x11ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x12ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x13ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x14ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x15ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x16ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x17ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x18ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x19ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1aABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1bABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1cABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1dABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1eABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1fABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00 ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00!ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\"ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00#ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00$ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00%ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00&ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00'ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00(ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00)ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00*ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00+ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00,ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00-ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00.ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00/ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x000ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x001ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x002ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x003ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x004ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x005ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x006ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x007ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x008ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x009ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00:ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00;ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00<ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00=ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00>ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00?ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00@ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00AABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00BABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00CABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00DABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00EABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00FABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00GABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00HABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00IABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00JABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00KABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00LABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00MABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00NABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00OABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00PABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00QABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00RABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00SABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00TABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00UABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00VABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00WABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00XABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00YABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00ZABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00[ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\\ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00]ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00^ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00_ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00`ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00aABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00bABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00cABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00dABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00eABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00fABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00gABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00hABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00iABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00jABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00kABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00lABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00mABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00nABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00oABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00pABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00qABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00rABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00sABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00tABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00uABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00vABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00wABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00xABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00yABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00zABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00{ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00|ABCDEFGHIJKLMNOPQRSTUVWXYZ123456", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x01>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x02>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x03>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x04>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x05>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x06>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\a>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\b>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\t>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\n>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\v>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\f>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\r>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x0e>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x0f>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x10>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x11>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x12>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x13>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x14>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x15>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x16>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x17>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x18>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x19>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1a>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1b>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1c>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1d>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1e>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1f>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00 >\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00!>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\">\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00#>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00$>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00%>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00&>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00'>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00(>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00)>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00*>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00+>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00,>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00->\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00.>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00/>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x000>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x001>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x002>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x003>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x004>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x005>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x006>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x007>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x008>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x009>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00:>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00;>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00<>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00=>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00>>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00?>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00@>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00A>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00B>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00C>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00D>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00E>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00F>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00G>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00H>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00I>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00J>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00K>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00L>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00M>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00N>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00O>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00P>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00Q>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00R>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00S>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00T>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00U>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00V>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00W>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00X>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00Y>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00Z>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00[>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\\>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00]>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00^>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00_>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00`>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00a>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00b>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00c>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00d>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00e>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00f>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00g>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00h>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00i>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00j>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00k>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00l>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00m>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00n>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00o>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00p>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00q>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00r>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00s>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00t>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00u>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00v>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00w>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00x>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00y>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00z>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00{>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00|>\x15\x0e\xacHk4O\x11a\xa8R\xcd5\x9atr\x8cXO\x9c]\x10\xdf\xf61\xea\x11\x18\x06\x8a\xaa", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x01K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x02K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x03K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x04K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x05K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x06K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\aK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\bK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\tK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\nK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\vK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\fK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\rK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x0eK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x0fK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x10K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x11K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x12K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x13K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x14K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x15K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x16K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x17K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x18K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x19K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1aK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1bK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1cK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1dK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1eK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\x1fK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00 K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00!K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\"K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00#K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00$K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00%K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00&K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00'K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00(K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00)K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00*K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00+K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00,K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00-K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00.K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00/K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x000K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x001K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x002K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x003K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x004K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x005K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x006K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x007K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x008K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x009K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00:K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00;K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00<K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00=K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00>K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00?K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00@K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00AK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00BK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00CK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00DK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00EK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00FK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00GK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00HK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00IK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00JK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00KK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00LK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00MK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00NK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00OK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00PK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00QK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00RK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00SK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00TK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00UK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00VK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00WK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00XK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00YK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00ZK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00[K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00\\K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00]K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00^K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00_K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00`K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00aK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00bK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00cK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00dK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00eK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00fK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00gK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00hK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00iK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00jK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00kK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00lK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00mK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00nK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00oK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00pK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00qK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00rK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00sK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00tK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00uK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00vK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00wK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00xK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00yK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00zK3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", + "chacha8:\x00\x00\x00\x00\x00\x00\x00{K3\x9bB!,\x94\x9d\x975\xce'O_t\xee|\xb21\x87\xbb\xbb\xfd)\x8f\xe52\x01\vP\fk", +} diff --git a/src/math/rand/v2/example_test.go b/src/math/rand/v2/example_test.go new file mode 100644 index 0000000..070b0ad --- /dev/null +++ b/src/math/rand/v2/example_test.go @@ -0,0 +1,142 @@ +// Copyright 2012 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand_test + +import ( + "fmt" + "math/rand/v2" + "os" + "strings" + "text/tabwriter" + "time" +) + +// These tests serve as an example but also make sure we don't change +// the output of the random number generator when given a fixed seed. + +func Example() { + answers := []string{ + "It is certain", + "It is decidedly so", + "Without a doubt", + "Yes definitely", + "You may rely on it", + "As I see it yes", + "Most likely", + "Outlook good", + "Yes", + "Signs point to yes", + "Reply hazy try again", + "Ask again later", + "Better not tell you now", + "Cannot predict now", + "Concentrate and ask again", + "Don't count on it", + "My reply is no", + "My sources say no", + "Outlook not so good", + "Very doubtful", + } + fmt.Println("Magic 8-Ball says:", answers[rand.IntN(len(answers))]) +} + +// This example shows the use of each of the methods on a *Rand. +// The use of the global functions is the same, without the receiver. +func Example_rand() { + // Create and seed the generator. + // Typically a non-fixed seed should be used, such as Uint64(), Uint64(). + // Using a fixed seed will produce the same output on every run. + r := rand.New(rand.NewPCG(1, 2)) + + // The tabwriter here helps us generate aligned output. + w := tabwriter.NewWriter(os.Stdout, 1, 1, 1, ' ', 0) + defer w.Flush() + show := func(name string, v1, v2, v3 any) { + fmt.Fprintf(w, "%s\t%v\t%v\t%v\n", name, v1, v2, v3) + } + + // Float32 and Float64 values are in [0, 1). + show("Float32", r.Float32(), r.Float32(), r.Float32()) + show("Float64", r.Float64(), r.Float64(), r.Float64()) + + // ExpFloat64 values have an average of 1 but decay exponentially. + show("ExpFloat64", r.ExpFloat64(), r.ExpFloat64(), r.ExpFloat64()) + + // NormFloat64 values have an average of 0 and a standard deviation of 1. + show("NormFloat64", r.NormFloat64(), r.NormFloat64(), r.NormFloat64()) + + // Int32, Int64, and Uint32 generate values of the given width. + // The Int method (not shown) is like either Int32 or Int64 + // depending on the size of 'int'. + show("Int32", r.Int32(), r.Int32(), r.Int32()) + show("Int64", r.Int64(), r.Int64(), r.Int64()) + show("Uint32", r.Uint32(), r.Uint32(), r.Uint32()) + + // IntN, Int32N, and Int64N limit their output to be < n. + // They do so more carefully than using r.Int()%n. + show("IntN(10)", r.IntN(10), r.IntN(10), r.IntN(10)) + show("Int32N(10)", r.Int32N(10), r.Int32N(10), r.Int32N(10)) + show("Int64N(10)", r.Int64N(10), r.Int64N(10), r.Int64N(10)) + + // Perm generates a random permutation of the numbers [0, n). + show("Perm", r.Perm(5), r.Perm(5), r.Perm(5)) + // Output: + // Float32 0.95955694 0.8076733 0.8135684 + // Float64 0.4297927436037299 0.797802349388613 0.3883664855410056 + // ExpFloat64 0.43463410545541104 0.5513632046504593 0.7426404617374481 + // NormFloat64 -0.9303318111676635 -0.04750789419852852 0.22248301107582735 + // Int32 2020777787 260808523 851126509 + // Int64 5231057920893523323 4257872588489500903 158397175702351138 + // Uint32 314478343 1418758728 208955345 + // IntN(10) 6 2 0 + // Int32N(10) 3 7 7 + // Int64N(10) 8 9 4 + // Perm [0 3 1 4 2] [4 1 2 0 3] [4 3 2 0 1] +} + +func ExamplePerm() { + for _, value := range rand.Perm(3) { + fmt.Println(value) + } + + // Unordered output: 1 + // 2 + // 0 +} + +func ExampleN() { + // Print an int64 in the half-open interval [0, 100). + fmt.Println(rand.N(int64(100))) + + // Sleep for a random duration between 0 and 100 milliseconds. + time.Sleep(rand.N(100 * time.Millisecond)) +} + +func ExampleShuffle() { + words := strings.Fields("ink runs from the corners of my mouth") + rand.Shuffle(len(words), func(i, j int) { + words[i], words[j] = words[j], words[i] + }) + fmt.Println(words) +} + +func ExampleShuffle_slicesInUnison() { + numbers := []byte("12345") + letters := []byte("ABCDE") + // Shuffle numbers, swapping corresponding entries in letters at the same time. + rand.Shuffle(len(numbers), func(i, j int) { + numbers[i], numbers[j] = numbers[j], numbers[i] + letters[i], letters[j] = letters[j], letters[i] + }) + for i := range numbers { + fmt.Printf("%c: %c\n", letters[i], numbers[i]) + } +} + +func ExampleIntN() { + fmt.Println(rand.IntN(100)) + fmt.Println(rand.IntN(100)) + fmt.Println(rand.IntN(100)) +} diff --git a/src/math/rand/v2/exp.go b/src/math/rand/v2/exp.go new file mode 100644 index 0000000..ed7f727 --- /dev/null +++ b/src/math/rand/v2/exp.go @@ -0,0 +1,222 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand + +import ( + "math" +) + +/* + * Exponential distribution + * + * See "The Ziggurat Method for Generating Random Variables" + * (Marsaglia & Tsang, 2000) + * https://www.jstatsoft.org/v05/i08/paper [pdf] + */ + +const ( + re = 7.69711747013104972 +) + +// ExpFloat64 returns an exponentially distributed float64 in the range +// (0, +math.MaxFloat64] with an exponential distribution whose rate parameter +// (lambda) is 1 and whose mean is 1/lambda (1). +// To produce a distribution with a different rate parameter, +// callers can adjust the output using: +// +// sample = ExpFloat64() / desiredRateParameter +func (r *Rand) ExpFloat64() float64 { + for { + u := r.Uint64() + j := uint32(u) + i := uint8(u >> 32) + x := float64(j) * float64(we[i]) + if j < ke[i] { + return x + } + if i == 0 { + return re - math.Log(r.Float64()) + } + if fe[i]+float32(r.Float64())*(fe[i-1]-fe[i]) < float32(math.Exp(-x)) { + return x + } + } +} + +var ke = [256]uint32{ + 0xe290a139, 0x0, 0x9beadebc, 0xc377ac71, 0xd4ddb990, + 0xde893fb8, 0xe4a8e87c, 0xe8dff16a, 0xebf2deab, 0xee49a6e8, + 0xf0204efd, 0xf19bdb8e, 0xf2d458bb, 0xf3da104b, 0xf4b86d78, + 0xf577ad8a, 0xf61de83d, 0xf6afb784, 0xf730a573, 0xf7a37651, + 0xf80a5bb6, 0xf867189d, 0xf8bb1b4f, 0xf9079062, 0xf94d70ca, + 0xf98d8c7d, 0xf9c8928a, 0xf9ff175b, 0xfa319996, 0xfa6085f8, + 0xfa8c3a62, 0xfab5084e, 0xfadb36c8, 0xfaff0410, 0xfb20a6ea, + 0xfb404fb4, 0xfb5e2951, 0xfb7a59e9, 0xfb95038c, 0xfbae44ba, + 0xfbc638d8, 0xfbdcf892, 0xfbf29a30, 0xfc0731df, 0xfc1ad1ed, + 0xfc2d8b02, 0xfc3f6c4d, 0xfc5083ac, 0xfc60ddd1, 0xfc708662, + 0xfc7f8810, 0xfc8decb4, 0xfc9bbd62, 0xfca9027c, 0xfcb5c3c3, + 0xfcc20864, 0xfccdd70a, 0xfcd935e3, 0xfce42ab0, 0xfceebace, + 0xfcf8eb3b, 0xfd02c0a0, 0xfd0c3f59, 0xfd156b7b, 0xfd1e48d6, + 0xfd26daff, 0xfd2f2552, 0xfd372af7, 0xfd3eeee5, 0xfd4673e7, + 0xfd4dbc9e, 0xfd54cb85, 0xfd5ba2f2, 0xfd62451b, 0xfd68b415, + 0xfd6ef1da, 0xfd750047, 0xfd7ae120, 0xfd809612, 0xfd8620b4, + 0xfd8b8285, 0xfd90bcf5, 0xfd95d15e, 0xfd9ac10b, 0xfd9f8d36, + 0xfda43708, 0xfda8bf9e, 0xfdad2806, 0xfdb17141, 0xfdb59c46, + 0xfdb9a9fd, 0xfdbd9b46, 0xfdc170f6, 0xfdc52bd8, 0xfdc8ccac, + 0xfdcc542d, 0xfdcfc30b, 0xfdd319ef, 0xfdd6597a, 0xfdd98245, + 0xfddc94e5, 0xfddf91e6, 0xfde279ce, 0xfde54d1f, 0xfde80c52, + 0xfdeab7de, 0xfded5034, 0xfdefd5be, 0xfdf248e3, 0xfdf4aa06, + 0xfdf6f984, 0xfdf937b6, 0xfdfb64f4, 0xfdfd818d, 0xfdff8dd0, + 0xfe018a08, 0xfe03767a, 0xfe05536c, 0xfe07211c, 0xfe08dfc9, + 0xfe0a8fab, 0xfe0c30fb, 0xfe0dc3ec, 0xfe0f48b1, 0xfe10bf76, + 0xfe122869, 0xfe1383b4, 0xfe14d17c, 0xfe1611e7, 0xfe174516, + 0xfe186b2a, 0xfe19843e, 0xfe1a9070, 0xfe1b8fd6, 0xfe1c8289, + 0xfe1d689b, 0xfe1e4220, 0xfe1f0f26, 0xfe1fcfbc, 0xfe2083ed, + 0xfe212bc3, 0xfe21c745, 0xfe225678, 0xfe22d95f, 0xfe234ffb, + 0xfe23ba4a, 0xfe241849, 0xfe2469f2, 0xfe24af3c, 0xfe24e81e, + 0xfe25148b, 0xfe253474, 0xfe2547c7, 0xfe254e70, 0xfe25485a, + 0xfe25356a, 0xfe251586, 0xfe24e88f, 0xfe24ae64, 0xfe2466e1, + 0xfe2411df, 0xfe23af34, 0xfe233eb4, 0xfe22c02c, 0xfe22336b, + 0xfe219838, 0xfe20ee58, 0xfe20358c, 0xfe1f6d92, 0xfe1e9621, + 0xfe1daef0, 0xfe1cb7ac, 0xfe1bb002, 0xfe1a9798, 0xfe196e0d, + 0xfe1832fd, 0xfe16e5fe, 0xfe15869d, 0xfe141464, 0xfe128ed3, + 0xfe10f565, 0xfe0f478c, 0xfe0d84b1, 0xfe0bac36, 0xfe09bd73, + 0xfe07b7b5, 0xfe059a40, 0xfe03644c, 0xfe011504, 0xfdfeab88, + 0xfdfc26e9, 0xfdf98629, 0xfdf6c83b, 0xfdf3ec01, 0xfdf0f04a, + 0xfdedd3d1, 0xfdea953d, 0xfde7331e, 0xfde3abe9, 0xfddffdfb, + 0xfddc2791, 0xfdd826cd, 0xfdd3f9a8, 0xfdcf9dfc, 0xfdcb1176, + 0xfdc65198, 0xfdc15bb3, 0xfdbc2ce2, 0xfdb6c206, 0xfdb117be, + 0xfdab2a63, 0xfda4f5fd, 0xfd9e7640, 0xfd97a67a, 0xfd908192, + 0xfd8901f2, 0xfd812182, 0xfd78d98e, 0xfd7022bb, 0xfd66f4ed, + 0xfd5d4732, 0xfd530f9c, 0xfd48432b, 0xfd3cd59a, 0xfd30b936, + 0xfd23dea4, 0xfd16349e, 0xfd07a7a3, 0xfcf8219b, 0xfce7895b, + 0xfcd5c220, 0xfcc2aadb, 0xfcae1d5e, 0xfc97ed4e, 0xfc7fe6d4, + 0xfc65ccf3, 0xfc495762, 0xfc2a2fc8, 0xfc07ee19, 0xfbe213c1, + 0xfbb8051a, 0xfb890078, 0xfb5411a5, 0xfb180005, 0xfad33482, + 0xfa839276, 0xfa263b32, 0xf9b72d1c, 0xf930a1a2, 0xf889f023, + 0xf7b577d2, 0xf69c650c, 0xf51530f0, 0xf2cb0e3c, 0xeeefb15d, + 0xe6da6ecf, +} +var we = [256]float32{ + 2.0249555e-09, 1.486674e-11, 2.4409617e-11, 3.1968806e-11, + 3.844677e-11, 4.4228204e-11, 4.9516443e-11, 5.443359e-11, + 5.905944e-11, 6.344942e-11, 6.7643814e-11, 7.1672945e-11, + 7.556032e-11, 7.932458e-11, 8.298079e-11, 8.654132e-11, + 9.0016515e-11, 9.3415074e-11, 9.674443e-11, 1.0001099e-10, + 1.03220314e-10, 1.06377254e-10, 1.09486115e-10, 1.1255068e-10, + 1.1557435e-10, 1.1856015e-10, 1.2151083e-10, 1.2442886e-10, + 1.2731648e-10, 1.3017575e-10, 1.3300853e-10, 1.3581657e-10, + 1.3860142e-10, 1.4136457e-10, 1.4410738e-10, 1.4683108e-10, + 1.4953687e-10, 1.5222583e-10, 1.54899e-10, 1.5755733e-10, + 1.6020171e-10, 1.6283301e-10, 1.6545203e-10, 1.6805951e-10, + 1.7065617e-10, 1.732427e-10, 1.7581973e-10, 1.7838787e-10, + 1.8094774e-10, 1.8349985e-10, 1.8604476e-10, 1.8858298e-10, + 1.9111498e-10, 1.9364126e-10, 1.9616223e-10, 1.9867835e-10, + 2.0119004e-10, 2.0369768e-10, 2.0620168e-10, 2.087024e-10, + 2.1120022e-10, 2.136955e-10, 2.1618855e-10, 2.1867974e-10, + 2.2116936e-10, 2.2365775e-10, 2.261452e-10, 2.2863202e-10, + 2.311185e-10, 2.3360494e-10, 2.360916e-10, 2.3857874e-10, + 2.4106667e-10, 2.4355562e-10, 2.4604588e-10, 2.485377e-10, + 2.5103128e-10, 2.5352695e-10, 2.560249e-10, 2.585254e-10, + 2.6102867e-10, 2.6353494e-10, 2.6604446e-10, 2.6855745e-10, + 2.7107416e-10, 2.7359479e-10, 2.761196e-10, 2.7864877e-10, + 2.8118255e-10, 2.8372119e-10, 2.8626485e-10, 2.888138e-10, + 2.9136826e-10, 2.939284e-10, 2.9649452e-10, 2.9906677e-10, + 3.016454e-10, 3.0423064e-10, 3.0682268e-10, 3.0942177e-10, + 3.1202813e-10, 3.1464195e-10, 3.1726352e-10, 3.19893e-10, + 3.2253064e-10, 3.251767e-10, 3.2783135e-10, 3.3049485e-10, + 3.3316744e-10, 3.3584938e-10, 3.3854083e-10, 3.4124212e-10, + 3.4395342e-10, 3.46675e-10, 3.4940711e-10, 3.5215003e-10, + 3.5490397e-10, 3.5766917e-10, 3.6044595e-10, 3.6323455e-10, + 3.660352e-10, 3.6884823e-10, 3.7167386e-10, 3.745124e-10, + 3.773641e-10, 3.802293e-10, 3.8310827e-10, 3.860013e-10, + 3.8890866e-10, 3.918307e-10, 3.9476775e-10, 3.9772008e-10, + 4.0068804e-10, 4.0367196e-10, 4.0667217e-10, 4.09689e-10, + 4.1272286e-10, 4.1577405e-10, 4.1884296e-10, 4.2192994e-10, + 4.250354e-10, 4.281597e-10, 4.313033e-10, 4.3446652e-10, + 4.3764986e-10, 4.408537e-10, 4.4407847e-10, 4.4732465e-10, + 4.5059267e-10, 4.5388301e-10, 4.571962e-10, 4.6053267e-10, + 4.6389292e-10, 4.6727755e-10, 4.70687e-10, 4.741219e-10, + 4.7758275e-10, 4.810702e-10, 4.845848e-10, 4.8812715e-10, + 4.9169796e-10, 4.9529775e-10, 4.989273e-10, 5.0258725e-10, + 5.0627835e-10, 5.100013e-10, 5.1375687e-10, 5.1754584e-10, + 5.21369e-10, 5.2522725e-10, 5.2912136e-10, 5.330522e-10, + 5.370208e-10, 5.4102806e-10, 5.45075e-10, 5.491625e-10, + 5.532918e-10, 5.5746385e-10, 5.616799e-10, 5.6594107e-10, + 5.7024857e-10, 5.746037e-10, 5.7900773e-10, 5.834621e-10, + 5.8796823e-10, 5.925276e-10, 5.971417e-10, 6.018122e-10, + 6.065408e-10, 6.113292e-10, 6.1617933e-10, 6.2109295e-10, + 6.260722e-10, 6.3111916e-10, 6.3623595e-10, 6.4142497e-10, + 6.4668854e-10, 6.5202926e-10, 6.5744976e-10, 6.6295286e-10, + 6.6854156e-10, 6.742188e-10, 6.79988e-10, 6.858526e-10, + 6.9181616e-10, 6.978826e-10, 7.04056e-10, 7.103407e-10, + 7.167412e-10, 7.2326256e-10, 7.2990985e-10, 7.366886e-10, + 7.4360473e-10, 7.5066453e-10, 7.5787476e-10, 7.6524265e-10, + 7.7277595e-10, 7.80483e-10, 7.883728e-10, 7.9645507e-10, + 8.047402e-10, 8.1323964e-10, 8.219657e-10, 8.309319e-10, + 8.401528e-10, 8.496445e-10, 8.594247e-10, 8.6951274e-10, + 8.799301e-10, 8.9070046e-10, 9.018503e-10, 9.134092e-10, + 9.254101e-10, 9.378904e-10, 9.508923e-10, 9.644638e-10, + 9.786603e-10, 9.935448e-10, 1.0091913e-09, 1.025686e-09, + 1.0431306e-09, 1.0616465e-09, 1.08138e-09, 1.1025096e-09, + 1.1252564e-09, 1.1498986e-09, 1.1767932e-09, 1.206409e-09, + 1.2393786e-09, 1.276585e-09, 1.3193139e-09, 1.3695435e-09, + 1.4305498e-09, 1.508365e-09, 1.6160854e-09, 1.7921248e-09, +} +var fe = [256]float32{ + 1, 0.9381437, 0.90046996, 0.87170434, 0.8477855, 0.8269933, + 0.8084217, 0.7915276, 0.77595687, 0.7614634, 0.7478686, + 0.7350381, 0.72286767, 0.71127474, 0.70019263, 0.6895665, + 0.67935055, 0.6695063, 0.66000086, 0.65080583, 0.6418967, + 0.63325197, 0.6248527, 0.6166822, 0.60872537, 0.60096896, + 0.5934009, 0.58601034, 0.5787874, 0.57172304, 0.5648092, + 0.5580383, 0.5514034, 0.5448982, 0.5385169, 0.53225386, + 0.5261042, 0.52006316, 0.5141264, 0.50828975, 0.5025495, + 0.496902, 0.49134386, 0.485872, 0.48048335, 0.4751752, + 0.46994483, 0.46478975, 0.45970762, 0.45469615, 0.44975325, + 0.44487688, 0.44006512, 0.43531612, 0.43062815, 0.42599955, + 0.42142874, 0.4169142, 0.41245446, 0.40804818, 0.403694, + 0.3993907, 0.39513698, 0.39093173, 0.38677382, 0.38266218, + 0.37859577, 0.37457356, 0.37059465, 0.3666581, 0.362763, + 0.35890847, 0.35509375, 0.351318, 0.3475805, 0.34388044, + 0.34021714, 0.3365899, 0.33299807, 0.32944095, 0.32591796, + 0.3224285, 0.3189719, 0.31554767, 0.31215525, 0.30879408, + 0.3054636, 0.3021634, 0.29889292, 0.2956517, 0.29243928, + 0.28925523, 0.28609908, 0.28297043, 0.27986884, 0.27679393, + 0.2737453, 0.2707226, 0.2677254, 0.26475343, 0.26180625, + 0.25888354, 0.25598502, 0.2531103, 0.25025907, 0.24743107, + 0.24462597, 0.24184346, 0.23908329, 0.23634516, 0.23362878, + 0.23093392, 0.2282603, 0.22560766, 0.22297576, 0.22036438, + 0.21777324, 0.21520215, 0.21265087, 0.21011916, 0.20760682, + 0.20511365, 0.20263945, 0.20018397, 0.19774707, 0.19532852, + 0.19292815, 0.19054577, 0.1881812, 0.18583426, 0.18350479, + 0.1811926, 0.17889754, 0.17661946, 0.17435817, 0.17211354, + 0.1698854, 0.16767362, 0.16547804, 0.16329853, 0.16113494, + 0.15898713, 0.15685499, 0.15473837, 0.15263714, 0.15055119, + 0.14848037, 0.14642459, 0.14438373, 0.14235765, 0.14034624, + 0.13834943, 0.13636707, 0.13439907, 0.13244532, 0.13050574, + 0.1285802, 0.12666863, 0.12477092, 0.12288698, 0.12101672, + 0.119160056, 0.1173169, 0.115487166, 0.11367077, 0.11186763, + 0.11007768, 0.10830083, 0.10653701, 0.10478614, 0.10304816, + 0.101323, 0.09961058, 0.09791085, 0.09622374, 0.09454919, + 0.09288713, 0.091237515, 0.08960028, 0.087975375, 0.08636274, + 0.08476233, 0.083174095, 0.081597984, 0.08003395, 0.07848195, + 0.076941945, 0.07541389, 0.07389775, 0.072393484, 0.07090106, + 0.069420435, 0.06795159, 0.066494495, 0.06504912, 0.063615434, + 0.062193416, 0.060783047, 0.059384305, 0.057997175, + 0.05662164, 0.05525769, 0.053905312, 0.052564494, 0.051235236, + 0.049917534, 0.048611384, 0.047316793, 0.046033762, 0.0447623, + 0.043502413, 0.042254124, 0.041017443, 0.039792392, + 0.038578995, 0.037377283, 0.036187284, 0.035009038, + 0.033842582, 0.032687962, 0.031545233, 0.030414443, 0.02929566, + 0.02818895, 0.027094385, 0.026012046, 0.024942026, 0.023884421, + 0.022839336, 0.021806888, 0.020787204, 0.019780423, 0.0187867, + 0.0178062, 0.016839107, 0.015885621, 0.014945968, 0.014020392, + 0.013109165, 0.012212592, 0.011331013, 0.01046481, 0.009614414, + 0.008780315, 0.007963077, 0.0071633533, 0.006381906, + 0.0056196423, 0.0048776558, 0.004157295, 0.0034602648, + 0.0027887989, 0.0021459677, 0.0015362998, 0.0009672693, + 0.00045413437, +} diff --git a/src/math/rand/v2/export_test.go b/src/math/rand/v2/export_test.go new file mode 100644 index 0000000..16ecb20 --- /dev/null +++ b/src/math/rand/v2/export_test.go @@ -0,0 +1,13 @@ +// Copyright 2021 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand + +func GetNormalDistributionParameters() (float64, [128]uint32, [128]float32, [128]float32) { + return rn, kn, wn, fn +} + +func GetExponentialDistributionParameters() (float64, [256]uint32, [256]float32, [256]float32) { + return re, ke, we, fe +} diff --git a/src/math/rand/v2/normal.go b/src/math/rand/v2/normal.go new file mode 100644 index 0000000..ea1ae40 --- /dev/null +++ b/src/math/rand/v2/normal.go @@ -0,0 +1,157 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand + +import ( + "math" +) + +/* + * Normal distribution + * + * See "The Ziggurat Method for Generating Random Variables" + * (Marsaglia & Tsang, 2000) + * http://www.jstatsoft.org/v05/i08/paper [pdf] + */ + +const ( + rn = 3.442619855899 +) + +func absInt32(i int32) uint32 { + if i < 0 { + return uint32(-i) + } + return uint32(i) +} + +// NormFloat64 returns a normally distributed float64 in +// the range -math.MaxFloat64 through +math.MaxFloat64 inclusive, +// with standard normal distribution (mean = 0, stddev = 1). +// To produce a different normal distribution, callers can +// adjust the output using: +// +// sample = NormFloat64() * desiredStdDev + desiredMean +func (r *Rand) NormFloat64() float64 { + for { + u := r.Uint64() + j := int32(u) // Possibly negative + i := u >> 32 & 0x7F + x := float64(j) * float64(wn[i]) + if absInt32(j) < kn[i] { + // This case should be hit better than 99% of the time. + return x + } + + if i == 0 { + // This extra work is only required for the base strip. + for { + x = -math.Log(r.Float64()) * (1.0 / rn) + y := -math.Log(r.Float64()) + if y+y >= x*x { + break + } + } + if j > 0 { + return rn + x + } + return -rn - x + } + if fn[i]+float32(r.Float64())*(fn[i-1]-fn[i]) < float32(math.Exp(-.5*x*x)) { + return x + } + } +} + +var kn = [128]uint32{ + 0x76ad2212, 0x0, 0x600f1b53, 0x6ce447a6, 0x725b46a2, + 0x7560051d, 0x774921eb, 0x789a25bd, 0x799045c3, 0x7a4bce5d, + 0x7adf629f, 0x7b5682a6, 0x7bb8a8c6, 0x7c0ae722, 0x7c50cce7, + 0x7c8cec5b, 0x7cc12cd6, 0x7ceefed2, 0x7d177e0b, 0x7d3b8883, + 0x7d5bce6c, 0x7d78dd64, 0x7d932886, 0x7dab0e57, 0x7dc0dd30, + 0x7dd4d688, 0x7de73185, 0x7df81cea, 0x7e07c0a3, 0x7e163efa, + 0x7e23b587, 0x7e303dfd, 0x7e3beec2, 0x7e46db77, 0x7e51155d, + 0x7e5aabb3, 0x7e63abf7, 0x7e6c222c, 0x7e741906, 0x7e7b9a18, + 0x7e82adfa, 0x7e895c63, 0x7e8fac4b, 0x7e95a3fb, 0x7e9b4924, + 0x7ea0a0ef, 0x7ea5b00d, 0x7eaa7ac3, 0x7eaf04f3, 0x7eb3522a, + 0x7eb765a5, 0x7ebb4259, 0x7ebeeafd, 0x7ec2620a, 0x7ec5a9c4, + 0x7ec8c441, 0x7ecbb365, 0x7ece78ed, 0x7ed11671, 0x7ed38d62, + 0x7ed5df12, 0x7ed80cb4, 0x7eda175c, 0x7edc0005, 0x7eddc78e, + 0x7edf6ebf, 0x7ee0f647, 0x7ee25ebe, 0x7ee3a8a9, 0x7ee4d473, + 0x7ee5e276, 0x7ee6d2f5, 0x7ee7a620, 0x7ee85c10, 0x7ee8f4cd, + 0x7ee97047, 0x7ee9ce59, 0x7eea0eca, 0x7eea3147, 0x7eea3568, + 0x7eea1aab, 0x7ee9e071, 0x7ee98602, 0x7ee90a88, 0x7ee86d08, + 0x7ee7ac6a, 0x7ee6c769, 0x7ee5bc9c, 0x7ee48a67, 0x7ee32efc, + 0x7ee1a857, 0x7edff42f, 0x7ede0ffa, 0x7edbf8d9, 0x7ed9ab94, + 0x7ed7248d, 0x7ed45fae, 0x7ed1585c, 0x7ece095f, 0x7eca6ccb, + 0x7ec67be2, 0x7ec22eee, 0x7ebd7d1a, 0x7eb85c35, 0x7eb2c075, + 0x7eac9c20, 0x7ea5df27, 0x7e9e769f, 0x7e964c16, 0x7e8d44ba, + 0x7e834033, 0x7e781728, 0x7e6b9933, 0x7e5d8a1a, 0x7e4d9ded, + 0x7e3b737a, 0x7e268c2f, 0x7e0e3ff5, 0x7df1aa5d, 0x7dcf8c72, + 0x7da61a1e, 0x7d72a0fb, 0x7d30e097, 0x7cd9b4ab, 0x7c600f1a, + 0x7ba90bdc, 0x7a722176, 0x77d664e5, +} +var wn = [128]float32{ + 1.7290405e-09, 1.2680929e-10, 1.6897518e-10, 1.9862688e-10, + 2.2232431e-10, 2.4244937e-10, 2.601613e-10, 2.7611988e-10, + 2.9073963e-10, 3.042997e-10, 3.1699796e-10, 3.289802e-10, + 3.4035738e-10, 3.5121603e-10, 3.616251e-10, 3.7164058e-10, + 3.8130857e-10, 3.9066758e-10, 3.9975012e-10, 4.08584e-10, + 4.1719309e-10, 4.2559822e-10, 4.338176e-10, 4.418672e-10, + 4.497613e-10, 4.5751258e-10, 4.651324e-10, 4.7263105e-10, + 4.8001775e-10, 4.87301e-10, 4.944885e-10, 5.015873e-10, + 5.0860405e-10, 5.155446e-10, 5.2241467e-10, 5.2921934e-10, + 5.359635e-10, 5.426517e-10, 5.4928817e-10, 5.5587696e-10, + 5.624219e-10, 5.6892646e-10, 5.753941e-10, 5.818282e-10, + 5.882317e-10, 5.946077e-10, 6.00959e-10, 6.072884e-10, + 6.135985e-10, 6.19892e-10, 6.2617134e-10, 6.3243905e-10, + 6.386974e-10, 6.449488e-10, 6.511956e-10, 6.5744005e-10, + 6.6368433e-10, 6.699307e-10, 6.7618144e-10, 6.824387e-10, + 6.8870465e-10, 6.949815e-10, 7.012715e-10, 7.075768e-10, + 7.1389966e-10, 7.202424e-10, 7.266073e-10, 7.329966e-10, + 7.394128e-10, 7.4585826e-10, 7.5233547e-10, 7.58847e-10, + 7.653954e-10, 7.719835e-10, 7.7861395e-10, 7.852897e-10, + 7.920138e-10, 7.987892e-10, 8.0561924e-10, 8.125073e-10, + 8.194569e-10, 8.2647167e-10, 8.3355556e-10, 8.407127e-10, + 8.479473e-10, 8.55264e-10, 8.6266755e-10, 8.7016316e-10, + 8.777562e-10, 8.8545243e-10, 8.932582e-10, 9.0117996e-10, + 9.09225e-10, 9.174008e-10, 9.2571584e-10, 9.341788e-10, + 9.427997e-10, 9.515889e-10, 9.605579e-10, 9.697193e-10, + 9.790869e-10, 9.88676e-10, 9.985036e-10, 1.0085882e-09, + 1.0189509e-09, 1.0296151e-09, 1.0406069e-09, 1.0519566e-09, + 1.063698e-09, 1.0758702e-09, 1.0885183e-09, 1.1016947e-09, + 1.1154611e-09, 1.1298902e-09, 1.1450696e-09, 1.1611052e-09, + 1.1781276e-09, 1.1962995e-09, 1.2158287e-09, 1.2369856e-09, + 1.2601323e-09, 1.2857697e-09, 1.3146202e-09, 1.347784e-09, + 1.3870636e-09, 1.4357403e-09, 1.5008659e-09, 1.6030948e-09, +} +var fn = [128]float32{ + 1, 0.9635997, 0.9362827, 0.9130436, 0.89228165, 0.87324303, + 0.8555006, 0.8387836, 0.8229072, 0.8077383, 0.793177, + 0.7791461, 0.7655842, 0.7524416, 0.73967725, 0.7272569, + 0.7151515, 0.7033361, 0.69178915, 0.68049186, 0.6694277, + 0.658582, 0.6479418, 0.63749546, 0.6272325, 0.6171434, + 0.6072195, 0.5974532, 0.58783704, 0.5783647, 0.56903, + 0.5598274, 0.5507518, 0.54179835, 0.5329627, 0.52424055, + 0.5156282, 0.50712204, 0.49871865, 0.49041483, 0.48220766, + 0.4740943, 0.46607214, 0.4581387, 0.45029163, 0.44252872, + 0.43484783, 0.427247, 0.41972435, 0.41227803, 0.40490642, + 0.39760786, 0.3903808, 0.3832238, 0.37613547, 0.36911446, + 0.3621595, 0.35526937, 0.34844297, 0.34167916, 0.33497685, + 0.3283351, 0.3217529, 0.3152294, 0.30876362, 0.30235484, + 0.29600215, 0.28970486, 0.2834622, 0.2772735, 0.27113807, + 0.2650553, 0.25902456, 0.2530453, 0.24711695, 0.241239, + 0.23541094, 0.22963232, 0.2239027, 0.21822165, 0.21258877, + 0.20700371, 0.20146611, 0.19597565, 0.19053204, 0.18513499, + 0.17978427, 0.17447963, 0.1692209, 0.16400786, 0.15884037, + 0.15371831, 0.14864157, 0.14361008, 0.13862377, 0.13368265, + 0.12878671, 0.12393598, 0.119130544, 0.11437051, 0.10965602, + 0.104987256, 0.10036444, 0.095787846, 0.0912578, 0.08677467, + 0.0823389, 0.077950984, 0.073611505, 0.06932112, 0.06508058, + 0.06089077, 0.056752663, 0.0526674, 0.048636295, 0.044660863, + 0.040742867, 0.03688439, 0.033087887, 0.029356318, + 0.025693292, 0.022103304, 0.018592102, 0.015167298, + 0.011839478, 0.008624485, 0.005548995, 0.0026696292, +} diff --git a/src/math/rand/v2/pcg.go b/src/math/rand/v2/pcg.go new file mode 100644 index 0000000..77708d7 --- /dev/null +++ b/src/math/rand/v2/pcg.go @@ -0,0 +1,121 @@ +// Copyright 2023 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand + +import ( + "errors" + "math/bits" +) + +// https://numpy.org/devdocs/reference/random/upgrading-pcg64.html +// https://github.com/imneme/pcg-cpp/commit/871d0494ee9c9a7b7c43f753e3d8ca47c26f8005 + +// A PCG is a PCG generator with 128 bits of internal state. +// A zero PCG is equivalent to NewPCG(0, 0). +type PCG struct { + hi uint64 + lo uint64 +} + +// NewPCG returns a new PCG seeded with the given values. +func NewPCG(seed1, seed2 uint64) *PCG { + return &PCG{seed1, seed2} +} + +// Seed resets the PCG to behave the same way as NewPCG(seed1, seed2). +func (p *PCG) Seed(seed1, seed2 uint64) { + p.hi = seed1 + p.lo = seed2 +} + +// binary.bigEndian.Uint64, copied to avoid dependency +func beUint64(b []byte) uint64 { + _ = b[7] // bounds check hint to compiler; see golang.org/issue/14808 + return uint64(b[7]) | uint64(b[6])<<8 | uint64(b[5])<<16 | uint64(b[4])<<24 | + uint64(b[3])<<32 | uint64(b[2])<<40 | uint64(b[1])<<48 | uint64(b[0])<<56 +} + +// binary.bigEndian.PutUint64, copied to avoid dependency +func bePutUint64(b []byte, v uint64) { + _ = b[7] // early bounds check to guarantee safety of writes below + b[0] = byte(v >> 56) + b[1] = byte(v >> 48) + b[2] = byte(v >> 40) + b[3] = byte(v >> 32) + b[4] = byte(v >> 24) + b[5] = byte(v >> 16) + b[6] = byte(v >> 8) + b[7] = byte(v) +} + +// MarshalBinary implements the encoding.BinaryMarshaler interface. +func (p *PCG) MarshalBinary() ([]byte, error) { + b := make([]byte, 20) + copy(b, "pcg:") + bePutUint64(b[4:], p.hi) + bePutUint64(b[4+8:], p.lo) + return b, nil +} + +var errUnmarshalPCG = errors.New("invalid PCG encoding") + +// UnmarshalBinary implements the encoding.BinaryUnmarshaler interface. +func (p *PCG) UnmarshalBinary(data []byte) error { + if len(data) != 20 || string(data[:4]) != "pcg:" { + return errUnmarshalPCG + } + p.hi = beUint64(data[4:]) + p.lo = beUint64(data[4+8:]) + return nil +} + +func (p *PCG) next() (hi, lo uint64) { + // https://github.com/imneme/pcg-cpp/blob/428802d1a5/include/pcg_random.hpp#L161 + // + // Numpy's PCG multiplies by the 64-bit value cheapMul + // instead of the 128-bit value used here and in the official PCG code. + // This does not seem worthwhile, at least for Go: not having any high + // bits in the multiplier reduces the effect of low bits on the highest bits, + // and it only saves 1 multiply out of 3. + // (On 32-bit systems, it saves 1 out of 6, since Mul64 is doing 4.) + const ( + mulHi = 2549297995355413924 + mulLo = 4865540595714422341 + incHi = 6364136223846793005 + incLo = 1442695040888963407 + ) + + // state = state * mul + inc + hi, lo = bits.Mul64(p.lo, mulLo) + hi += p.hi*mulLo + p.lo*mulHi + lo, c := bits.Add64(lo, incLo, 0) + hi, _ = bits.Add64(hi, incHi, c) + p.lo = lo + p.hi = hi + return hi, lo +} + +// Uint64 return a uniformly-distributed random uint64 value. +func (p *PCG) Uint64() uint64 { + hi, lo := p.next() + + // XSL-RR would be + // hi, lo := p.next() + // return bits.RotateLeft64(lo^hi, -int(hi>>58)) + // but Numpy uses DXSM and O'Neill suggests doing the same. + // See https://github.com/golang/go/issues/21835#issuecomment-739065688 + // and following comments. + + // DXSM "double xorshift multiply" + // https://github.com/imneme/pcg-cpp/blob/428802d1a5/include/pcg_random.hpp#L1015 + + // https://github.com/imneme/pcg-cpp/blob/428802d1a5/include/pcg_random.hpp#L176 + const cheapMul = 0xda942042e4dd58b5 + hi ^= hi >> 32 + hi *= cheapMul + hi ^= hi >> 48 + hi *= (lo | 1) + return hi +} diff --git a/src/math/rand/v2/pcg_test.go b/src/math/rand/v2/pcg_test.go new file mode 100644 index 0000000..db866c8 --- /dev/null +++ b/src/math/rand/v2/pcg_test.go @@ -0,0 +1,79 @@ +// Copyright 2023 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand_test + +import ( + . "math/rand/v2" + "testing" +) + +func BenchmarkPCG_DXSM(b *testing.B) { + var p PCG + var t uint64 + for n := b.N; n > 0; n-- { + t += p.Uint64() + } + Sink = t +} + +func TestPCGMarshal(t *testing.T) { + var p PCG + const ( + seed1 = 0x123456789abcdef0 + seed2 = 0xfedcba9876543210 + want = "pcg:\x12\x34\x56\x78\x9a\xbc\xde\xf0\xfe\xdc\xba\x98\x76\x54\x32\x10" + ) + p.Seed(seed1, seed2) + data, err := p.MarshalBinary() + if string(data) != want || err != nil { + t.Errorf("MarshalBinary() = %q, %v, want %q, nil", data, err, want) + } + + q := PCG{} + if err := q.UnmarshalBinary([]byte(want)); err != nil { + t.Fatalf("UnmarshalBinary(): %v", err) + } + if q != p { + t.Fatalf("after round trip, q = %#x, but p = %#x", q, p) + } + + qu := q.Uint64() + pu := p.Uint64() + if qu != pu { + t.Errorf("after round trip, q.Uint64() = %#x, but p.Uint64() = %#x", qu, pu) + } +} + +func TestPCG(t *testing.T) { + p := NewPCG(1, 2) + want := []uint64{ + 0xc4f5a58656eef510, + 0x9dcec3ad077dec6c, + 0xc8d04605312f8088, + 0xcbedc0dcb63ac19a, + 0x3bf98798cae97950, + 0xa8c6d7f8d485abc, + 0x7ffa3780429cd279, + 0x730ad2626b1c2f8e, + 0x21ff2330f4a0ad99, + 0x2f0901a1947094b0, + 0xa9735a3cfbe36cef, + 0x71ddb0a01a12c84a, + 0xf0e53e77a78453bb, + 0x1f173e9663be1e9d, + 0x657651da3ac4115e, + 0xc8987376b65a157b, + 0xbb17008f5fca28e7, + 0x8232bd645f29ed22, + 0x12be8f07ad14c539, + 0x54908a48e8e4736e, + } + + for i, x := range want { + if u := p.Uint64(); u != x { + t.Errorf("PCG #%d = %#x, want %#x", i, u, x) + } + } +} diff --git a/src/math/rand/v2/race_test.go b/src/math/rand/v2/race_test.go new file mode 100644 index 0000000..5ab7a21 --- /dev/null +++ b/src/math/rand/v2/race_test.go @@ -0,0 +1,44 @@ +// Copyright 2016 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand_test + +import ( + . "math/rand/v2" + "sync" + "testing" +) + +// TestConcurrent exercises the rand API concurrently, triggering situations +// where the race detector is likely to detect issues. +func TestConcurrent(t *testing.T) { + const ( + numRoutines = 10 + numCycles = 10 + ) + var wg sync.WaitGroup + defer wg.Wait() + wg.Add(numRoutines) + for i := 0; i < numRoutines; i++ { + go func(i int) { + defer wg.Done() + var seed int64 + for j := 0; j < numCycles; j++ { + seed += int64(ExpFloat64()) + seed += int64(Float32()) + seed += int64(Float64()) + seed += int64(IntN(Int())) + seed += int64(Int32N(Int32())) + seed += int64(Int64N(Int64())) + seed += int64(NormFloat64()) + seed += int64(Uint32()) + seed += int64(Uint64()) + for _, p := range Perm(10) { + seed += int64(p) + } + } + _ = seed + }(i) + } +} diff --git a/src/math/rand/v2/rand.go b/src/math/rand/v2/rand.go new file mode 100644 index 0000000..f490408 --- /dev/null +++ b/src/math/rand/v2/rand.go @@ -0,0 +1,363 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package rand implements pseudo-random number generators suitable for tasks +// such as simulation, but it should not be used for security-sensitive work. +// +// Random numbers are generated by a [Source], usually wrapped in a [Rand]. +// Both types should be used by a single goroutine at a time: sharing among +// multiple goroutines requires some kind of synchronization. +// +// Top-level functions, such as [Float64] and [Int], +// are safe for concurrent use by multiple goroutines. +// +// This package's outputs might be easily predictable regardless of how it's +// seeded. For random numbers suitable for security-sensitive work, see the +// crypto/rand package. +package rand + +import ( + "math/bits" + _ "unsafe" // for go:linkname +) + +// A Source is a source of uniformly-distributed +// pseudo-random uint64 values in the range [0, 1<<64). +// +// A Source is not safe for concurrent use by multiple goroutines. +type Source interface { + Uint64() uint64 +} + +// A Rand is a source of random numbers. +type Rand struct { + src Source +} + +// New returns a new Rand that uses random values from src +// to generate other random values. +func New(src Source) *Rand { + return &Rand{src: src} +} + +// Int64 returns a non-negative pseudo-random 63-bit integer as an int64. +func (r *Rand) Int64() int64 { return int64(r.src.Uint64() &^ (1 << 63)) } + +// Uint32 returns a pseudo-random 32-bit value as a uint32. +func (r *Rand) Uint32() uint32 { return uint32(r.src.Uint64() >> 32) } + +// Uint64 returns a pseudo-random 64-bit value as a uint64. +func (r *Rand) Uint64() uint64 { return r.src.Uint64() } + +// Int32 returns a non-negative pseudo-random 31-bit integer as an int32. +func (r *Rand) Int32() int32 { return int32(r.src.Uint64() >> 33) } + +// Int returns a non-negative pseudo-random int. +func (r *Rand) Int() int { return int(uint(r.src.Uint64()) << 1 >> 1) } + +// Int64N returns, as an int64, a non-negative pseudo-random number in the half-open interval [0,n). +// It panics if n <= 0. +func (r *Rand) Int64N(n int64) int64 { + if n <= 0 { + panic("invalid argument to Int64N") + } + return int64(r.uint64n(uint64(n))) +} + +// Uint64N returns, as a uint64, a non-negative pseudo-random number in the half-open interval [0,n). +// It panics if n == 0. +func (r *Rand) Uint64N(n uint64) uint64 { + if n == 0 { + panic("invalid argument to Uint64N") + } + return r.uint64n(n) +} + +// uint64n is the no-bounds-checks version of Uint64N. +func (r *Rand) uint64n(n uint64) uint64 { + if is32bit && uint64(uint32(n)) == n { + return uint64(r.uint32n(uint32(n))) + } + if n&(n-1) == 0 { // n is power of two, can mask + return r.Uint64() & (n - 1) + } + + // Suppose we have a uint64 x uniform in the range [0,2⁶⁴) + // and want to reduce it to the range [0,n) preserving exact uniformity. + // We can simulate a scaling arbitrary precision x * (n/2⁶⁴) by + // the high bits of a double-width multiply of x*n, meaning (x*n)/2⁶⁴. + // Since there are 2⁶⁴ possible inputs x and only n possible outputs, + // the output is necessarily biased if n does not divide 2⁶⁴. + // In general (x*n)/2⁶⁴ = k for x*n in [k*2⁶⁴,(k+1)*2⁶⁴). + // There are either floor(2⁶⁴/n) or ceil(2⁶⁴/n) possible products + // in that range, depending on k. + // But suppose we reject the sample and try again when + // x*n is in [k*2⁶⁴, k*2⁶⁴+(2⁶⁴%n)), meaning rejecting fewer than n possible + // outcomes out of the 2⁶⁴. + // Now there are exactly floor(2⁶⁴/n) possible ways to produce + // each output value k, so we've restored uniformity. + // To get valid uint64 math, 2⁶⁴ % n = (2⁶⁴ - n) % n = -n % n, + // so the direct implementation of this algorithm would be: + // + // hi, lo := bits.Mul64(r.Uint64(), n) + // thresh := -n % n + // for lo < thresh { + // hi, lo = bits.Mul64(r.Uint64(), n) + // } + // + // That still leaves an expensive 64-bit division that we would rather avoid. + // We know that thresh < n, and n is usually much less than 2⁶⁴, so we can + // avoid the last four lines unless lo < n. + // + // See also: + // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction + // https://lemire.me/blog/2016/06/30/fast-random-shuffling + hi, lo := bits.Mul64(r.Uint64(), n) + if lo < n { + thresh := -n % n + for lo < thresh { + hi, lo = bits.Mul64(r.Uint64(), n) + } + } + return hi +} + +// uint32n is an identical computation to uint64n +// but optimized for 32-bit systems. +func (r *Rand) uint32n(n uint32) uint32 { + if n&(n-1) == 0 { // n is power of two, can mask + return uint32(r.Uint64()) & (n - 1) + } + // On 64-bit systems we still use the uint64 code below because + // the probability of a random uint64 lo being < a uint32 n is near zero, + // meaning the unbiasing loop almost never runs. + // On 32-bit systems, here we need to implement that same logic in 32-bit math, + // both to preserve the exact output sequence observed on 64-bit machines + // and to preserve the optimization that the unbiasing loop almost never runs. + // + // We want to compute + // hi, lo := bits.Mul64(r.Uint64(), n) + // In terms of 32-bit halves, this is: + // x1:x0 := r.Uint64() + // 0:hi, lo1:lo0 := bits.Mul64(x1:x0, 0:n) + // Writing out the multiplication in terms of bits.Mul32 allows + // using direct hardware instructions and avoiding + // the computations involving these zeros. + x := r.Uint64() + lo1a, lo0 := bits.Mul32(uint32(x), n) + hi, lo1b := bits.Mul32(uint32(x>>32), n) + lo1, c := bits.Add32(lo1a, lo1b, 0) + hi += c + if lo1 == 0 && lo0 < uint32(n) { + n64 := uint64(n) + thresh := uint32(-n64 % n64) + for lo1 == 0 && lo0 < thresh { + x := r.Uint64() + lo1a, lo0 = bits.Mul32(uint32(x), n) + hi, lo1b = bits.Mul32(uint32(x>>32), n) + lo1, c = bits.Add32(lo1a, lo1b, 0) + hi += c + } + } + return hi +} + +// Int32N returns, as an int32, a non-negative pseudo-random number in the half-open interval [0,n). +// It panics if n <= 0. +func (r *Rand) Int32N(n int32) int32 { + if n <= 0 { + panic("invalid argument to Int32N") + } + return int32(r.uint64n(uint64(n))) +} + +// Uint32N returns, as a uint32, a non-negative pseudo-random number in the half-open interval [0,n). +// It panics if n == 0. +func (r *Rand) Uint32N(n uint32) uint32 { + if n == 0 { + panic("invalid argument to Uint32N") + } + return uint32(r.uint64n(uint64(n))) +} + +const is32bit = ^uint(0)>>32 == 0 + +// IntN returns, as an int, a non-negative pseudo-random number in the half-open interval [0,n). +// It panics if n <= 0. +func (r *Rand) IntN(n int) int { + if n <= 0 { + panic("invalid argument to IntN") + } + return int(r.uint64n(uint64(n))) +} + +// UintN returns, as a uint, a non-negative pseudo-random number in the half-open interval [0,n). +// It panics if n == 0. +func (r *Rand) UintN(n uint) uint { + if n == 0 { + panic("invalid argument to UintN") + } + return uint(r.uint64n(uint64(n))) +} + +// Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0). +func (r *Rand) Float64() float64 { + // There are exactly 1<<53 float64s in [0,1). Use Intn(1<<53) / (1<<53). + return float64(r.Uint64()<<11>>11) / (1 << 53) +} + +// Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0). +func (r *Rand) Float32() float32 { + // There are exactly 1<<24 float32s in [0,1). Use Intn(1<<24) / (1<<24). + return float32(r.Uint32()<<8>>8) / (1 << 24) +} + +// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers +// in the half-open interval [0,n). +func (r *Rand) Perm(n int) []int { + p := make([]int, n) + for i := range p { + p[i] = i + } + r.Shuffle(len(p), func(i, j int) { p[i], p[j] = p[j], p[i] }) + return p +} + +// Shuffle pseudo-randomizes the order of elements. +// n is the number of elements. Shuffle panics if n < 0. +// swap swaps the elements with indexes i and j. +func (r *Rand) Shuffle(n int, swap func(i, j int)) { + if n < 0 { + panic("invalid argument to Shuffle") + } + + // Fisher-Yates shuffle: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle + // Shuffle really ought not be called with n that doesn't fit in 32 bits. + // Not only will it take a very long time, but with 2³¹! possible permutations, + // there's no way that any PRNG can have a big enough internal state to + // generate even a minuscule percentage of the possible permutations. + // Nevertheless, the right API signature accepts an int n, so handle it as best we can. + for i := n - 1; i > 0; i-- { + j := int(r.uint64n(uint64(i + 1))) + swap(i, j) + } +} + +/* + * Top-level convenience functions + */ + +// globalRand is the source of random numbers for the top-level +// convenience functions. +var globalRand = &Rand{src: &runtimeSource{}} + +//go:linkname runtime_rand runtime.rand +func runtime_rand() uint64 + +// runtimeSource is a Source that uses the runtime fastrand functions. +type runtimeSource struct{} + +func (*runtimeSource) Uint64() uint64 { + return runtime_rand() +} + +// Int64 returns a non-negative pseudo-random 63-bit integer as an int64 +// from the default Source. +func Int64() int64 { return globalRand.Int64() } + +// Uint32 returns a pseudo-random 32-bit value as a uint32 +// from the default Source. +func Uint32() uint32 { return globalRand.Uint32() } + +// Uint64N returns, as a uint64, a pseudo-random number in the half-open interval [0,n) +// from the default Source. +// It panics if n <= 0. +func Uint64N(n uint64) uint64 { return globalRand.Uint64N(n) } + +// Uint32N returns, as a uint32, a pseudo-random number in the half-open interval [0,n) +// from the default Source. +// It panics if n <= 0. +func Uint32N(n uint32) uint32 { return globalRand.Uint32N(n) } + +// Uint64 returns a pseudo-random 64-bit value as a uint64 +// from the default Source. +func Uint64() uint64 { return globalRand.Uint64() } + +// Int32 returns a non-negative pseudo-random 31-bit integer as an int32 +// from the default Source. +func Int32() int32 { return globalRand.Int32() } + +// Int returns a non-negative pseudo-random int from the default Source. +func Int() int { return globalRand.Int() } + +// Int64N returns, as an int64, a pseudo-random number in the half-open interval [0,n) +// from the default Source. +// It panics if n <= 0. +func Int64N(n int64) int64 { return globalRand.Int64N(n) } + +// Int32N returns, as an int32, a pseudo-random number in the half-open interval [0,n) +// from the default Source. +// It panics if n <= 0. +func Int32N(n int32) int32 { return globalRand.Int32N(n) } + +// IntN returns, as an int, a pseudo-random number in the half-open interval [0,n) +// from the default Source. +// It panics if n <= 0. +func IntN(n int) int { return globalRand.IntN(n) } + +// UintN returns, as a uint, a pseudo-random number in the half-open interval [0,n) +// from the default Source. +// It panics if n <= 0. +func UintN(n uint) uint { return globalRand.UintN(n) } + +// N returns a pseudo-random number in the half-open interval [0,n) from the default Source. +// The type parameter Int can be any integer type. +// It panics if n <= 0. +func N[Int intType](n Int) Int { + if n <= 0 { + panic("invalid argument to N") + } + return Int(globalRand.uint64n(uint64(n))) +} + +type intType interface { + ~int | ~int8 | ~int16 | ~int32 | ~int64 | + ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr +} + +// Float64 returns, as a float64, a pseudo-random number in the half-open interval [0.0,1.0) +// from the default Source. +func Float64() float64 { return globalRand.Float64() } + +// Float32 returns, as a float32, a pseudo-random number in the half-open interval [0.0,1.0) +// from the default Source. +func Float32() float32 { return globalRand.Float32() } + +// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers +// in the half-open interval [0,n) from the default Source. +func Perm(n int) []int { return globalRand.Perm(n) } + +// Shuffle pseudo-randomizes the order of elements using the default Source. +// n is the number of elements. Shuffle panics if n < 0. +// swap swaps the elements with indexes i and j. +func Shuffle(n int, swap func(i, j int)) { globalRand.Shuffle(n, swap) } + +// NormFloat64 returns a normally distributed float64 in the range +// [-math.MaxFloat64, +math.MaxFloat64] with +// standard normal distribution (mean = 0, stddev = 1) +// from the default Source. +// To produce a different normal distribution, callers can +// adjust the output using: +// +// sample = NormFloat64() * desiredStdDev + desiredMean +func NormFloat64() float64 { return globalRand.NormFloat64() } + +// ExpFloat64 returns an exponentially distributed float64 in the range +// (0, +math.MaxFloat64] with an exponential distribution whose rate parameter +// (lambda) is 1 and whose mean is 1/lambda (1) from the default Source. +// To produce a distribution with a different rate parameter, +// callers can adjust the output using: +// +// sample = ExpFloat64() / desiredRateParameter +func ExpFloat64() float64 { return globalRand.ExpFloat64() } diff --git a/src/math/rand/v2/rand_test.go b/src/math/rand/v2/rand_test.go new file mode 100644 index 0000000..c4b53fa --- /dev/null +++ b/src/math/rand/v2/rand_test.go @@ -0,0 +1,787 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand_test + +import ( + "errors" + "fmt" + "internal/testenv" + "math" + . "math/rand/v2" + "os" + "runtime" + "sync" + "sync/atomic" + "testing" +) + +const ( + numTestSamples = 10000 +) + +var rn, kn, wn, fn = GetNormalDistributionParameters() +var re, ke, we, fe = GetExponentialDistributionParameters() + +type statsResults struct { + mean float64 + stddev float64 + closeEnough float64 + maxError float64 +} + +func max(a, b float64) float64 { + if a > b { + return a + } + return b +} + +func nearEqual(a, b, closeEnough, maxError float64) bool { + absDiff := math.Abs(a - b) + if absDiff < closeEnough { // Necessary when one value is zero and one value is close to zero. + return true + } + return absDiff/max(math.Abs(a), math.Abs(b)) < maxError +} + +var testSeeds = []uint64{1, 1754801282, 1698661970, 1550503961} + +// checkSimilarDistribution returns success if the mean and stddev of the +// two statsResults are similar. +func (this *statsResults) checkSimilarDistribution(expected *statsResults) error { + if !nearEqual(this.mean, expected.mean, expected.closeEnough, expected.maxError) { + s := fmt.Sprintf("mean %v != %v (allowed error %v, %v)", this.mean, expected.mean, expected.closeEnough, expected.maxError) + fmt.Println(s) + return errors.New(s) + } + if !nearEqual(this.stddev, expected.stddev, expected.closeEnough, expected.maxError) { + s := fmt.Sprintf("stddev %v != %v (allowed error %v, %v)", this.stddev, expected.stddev, expected.closeEnough, expected.maxError) + fmt.Println(s) + return errors.New(s) + } + return nil +} + +func getStatsResults(samples []float64) *statsResults { + res := new(statsResults) + var sum, squaresum float64 + for _, s := range samples { + sum += s + squaresum += s * s + } + res.mean = sum / float64(len(samples)) + res.stddev = math.Sqrt(squaresum/float64(len(samples)) - res.mean*res.mean) + return res +} + +func checkSampleDistribution(t *testing.T, samples []float64, expected *statsResults) { + t.Helper() + actual := getStatsResults(samples) + err := actual.checkSimilarDistribution(expected) + if err != nil { + t.Errorf(err.Error()) + } +} + +func checkSampleSliceDistributions(t *testing.T, samples []float64, nslices int, expected *statsResults) { + t.Helper() + chunk := len(samples) / nslices + for i := 0; i < nslices; i++ { + low := i * chunk + var high int + if i == nslices-1 { + high = len(samples) - 1 + } else { + high = (i + 1) * chunk + } + checkSampleDistribution(t, samples[low:high], expected) + } +} + +// +// Normal distribution tests +// + +func generateNormalSamples(nsamples int, mean, stddev float64, seed uint64) []float64 { + r := New(NewPCG(seed, seed)) + samples := make([]float64, nsamples) + for i := range samples { + samples[i] = r.NormFloat64()*stddev + mean + } + return samples +} + +func testNormalDistribution(t *testing.T, nsamples int, mean, stddev float64, seed uint64) { + //fmt.Printf("testing nsamples=%v mean=%v stddev=%v seed=%v\n", nsamples, mean, stddev, seed); + + samples := generateNormalSamples(nsamples, mean, stddev, seed) + errorScale := max(1.0, stddev) // Error scales with stddev + expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.08 * errorScale} + + // Make sure that the entire set matches the expected distribution. + checkSampleDistribution(t, samples, expected) + + // Make sure that each half of the set matches the expected distribution. + checkSampleSliceDistributions(t, samples, 2, expected) + + // Make sure that each 7th of the set matches the expected distribution. + checkSampleSliceDistributions(t, samples, 7, expected) +} + +// Actual tests + +func TestStandardNormalValues(t *testing.T) { + for _, seed := range testSeeds { + testNormalDistribution(t, numTestSamples, 0, 1, seed) + } +} + +func TestNonStandardNormalValues(t *testing.T) { + sdmax := 1000.0 + mmax := 1000.0 + if testing.Short() { + sdmax = 5 + mmax = 5 + } + for sd := 0.5; sd < sdmax; sd *= 2 { + for m := 0.5; m < mmax; m *= 2 { + for _, seed := range testSeeds { + testNormalDistribution(t, numTestSamples, m, sd, seed) + if testing.Short() { + break + } + } + } + } +} + +// +// Exponential distribution tests +// + +func generateExponentialSamples(nsamples int, rate float64, seed uint64) []float64 { + r := New(NewPCG(seed, seed)) + samples := make([]float64, nsamples) + for i := range samples { + samples[i] = r.ExpFloat64() / rate + } + return samples +} + +func testExponentialDistribution(t *testing.T, nsamples int, rate float64, seed uint64) { + //fmt.Printf("testing nsamples=%v rate=%v seed=%v\n", nsamples, rate, seed); + + mean := 1 / rate + stddev := mean + + samples := generateExponentialSamples(nsamples, rate, seed) + errorScale := max(1.0, 1/rate) // Error scales with the inverse of the rate + expected := &statsResults{mean, stddev, 0.10 * errorScale, 0.20 * errorScale} + + // Make sure that the entire set matches the expected distribution. + checkSampleDistribution(t, samples, expected) + + // Make sure that each half of the set matches the expected distribution. + checkSampleSliceDistributions(t, samples, 2, expected) + + // Make sure that each 7th of the set matches the expected distribution. + checkSampleSliceDistributions(t, samples, 7, expected) +} + +// Actual tests + +func TestStandardExponentialValues(t *testing.T) { + for _, seed := range testSeeds { + testExponentialDistribution(t, numTestSamples, 1, seed) + } +} + +func TestNonStandardExponentialValues(t *testing.T) { + for rate := 0.05; rate < 10; rate *= 2 { + for _, seed := range testSeeds { + testExponentialDistribution(t, numTestSamples, rate, seed) + if testing.Short() { + break + } + } + } +} + +// +// Table generation tests +// + +func initNorm() (testKn []uint32, testWn, testFn []float32) { + const m1 = 1 << 31 + var ( + dn float64 = rn + tn = dn + vn float64 = 9.91256303526217e-3 + ) + + testKn = make([]uint32, 128) + testWn = make([]float32, 128) + testFn = make([]float32, 128) + + q := vn / math.Exp(-0.5*dn*dn) + testKn[0] = uint32((dn / q) * m1) + testKn[1] = 0 + testWn[0] = float32(q / m1) + testWn[127] = float32(dn / m1) + testFn[0] = 1.0 + testFn[127] = float32(math.Exp(-0.5 * dn * dn)) + for i := 126; i >= 1; i-- { + dn = math.Sqrt(-2.0 * math.Log(vn/dn+math.Exp(-0.5*dn*dn))) + testKn[i+1] = uint32((dn / tn) * m1) + tn = dn + testFn[i] = float32(math.Exp(-0.5 * dn * dn)) + testWn[i] = float32(dn / m1) + } + return +} + +func initExp() (testKe []uint32, testWe, testFe []float32) { + const m2 = 1 << 32 + var ( + de float64 = re + te = de + ve float64 = 3.9496598225815571993e-3 + ) + + testKe = make([]uint32, 256) + testWe = make([]float32, 256) + testFe = make([]float32, 256) + + q := ve / math.Exp(-de) + testKe[0] = uint32((de / q) * m2) + testKe[1] = 0 + testWe[0] = float32(q / m2) + testWe[255] = float32(de / m2) + testFe[0] = 1.0 + testFe[255] = float32(math.Exp(-de)) + for i := 254; i >= 1; i-- { + de = -math.Log(ve/de + math.Exp(-de)) + testKe[i+1] = uint32((de / te) * m2) + te = de + testFe[i] = float32(math.Exp(-de)) + testWe[i] = float32(de / m2) + } + return +} + +// compareUint32Slices returns the first index where the two slices +// disagree, or <0 if the lengths are the same and all elements +// are identical. +func compareUint32Slices(s1, s2 []uint32) int { + if len(s1) != len(s2) { + if len(s1) > len(s2) { + return len(s2) + 1 + } + return len(s1) + 1 + } + for i := range s1 { + if s1[i] != s2[i] { + return i + } + } + return -1 +} + +// compareFloat32Slices returns the first index where the two slices +// disagree, or <0 if the lengths are the same and all elements +// are identical. +func compareFloat32Slices(s1, s2 []float32) int { + if len(s1) != len(s2) { + if len(s1) > len(s2) { + return len(s2) + 1 + } + return len(s1) + 1 + } + for i := range s1 { + if !nearEqual(float64(s1[i]), float64(s2[i]), 0, 1e-7) { + return i + } + } + return -1 +} + +func TestNormTables(t *testing.T) { + testKn, testWn, testFn := initNorm() + if i := compareUint32Slices(kn[0:], testKn); i >= 0 { + t.Errorf("kn disagrees at index %v; %v != %v", i, kn[i], testKn[i]) + } + if i := compareFloat32Slices(wn[0:], testWn); i >= 0 { + t.Errorf("wn disagrees at index %v; %v != %v", i, wn[i], testWn[i]) + } + if i := compareFloat32Slices(fn[0:], testFn); i >= 0 { + t.Errorf("fn disagrees at index %v; %v != %v", i, fn[i], testFn[i]) + } +} + +func TestExpTables(t *testing.T) { + testKe, testWe, testFe := initExp() + if i := compareUint32Slices(ke[0:], testKe); i >= 0 { + t.Errorf("ke disagrees at index %v; %v != %v", i, ke[i], testKe[i]) + } + if i := compareFloat32Slices(we[0:], testWe); i >= 0 { + t.Errorf("we disagrees at index %v; %v != %v", i, we[i], testWe[i]) + } + if i := compareFloat32Slices(fe[0:], testFe); i >= 0 { + t.Errorf("fe disagrees at index %v; %v != %v", i, fe[i], testFe[i]) + } +} + +func hasSlowFloatingPoint() bool { + switch runtime.GOARCH { + case "arm": + return os.Getenv("GOARM") == "5" + case "mips", "mipsle", "mips64", "mips64le": + // Be conservative and assume that all mips boards + // have emulated floating point. + // TODO: detect what it actually has. + return true + } + return false +} + +func TestFloat32(t *testing.T) { + // For issue 6721, the problem came after 7533753 calls, so check 10e6. + num := int(10e6) + // But do the full amount only on builders (not locally). + // But ARM5 floating point emulation is slow (Issue 10749), so + // do less for that builder: + if testing.Short() && (testenv.Builder() == "" || hasSlowFloatingPoint()) { + num /= 100 // 1.72 seconds instead of 172 seconds + } + + r := testRand() + for ct := 0; ct < num; ct++ { + f := r.Float32() + if f >= 1 { + t.Fatal("Float32() should be in range [0,1). ct:", ct, "f:", f) + } + } +} + +func TestShuffleSmall(t *testing.T) { + // Check that Shuffle allows n=0 and n=1, but that swap is never called for them. + r := testRand() + for n := 0; n <= 1; n++ { + r.Shuffle(n, func(i, j int) { t.Fatalf("swap called, n=%d i=%d j=%d", n, i, j) }) + } +} + +// encodePerm converts from a permuted slice of length n, such as Perm generates, to an int in [0, n!). +// See https://en.wikipedia.org/wiki/Lehmer_code. +// encodePerm modifies the input slice. +func encodePerm(s []int) int { + // Convert to Lehmer code. + for i, x := range s { + r := s[i+1:] + for j, y := range r { + if y > x { + r[j]-- + } + } + } + // Convert to int in [0, n!). + m := 0 + fact := 1 + for i := len(s) - 1; i >= 0; i-- { + m += s[i] * fact + fact *= len(s) - i + } + return m +} + +// TestUniformFactorial tests several ways of generating a uniform value in [0, n!). +func TestUniformFactorial(t *testing.T) { + r := New(NewPCG(1, 2)) + top := 6 + if testing.Short() { + top = 3 + } + for n := 3; n <= top; n++ { + t.Run(fmt.Sprintf("n=%d", n), func(t *testing.T) { + // Calculate n!. + nfact := 1 + for i := 2; i <= n; i++ { + nfact *= i + } + + // Test a few different ways to generate a uniform distribution. + p := make([]int, n) // re-usable slice for Shuffle generator + tests := [...]struct { + name string + fn func() int + }{ + {name: "Int32N", fn: func() int { return int(r.Int32N(int32(nfact))) }}, + {name: "Perm", fn: func() int { return encodePerm(r.Perm(n)) }}, + {name: "Shuffle", fn: func() int { + // Generate permutation using Shuffle. + for i := range p { + p[i] = i + } + r.Shuffle(n, func(i, j int) { p[i], p[j] = p[j], p[i] }) + return encodePerm(p) + }}, + } + + for _, test := range tests { + t.Run(test.name, func(t *testing.T) { + // Gather chi-squared values and check that they follow + // the expected normal distribution given n!-1 degrees of freedom. + // See https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test and + // https://www.johndcook.com/Beautiful_Testing_ch10.pdf. + nsamples := 10 * nfact + if nsamples < 1000 { + nsamples = 1000 + } + samples := make([]float64, nsamples) + for i := range samples { + // Generate some uniformly distributed values and count their occurrences. + const iters = 1000 + counts := make([]int, nfact) + for i := 0; i < iters; i++ { + counts[test.fn()]++ + } + // Calculate chi-squared and add to samples. + want := iters / float64(nfact) + var χ2 float64 + for _, have := range counts { + err := float64(have) - want + χ2 += err * err + } + χ2 /= want + samples[i] = χ2 + } + + // Check that our samples approximate the appropriate normal distribution. + dof := float64(nfact - 1) + expected := &statsResults{mean: dof, stddev: math.Sqrt(2 * dof)} + errorScale := max(1.0, expected.stddev) + expected.closeEnough = 0.10 * errorScale + expected.maxError = 0.08 // TODO: What is the right value here? See issue 21211. + checkSampleDistribution(t, samples, expected) + }) + } + }) + } +} + +// Benchmarks + +var Sink uint64 + +func testRand() *Rand { + return New(NewPCG(1, 2)) +} + +func BenchmarkSourceUint64(b *testing.B) { + s := NewPCG(1, 2) + var t uint64 + for n := b.N; n > 0; n-- { + t += s.Uint64() + } + Sink = uint64(t) +} + +func BenchmarkGlobalInt64(b *testing.B) { + var t int64 + for n := b.N; n > 0; n-- { + t += Int64() + } + Sink = uint64(t) +} + +func BenchmarkGlobalInt64Parallel(b *testing.B) { + b.RunParallel(func(pb *testing.PB) { + var t int64 + for pb.Next() { + t += Int64() + } + atomic.AddUint64(&Sink, uint64(t)) + }) +} + +func BenchmarkGlobalUint64(b *testing.B) { + var t uint64 + for n := b.N; n > 0; n-- { + t += Uint64() + } + Sink = t +} + +func BenchmarkGlobalUint64Parallel(b *testing.B) { + b.RunParallel(func(pb *testing.PB) { + var t uint64 + for pb.Next() { + t += Uint64() + } + atomic.AddUint64(&Sink, t) + }) +} + +func BenchmarkInt64(b *testing.B) { + r := testRand() + var t int64 + for n := b.N; n > 0; n-- { + t += r.Int64() + } + Sink = uint64(t) +} + +var AlwaysFalse = false + +func keep[T int | uint | int32 | uint32 | int64 | uint64](x T) T { + if AlwaysFalse { + return -x + } + return x +} + +func BenchmarkUint64(b *testing.B) { + r := testRand() + var t uint64 + for n := b.N; n > 0; n-- { + t += r.Uint64() + } + Sink = t +} + +func BenchmarkGlobalIntN1000(b *testing.B) { + var t int + arg := keep(1000) + for n := b.N; n > 0; n-- { + t += IntN(arg) + } + Sink = uint64(t) +} + +func BenchmarkIntN1000(b *testing.B) { + r := testRand() + var t int + arg := keep(1000) + for n := b.N; n > 0; n-- { + t += r.IntN(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt64N1000(b *testing.B) { + r := testRand() + var t int64 + arg := keep(int64(1000)) + for n := b.N; n > 0; n-- { + t += r.Int64N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt64N1e8(b *testing.B) { + r := testRand() + var t int64 + arg := keep(int64(1e8)) + for n := b.N; n > 0; n-- { + t += r.Int64N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt64N1e9(b *testing.B) { + r := testRand() + var t int64 + arg := keep(int64(1e9)) + for n := b.N; n > 0; n-- { + t += r.Int64N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt64N2e9(b *testing.B) { + r := testRand() + var t int64 + arg := keep(int64(2e9)) + for n := b.N; n > 0; n-- { + t += r.Int64N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt64N1e18(b *testing.B) { + r := testRand() + var t int64 + arg := keep(int64(1e18)) + for n := b.N; n > 0; n-- { + t += r.Int64N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt64N2e18(b *testing.B) { + r := testRand() + var t int64 + arg := keep(int64(2e18)) + for n := b.N; n > 0; n-- { + t += r.Int64N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt64N4e18(b *testing.B) { + r := testRand() + var t int64 + arg := keep(int64(4e18)) + for n := b.N; n > 0; n-- { + t += r.Int64N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt32N1000(b *testing.B) { + r := testRand() + var t int32 + arg := keep(int32(1000)) + for n := b.N; n > 0; n-- { + t += r.Int32N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt32N1e8(b *testing.B) { + r := testRand() + var t int32 + arg := keep(int32(1e8)) + for n := b.N; n > 0; n-- { + t += r.Int32N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt32N1e9(b *testing.B) { + r := testRand() + var t int32 + arg := keep(int32(1e9)) + for n := b.N; n > 0; n-- { + t += r.Int32N(arg) + } + Sink = uint64(t) +} + +func BenchmarkInt32N2e9(b *testing.B) { + r := testRand() + var t int32 + arg := keep(int32(2e9)) + for n := b.N; n > 0; n-- { + t += r.Int32N(arg) + } + Sink = uint64(t) +} + +func BenchmarkFloat32(b *testing.B) { + r := testRand() + var t float32 + for n := b.N; n > 0; n-- { + t += r.Float32() + } + Sink = uint64(t) +} + +func BenchmarkFloat64(b *testing.B) { + r := testRand() + var t float64 + for n := b.N; n > 0; n-- { + t += r.Float64() + } + Sink = uint64(t) +} + +func BenchmarkExpFloat64(b *testing.B) { + r := testRand() + var t float64 + for n := b.N; n > 0; n-- { + t += r.ExpFloat64() + } + Sink = uint64(t) +} + +func BenchmarkNormFloat64(b *testing.B) { + r := testRand() + var t float64 + for n := b.N; n > 0; n-- { + t += r.NormFloat64() + } + Sink = uint64(t) +} + +func BenchmarkPerm3(b *testing.B) { + r := testRand() + var t int + for n := b.N; n > 0; n-- { + t += r.Perm(3)[0] + } + Sink = uint64(t) + +} + +func BenchmarkPerm30(b *testing.B) { + r := testRand() + var t int + for n := b.N; n > 0; n-- { + t += r.Perm(30)[0] + } + Sink = uint64(t) +} + +func BenchmarkPerm30ViaShuffle(b *testing.B) { + r := testRand() + var t int + for n := b.N; n > 0; n-- { + p := make([]int, 30) + for i := range p { + p[i] = i + } + r.Shuffle(30, func(i, j int) { p[i], p[j] = p[j], p[i] }) + t += p[0] + } + Sink = uint64(t) +} + +// BenchmarkShuffleOverhead uses a minimal swap function +// to measure just the shuffling overhead. +func BenchmarkShuffleOverhead(b *testing.B) { + r := testRand() + for n := b.N; n > 0; n-- { + r.Shuffle(30, func(i, j int) { + if i < 0 || i >= 30 || j < 0 || j >= 30 { + b.Fatalf("bad swap(%d, %d)", i, j) + } + }) + } +} + +func BenchmarkConcurrent(b *testing.B) { + const goroutines = 4 + var wg sync.WaitGroup + wg.Add(goroutines) + for i := 0; i < goroutines; i++ { + go func() { + defer wg.Done() + for n := b.N; n > 0; n-- { + Int64() + } + }() + } + wg.Wait() +} + +func TestN(t *testing.T) { + for i := 0; i < 1000; i++ { + v := N(10) + if v < 0 || v >= 10 { + t.Fatalf("N(10) returned %d", v) + } + } +} diff --git a/src/math/rand/v2/regress_test.go b/src/math/rand/v2/regress_test.go new file mode 100644 index 0000000..c85d584 --- /dev/null +++ b/src/math/rand/v2/regress_test.go @@ -0,0 +1,563 @@ +// Copyright 2014 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Test that random number sequences generated by a specific seed +// do not change from version to version. +// +// Do NOT make changes to the golden outputs. If bugs need to be fixed +// in the underlying code, find ways to fix them that do not affect the +// outputs. + +package rand_test + +import ( + "bytes" + "flag" + "fmt" + "go/format" + "io" + . "math/rand/v2" + "os" + "reflect" + "strings" + "testing" +) + +var update = flag.Bool("update", false, "update golden results for regression test") + +func TestRegress(t *testing.T) { + var int32s = []int32{1, 10, 32, 1 << 20, 1<<20 + 1, 1000000000, 1 << 30, 1<<31 - 2, 1<<31 - 1} + var uint32s = []uint32{1, 10, 32, 1 << 20, 1<<20 + 1, 1000000000, 1 << 30, 1<<31 - 2, 1<<31 - 1, 1<<32 - 2, 1<<32 - 1} + var int64s = []int64{1, 10, 32, 1 << 20, 1<<20 + 1, 1000000000, 1 << 30, 1<<31 - 2, 1<<31 - 1, 1000000000000000000, 1 << 60, 1<<63 - 2, 1<<63 - 1} + var uint64s = []uint64{1, 10, 32, 1 << 20, 1<<20 + 1, 1000000000, 1 << 30, 1<<31 - 2, 1<<31 - 1, 1000000000000000000, 1 << 60, 1<<63 - 2, 1<<63 - 1, 1<<64 - 2, 1<<64 - 1} + var permSizes = []int{0, 1, 5, 8, 9, 10, 16} + + n := reflect.TypeOf(New(NewPCG(1, 2))).NumMethod() + p := 0 + var buf bytes.Buffer + if *update { + fmt.Fprintf(&buf, "var regressGolden = []any{\n") + } + for i := 0; i < n; i++ { + if *update && i > 0 { + fmt.Fprintf(&buf, "\n") + } + r := New(NewPCG(1, 2)) + rv := reflect.ValueOf(r) + m := rv.Type().Method(i) + mv := rv.Method(i) + mt := mv.Type() + if mt.NumOut() == 0 { + continue + } + for repeat := 0; repeat < 20; repeat++ { + var args []reflect.Value + var argstr string + if mt.NumIn() == 1 { + var x any + switch mt.In(0).Kind() { + default: + t.Fatalf("unexpected argument type for r.%s", m.Name) + + case reflect.Int: + if m.Name == "Perm" { + x = permSizes[repeat%len(permSizes)] + break + } + big := int64s[repeat%len(int64s)] + if int64(int(big)) != big { + // On 32-bit machine. + // Consume an Int64 like on a 64-bit machine, + // to keep the golden data the same on different architectures. + r.Int64N(big) + if *update { + t.Fatalf("must run -update on 64-bit machine") + } + p++ + continue + } + x = int(big) + + case reflect.Uint: + big := uint64s[repeat%len(uint64s)] + if uint64(uint(big)) != big { + r.Uint64N(big) // what would happen on 64-bit machine, to keep stream in sync + if *update { + t.Fatalf("must run -update on 64-bit machine") + } + p++ + continue + } + x = uint(big) + + case reflect.Int32: + x = int32s[repeat%len(int32s)] + + case reflect.Int64: + x = int64s[repeat%len(int64s)] + + case reflect.Uint32: + x = uint32s[repeat%len(uint32s)] + + case reflect.Uint64: + x = uint64s[repeat%len(uint64s)] + } + argstr = fmt.Sprint(x) + args = append(args, reflect.ValueOf(x)) + } + + var out any + out = mv.Call(args)[0].Interface() + if m.Name == "Int" || m.Name == "IntN" { + out = int64(out.(int)) + } + if m.Name == "Uint" || m.Name == "UintN" { + out = uint64(out.(uint)) + } + if *update { + var val string + big := int64(1 << 60) + if int64(int(big)) != big && (m.Name == "Int" || m.Name == "IntN") { + // 32-bit machine cannot print 64-bit results + val = "truncated" + } else if reflect.TypeOf(out).Kind() == reflect.Slice { + val = fmt.Sprintf("%#v", out) + } else { + val = fmt.Sprintf("%T(%v)", out, out) + } + fmt.Fprintf(&buf, "\t%s, // %s(%s)\n", val, m.Name, argstr) + } else if p >= len(regressGolden) { + t.Errorf("r.%s(%s) = %v, missing golden value", m.Name, argstr, out) + } else { + want := regressGolden[p] + if m.Name == "Int" { + want = int64(int(uint(want.(int64)) << 1 >> 1)) + } + if !reflect.DeepEqual(out, want) { + t.Errorf("r.%s(%s) = %v, want %v", m.Name, argstr, out, want) + } + } + p++ + } + } + if *update { + replace(t, "regress_test.go", buf.Bytes()) + } +} + +func TestUpdateExample(t *testing.T) { + if !*update { + t.Skip("-update not given") + } + + oldStdout := os.Stdout + defer func() { + os.Stdout = oldStdout + }() + + r, w, err := os.Pipe() + if err != nil { + t.Fatal(err) + } + defer r.Close() + defer w.Close() + + go func() { + os.Stdout = w + Example_rand() + os.Stdout = oldStdout + w.Close() + }() + out, err := io.ReadAll(r) + if err != nil { + t.Fatal(err) + } + + var buf bytes.Buffer + fmt.Fprintf(&buf, "\t// Output:\n") + for _, line := range strings.Split(string(out), "\n") { + if line != "" { + fmt.Fprintf(&buf, "\t// %s\n", line) + } + } + + replace(t, "example_test.go", buf.Bytes()) + + // Exit so that Example_rand cannot fail. + fmt.Printf("UPDATED; ignore non-zero exit status\n") + os.Exit(1) +} + +// replace substitutes the definition text from new into the content of file. +// The text in new is of the form +// +// var whatever = T{ +// ... +// } +// +// Replace searches file for an exact match for the text of the first line, +// finds the closing brace, and then substitutes new for what used to be in the file. +// This lets us update the regressGolden table during go test -update. +func replace(t *testing.T, file string, new []byte) { + first, _, _ := bytes.Cut(new, []byte("\n")) + first = append(append([]byte("\n"), first...), '\n') + data, err := os.ReadFile(file) + if err != nil { + t.Fatal(err) + } + i := bytes.Index(data, first) + if i < 0 { + t.Fatalf("cannot find %q in %s", first, file) + } + j := bytes.Index(data[i+1:], []byte("\n}\n")) + if j < 0 { + t.Fatalf("cannot find end in %s", file) + } + data = append(append(data[:i+1:i+1], new...), data[i+1+j+1:]...) + data, err = format.Source(data) + if err != nil { + t.Fatal(err) + } + if err := os.WriteFile(file, data, 0666); err != nil { + t.Fatal(err) + } +} + +var regressGolden = []any{ + float64(0.5931317151369719), // ExpFloat64() + float64(0.0680034588807843), // ExpFloat64() + float64(0.036496967459790364), // ExpFloat64() + float64(2.460335459645379), // ExpFloat64() + float64(1.5792300208419903), // ExpFloat64() + float64(0.9149501499404387), // ExpFloat64() + float64(0.43463410545541104), // ExpFloat64() + float64(0.5513632046504593), // ExpFloat64() + float64(0.7426404617374481), // ExpFloat64() + float64(1.2334925132631804), // ExpFloat64() + float64(0.892529142200442), // ExpFloat64() + float64(0.21508763681487764), // ExpFloat64() + float64(1.0208588200798545), // ExpFloat64() + float64(0.7650739736831382), // ExpFloat64() + float64(0.7772788529257701), // ExpFloat64() + float64(1.102732861281323), // ExpFloat64() + float64(0.6982243043885805), // ExpFloat64() + float64(0.4981788638202421), // ExpFloat64() + float64(0.15806532306947937), // ExpFloat64() + float64(0.9419163802459202), // ExpFloat64() + + float32(0.95955694), // Float32() + float32(0.8076733), // Float32() + float32(0.8135684), // Float32() + float32(0.92872405), // Float32() + float32(0.97472525), // Float32() + float32(0.5485458), // Float32() + float32(0.97740936), // Float32() + float32(0.042272687), // Float32() + float32(0.99663067), // Float32() + float32(0.035181105), // Float32() + float32(0.45059562), // Float32() + float32(0.86597633), // Float32() + float32(0.8954844), // Float32() + float32(0.090798736), // Float32() + float32(0.46218646), // Float32() + float32(0.5955118), // Float32() + float32(0.08985227), // Float32() + float32(0.19820237), // Float32() + float32(0.7443699), // Float32() + float32(0.56461), // Float32() + + float64(0.6764556596678251), // Float64() + float64(0.4613862177205994), // Float64() + float64(0.5085473976760264), // Float64() + float64(0.4297927436037299), // Float64() + float64(0.797802349388613), // Float64() + float64(0.3883664855410056), // Float64() + float64(0.8192750264193612), // Float64() + float64(0.3381816951746133), // Float64() + float64(0.9730458047755973), // Float64() + float64(0.281449117585586), // Float64() + float64(0.6047654075331631), // Float64() + float64(0.9278107175107462), // Float64() + float64(0.16387541502137226), // Float64() + float64(0.7263900707339023), // Float64() + float64(0.6974917552729882), // Float64() + float64(0.7640946923790318), // Float64() + float64(0.7188183661358182), // Float64() + float64(0.5856191500346635), // Float64() + float64(0.9549597149363428), // Float64() + float64(0.5168804691962643), // Float64() + + int64(4969059760275911952), // Int() + int64(2147869220224756844), // Int() + int64(5246770554000605320), // Int() + int64(5471241176507662746), // Int() + int64(4321634407747778896), // Int() + int64(760102831717374652), // Int() + int64(9221744211007427193), // Int() + int64(8289669384274456462), // Int() + int64(2449715415482412441), // Int() + int64(3389241988064777392), // Int() + int64(2986830195847294191), // Int() + int64(8204908297817606218), // Int() + int64(8134976985547166651), // Int() + int64(2240328155279531677), // Int() + int64(7311121042813227358), // Int() + int64(5231057920893523323), // Int() + int64(4257872588489500903), // Int() + int64(158397175702351138), // Int() + int64(1350674201389090105), // Int() + int64(6093522341581845358), // Int() + + int32(1652216515), // Int32() + int32(1323786710), // Int32() + int32(1684546306), // Int32() + int32(1710678126), // Int32() + int32(503104460), // Int32() + int32(88487615), // Int32() + int32(1073552320), // Int32() + int32(965044529), // Int32() + int32(285184408), // Int32() + int32(394559696), // Int32() + int32(1421454622), // Int32() + int32(955177040), // Int32() + int32(2020777787), // Int32() + int32(260808523), // Int32() + int32(851126509), // Int32() + int32(1682717115), // Int32() + int32(1569423431), // Int32() + int32(1092181682), // Int32() + int32(157239171), // Int32() + int32(709379364), // Int32() + + int32(0), // Int32N(1) + int32(6), // Int32N(10) + int32(8), // Int32N(32) + int32(704922), // Int32N(1048576) + int32(245656), // Int32N(1048577) + int32(41205257), // Int32N(1000000000) + int32(43831929), // Int32N(1073741824) + int32(965044528), // Int32N(2147483646) + int32(285184408), // Int32N(2147483647) + int32(0), // Int32N(1) + int32(6), // Int32N(10) + int32(10), // Int32N(32) + int32(283579), // Int32N(1048576) + int32(127348), // Int32N(1048577) + int32(396336665), // Int32N(1000000000) + int32(911873403), // Int32N(1073741824) + int32(1569423430), // Int32N(2147483646) + int32(1092181681), // Int32N(2147483647) + int32(0), // Int32N(1) + int32(3), // Int32N(10) + + int64(4969059760275911952), // Int64() + int64(2147869220224756844), // Int64() + int64(5246770554000605320), // Int64() + int64(5471241176507662746), // Int64() + int64(4321634407747778896), // Int64() + int64(760102831717374652), // Int64() + int64(9221744211007427193), // Int64() + int64(8289669384274456462), // Int64() + int64(2449715415482412441), // Int64() + int64(3389241988064777392), // Int64() + int64(2986830195847294191), // Int64() + int64(8204908297817606218), // Int64() + int64(8134976985547166651), // Int64() + int64(2240328155279531677), // Int64() + int64(7311121042813227358), // Int64() + int64(5231057920893523323), // Int64() + int64(4257872588489500903), // Int64() + int64(158397175702351138), // Int64() + int64(1350674201389090105), // Int64() + int64(6093522341581845358), // Int64() + + int64(0), // Int64N(1) + int64(6), // Int64N(10) + int64(8), // Int64N(32) + int64(704922), // Int64N(1048576) + int64(245656), // Int64N(1048577) + int64(41205257), // Int64N(1000000000) + int64(43831929), // Int64N(1073741824) + int64(965044528), // Int64N(2147483646) + int64(285184408), // Int64N(2147483647) + int64(183731176326946086), // Int64N(1000000000000000000) + int64(680987186633600239), // Int64N(1152921504606846976) + int64(4102454148908803108), // Int64N(9223372036854775806) + int64(8679174511200971228), // Int64N(9223372036854775807) + int64(0), // Int64N(1) + int64(3), // Int64N(10) + int64(27), // Int64N(32) + int64(665831), // Int64N(1048576) + int64(533292), // Int64N(1048577) + int64(73220195), // Int64N(1000000000) + int64(686060398), // Int64N(1073741824) + + int64(0), // IntN(1) + int64(6), // IntN(10) + int64(8), // IntN(32) + int64(704922), // IntN(1048576) + int64(245656), // IntN(1048577) + int64(41205257), // IntN(1000000000) + int64(43831929), // IntN(1073741824) + int64(965044528), // IntN(2147483646) + int64(285184408), // IntN(2147483647) + int64(183731176326946086), // IntN(1000000000000000000) + int64(680987186633600239), // IntN(1152921504606846976) + int64(4102454148908803108), // IntN(9223372036854775806) + int64(8679174511200971228), // IntN(9223372036854775807) + int64(0), // IntN(1) + int64(3), // IntN(10) + int64(27), // IntN(32) + int64(665831), // IntN(1048576) + int64(533292), // IntN(1048577) + int64(73220195), // IntN(1000000000) + int64(686060398), // IntN(1073741824) + + float64(0.37944549835531083), // NormFloat64() + float64(0.07473804659119399), // NormFloat64() + float64(0.20006841200604142), // NormFloat64() + float64(-1.1253144115495104), // NormFloat64() + float64(-0.4005883316435388), // NormFloat64() + float64(-3.0853771402394736), // NormFloat64() + float64(1.932330243076978), // NormFloat64() + float64(1.726131393719264), // NormFloat64() + float64(-0.11707238034168332), // NormFloat64() + float64(-0.9303318111676635), // NormFloat64() + float64(-0.04750789419852852), // NormFloat64() + float64(0.22248301107582735), // NormFloat64() + float64(-1.83630520614272), // NormFloat64() + float64(0.7259521217919809), // NormFloat64() + float64(0.8806882871913041), // NormFloat64() + float64(-1.5022903484270484), // NormFloat64() + float64(0.5972577266810571), // NormFloat64() + float64(1.5631937339973658), // NormFloat64() + float64(-0.3841235370075905), // NormFloat64() + float64(-0.2967295854430667), // NormFloat64() + + []int{}, // Perm(0) + []int{0}, // Perm(1) + []int{1, 4, 2, 0, 3}, // Perm(5) + []int{4, 3, 6, 1, 5, 2, 7, 0}, // Perm(8) + []int{6, 5, 1, 8, 7, 2, 0, 3, 4}, // Perm(9) + []int{9, 4, 2, 5, 6, 8, 1, 7, 0, 3}, // Perm(10) + []int{5, 9, 3, 1, 4, 2, 10, 7, 15, 11, 0, 14, 13, 8, 6, 12}, // Perm(16) + []int{}, // Perm(0) + []int{0}, // Perm(1) + []int{4, 2, 1, 3, 0}, // Perm(5) + []int{0, 2, 3, 1, 5, 4, 6, 7}, // Perm(8) + []int{2, 0, 8, 3, 4, 7, 6, 5, 1}, // Perm(9) + []int{0, 6, 5, 3, 8, 4, 1, 2, 9, 7}, // Perm(10) + []int{9, 14, 4, 11, 13, 8, 0, 6, 2, 12, 3, 7, 1, 10, 5, 15}, // Perm(16) + []int{}, // Perm(0) + []int{0}, // Perm(1) + []int{2, 4, 0, 3, 1}, // Perm(5) + []int{3, 2, 1, 0, 7, 5, 4, 6}, // Perm(8) + []int{1, 3, 4, 5, 0, 2, 7, 8, 6}, // Perm(9) + []int{1, 8, 4, 7, 2, 6, 5, 9, 0, 3}, // Perm(10) + + uint32(3304433030), // Uint32() + uint32(2647573421), // Uint32() + uint32(3369092613), // Uint32() + uint32(3421356252), // Uint32() + uint32(1006208920), // Uint32() + uint32(176975231), // Uint32() + uint32(2147104640), // Uint32() + uint32(1930089058), // Uint32() + uint32(570368816), // Uint32() + uint32(789119393), // Uint32() + uint32(2842909244), // Uint32() + uint32(1910354080), // Uint32() + uint32(4041555575), // Uint32() + uint32(521617046), // Uint32() + uint32(1702253018), // Uint32() + uint32(3365434230), // Uint32() + uint32(3138846863), // Uint32() + uint32(2184363364), // Uint32() + uint32(314478343), // Uint32() + uint32(1418758728), // Uint32() + + uint32(0), // Uint32N(1) + uint32(6), // Uint32N(10) + uint32(8), // Uint32N(32) + uint32(704922), // Uint32N(1048576) + uint32(245656), // Uint32N(1048577) + uint32(41205257), // Uint32N(1000000000) + uint32(43831929), // Uint32N(1073741824) + uint32(965044528), // Uint32N(2147483646) + uint32(285184408), // Uint32N(2147483647) + uint32(789119393), // Uint32N(4294967294) + uint32(2842909244), // Uint32N(4294967295) + uint32(0), // Uint32N(1) + uint32(9), // Uint32N(10) + uint32(29), // Uint32N(32) + uint32(266590), // Uint32N(1048576) + uint32(821640), // Uint32N(1048577) + uint32(730819735), // Uint32N(1000000000) + uint32(522841378), // Uint32N(1073741824) + uint32(157239171), // Uint32N(2147483646) + uint32(709379364), // Uint32N(2147483647) + + uint64(14192431797130687760), // Uint64() + uint64(11371241257079532652), // Uint64() + uint64(14470142590855381128), // Uint64() + uint64(14694613213362438554), // Uint64() + uint64(4321634407747778896), // Uint64() + uint64(760102831717374652), // Uint64() + uint64(9221744211007427193), // Uint64() + uint64(8289669384274456462), // Uint64() + uint64(2449715415482412441), // Uint64() + uint64(3389241988064777392), // Uint64() + uint64(12210202232702069999), // Uint64() + uint64(8204908297817606218), // Uint64() + uint64(17358349022401942459), // Uint64() + uint64(2240328155279531677), // Uint64() + uint64(7311121042813227358), // Uint64() + uint64(14454429957748299131), // Uint64() + uint64(13481244625344276711), // Uint64() + uint64(9381769212557126946), // Uint64() + uint64(1350674201389090105), // Uint64() + uint64(6093522341581845358), // Uint64() + + uint64(0), // Uint64N(1) + uint64(6), // Uint64N(10) + uint64(8), // Uint64N(32) + uint64(704922), // Uint64N(1048576) + uint64(245656), // Uint64N(1048577) + uint64(41205257), // Uint64N(1000000000) + uint64(43831929), // Uint64N(1073741824) + uint64(965044528), // Uint64N(2147483646) + uint64(285184408), // Uint64N(2147483647) + uint64(183731176326946086), // Uint64N(1000000000000000000) + uint64(680987186633600239), // Uint64N(1152921504606846976) + uint64(4102454148908803108), // Uint64N(9223372036854775806) + uint64(8679174511200971228), // Uint64N(9223372036854775807) + uint64(2240328155279531676), // Uint64N(18446744073709551614) + uint64(7311121042813227357), // Uint64N(18446744073709551615) + uint64(0), // Uint64N(1) + uint64(7), // Uint64N(10) + uint64(2), // Uint64N(32) + uint64(312633), // Uint64N(1048576) + uint64(346376), // Uint64N(1048577) + + uint64(0), // UintN(1) + uint64(6), // UintN(10) + uint64(8), // UintN(32) + uint64(704922), // UintN(1048576) + uint64(245656), // UintN(1048577) + uint64(41205257), // UintN(1000000000) + uint64(43831929), // UintN(1073741824) + uint64(965044528), // UintN(2147483646) + uint64(285184408), // UintN(2147483647) + uint64(183731176326946086), // UintN(1000000000000000000) + uint64(680987186633600239), // UintN(1152921504606846976) + uint64(4102454148908803108), // UintN(9223372036854775806) + uint64(8679174511200971228), // UintN(9223372036854775807) + uint64(2240328155279531676), // UintN(18446744073709551614) + uint64(7311121042813227357), // UintN(18446744073709551615) + uint64(0), // UintN(1) + uint64(7), // UintN(10) + uint64(2), // UintN(32) + uint64(312633), // UintN(1048576) + uint64(346376), // UintN(1048577) +} diff --git a/src/math/rand/v2/zipf.go b/src/math/rand/v2/zipf.go new file mode 100644 index 0000000..f04c814 --- /dev/null +++ b/src/math/rand/v2/zipf.go @@ -0,0 +1,77 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// W.Hormann, G.Derflinger: +// "Rejection-Inversion to Generate Variates +// from Monotone Discrete Distributions" +// http://eeyore.wu-wien.ac.at/papers/96-04-04.wh-der.ps.gz + +package rand + +import "math" + +// A Zipf generates Zipf distributed variates. +type Zipf struct { + r *Rand + imax float64 + v float64 + q float64 + s float64 + oneminusQ float64 + oneminusQinv float64 + hxm float64 + hx0minusHxm float64 +} + +func (z *Zipf) h(x float64) float64 { + return math.Exp(z.oneminusQ*math.Log(z.v+x)) * z.oneminusQinv +} + +func (z *Zipf) hinv(x float64) float64 { + return math.Exp(z.oneminusQinv*math.Log(z.oneminusQ*x)) - z.v +} + +// NewZipf returns a Zipf variate generator. +// The generator generates values k ∈ [0, imax] +// such that P(k) is proportional to (v + k) ** (-s). +// Requirements: s > 1 and v >= 1. +func NewZipf(r *Rand, s float64, v float64, imax uint64) *Zipf { + z := new(Zipf) + if s <= 1.0 || v < 1 { + return nil + } + z.r = r + z.imax = float64(imax) + z.v = v + z.q = s + z.oneminusQ = 1.0 - z.q + z.oneminusQinv = 1.0 / z.oneminusQ + z.hxm = z.h(z.imax + 0.5) + z.hx0minusHxm = z.h(0.5) - math.Exp(math.Log(z.v)*(-z.q)) - z.hxm + z.s = 1 - z.hinv(z.h(1.5)-math.Exp(-z.q*math.Log(z.v+1.0))) + return z +} + +// Uint64 returns a value drawn from the Zipf distribution described +// by the Zipf object. +func (z *Zipf) Uint64() uint64 { + if z == nil { + panic("rand: nil Zipf") + } + k := 0.0 + + for { + r := z.r.Float64() // r on [0,1] + ur := z.hxm + r*z.hx0minusHxm + x := z.hinv(ur) + k = math.Floor(x + 0.5) + if k-x <= z.s { + break + } + if ur >= z.h(k+0.5)-math.Exp(-math.Log(k+z.v)*z.q) { + break + } + } + return uint64(k) +} |