// 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. /* * algorithm by * DP Mitchell and JA Reeds */ package rand // rand, rand31, rand63 - return non-negative random int, int32, int64 // urand32 - return random uint32 // nrand, nrand31, nrand63 - return 0 <= random < n // frand, frand64, frand32 - return 0 <= random float, float64, float32 < 1 // perm gives a random permutation []int const ( LEN = 607; TAP = 273; MASK = (1<<63)-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; } export func srand(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; } } } export func rand63() 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; } export func urand32() uint32 { return uint32(rand63() >> 31); } export func rand31() int32 { return int32(rand63() >> 32); } export func rand() int { u := uint(rand63()); return int(u << 1 >> 1); // clear sign bit if int == int32 } export func nrand63(n int64) int64 { if n <= 0 { return 0 } max := int64((1<<63)-1 - (1<<63) % uint64(n)); v := rand63(); for v > max { v = rand63() } return v % n } export func nrand31(n int32) int32 { return int32(nrand63(int64(n))) } export func nrand(n int) int { return int(nrand63(int64(n))) } export func frand64() float64 { x := float64(rand63()) / float64(MASK); for x >= 1 { x = float64(rand63()) / float64(MASK); } return x; } export func frand32() float32 { return float32(frand64()) } export func frand() float { return float(frand64()) } export func perm(n int) *[]int { m := new([]int, n); for i:=0; i