From b6708b2dad4af458e69fde7fc596ecdce03280d0 Mon Sep 17 00:00:00 2001 From: Rob Pike Date: Tue, 5 May 2009 17:05:39 -0700 Subject: directory-per-package step 1: move files from lib/X.go to lib/X/X.go no substantive changes except: - new Makefiles, all auto-generated - go/src/lib/Makefile has been extensively edited R=rsc OCL=28310 CL=28310 --- src/lib/rand/rand.go | 775 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 775 insertions(+) create mode 100644 src/lib/rand/rand.go (limited to 'src/lib/rand/rand.go') diff --git a/src/lib/rand/rand.go b/src/lib/rand/rand.go new file mode 100644 index 000000000..2fd48629b --- /dev/null +++ b/src/lib/rand/rand.go @@ -0,0 +1,775 @@ +// 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. + +// Uniformly distributed pseudo-random numbers. +package rand + +/* + * algorithm by + * DP Mitchell and JA Reeds + */ + +const ( + _LEN = 607; + _TAP = 273; + _MAX = 1<<63; + _MASK = _MAX-1; + _A = 48271; + _M = 2147483647; + _Q = 44488; + _R = 3399; +) + +var ( + rng_cooked [_LEN]int64; // cooked random numbers + rng_vec [_LEN]int64; // current feedback register + rng_tap int; // index into vector + rng_feed int; // index into vector +) + +func seedrand(x int32) int32 { + // seed rng x[n+1] = 48271 * x[n] mod (2**31 - 1) + hi := x / _Q; + lo := x % _Q; + x = _A*lo - _R*hi; + if x < 0 { + x += _M; + } + return x; +} + +// Seed uses the provided seed value to initialize the generator to a deterministic state. +func Seed(seed int32) { + rng_tap = 0; + rng_feed = _LEN-_TAP; + + seed = seed%_M; + if seed < 0 { + seed += _M; + } + if seed == 0 { + seed = 89482311; + } + + x := seed; + for i := -20; i < _LEN; i++ { + x = seedrand(x); + if i >= 0 { + var u int64; + u = int64(x) << 20; + x = seedrand(x); + u ^= int64(x) << 10; + x = seedrand(x); + u ^= int64(x); + u ^= rng_cooked[i]; + rng_vec[i] = u & _MASK; + } + } +} + +// Int63 returns a non-negative pseudo-random 63-bit integer as an int64. +func Int63() int64 { + rng_tap--; + if rng_tap < 0 { + rng_tap += _LEN; + } + + rng_feed--; + if rng_feed < 0 { + rng_feed += _LEN; + } + + x := (rng_vec[rng_feed] + rng_vec[rng_tap]) & _MASK; + rng_vec[rng_feed] = x; + return x; +} + +// Uint32 returns a pseudo-random 32-bit value as a uint32. +func Uint32() uint32 { + return uint32(Int63() >> 31); +} + +// Int31 returns a non-negative pseudo-random 31-bit integer as an int32. +func Int31() int32 { + return int32(Int63() >> 32); +} + +// Int returns a non-negative pseudo-random int. All bits but the top bit are random. +func Int() int { + u := uint(Int63()); + return int(u << 1 >> 1); // clear sign bit if int == int32 +} + +// Int63n returns, as an int64, a non-negative pseudo-random number in [0,n). +func Int63n(n int64) int64 { + if n <= 0 { + return 0 + } + max := int64((1<<63)-1 - (1<<63) % uint64(n)); + v := Int63(); + for v > max { + v = Int63() + } + return v % n +} + +// Int31n returns, as an int32, a non-negative pseudo-random number in [0,n). +func Int31n(n int32) int32 { + return int32(Int63n(int64(n))) +} + +// Intn returns, as an int, a non-negative pseudo-random number in [0,n). +func Intn(n int) int { + return int(Int63n(int64(n))) +} + +// Float64 returns, as a float64, a pseudo-random number in [0.0,1.0). +func Float64() float64 { + x := float64(Int63()) / float64(_MAX); + for x >= 1 { + x = float64(Int63()) / float64(_MAX); + } + return x; +} + +// Float32 returns, as a float32, a pseudo-random number in [0.0,1.0). +func Float32() float32 { + return float32(Float64()) +} + +// Float returns, as a float, a pseudo-random number in [0.0,1.0). +func Float() float +{ + return float(Float64()) +} + +// Perm returns, as an array of n ints, a pseudo-random permutation of the integers [0,n). +func Perm(n int) []int { + m := make([]int, n); + for i:=0; i