1/*
2 * Legal Notice
3 *
4 * This document and associated source code (the "Work") is a part of a
5 * benchmark specification maintained by the TPC.
6 *
7 * The TPC reserves all right, title, and interest to the Work as provided
8 * under U.S. and international laws, including without limitation all patent
9 * and trademark rights therein.
10 *
11 * No Warranty
12 *
13 * 1.1 TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW, THE INFORMATION
14 * CONTAINED HEREIN IS PROVIDED "AS IS" AND WITH ALL FAULTS, AND THE
15 * AUTHORS AND DEVELOPERS OF THE WORK HEREBY DISCLAIM ALL OTHER
16 * WARRANTIES AND CONDITIONS, EITHER EXPRESS, IMPLIED OR STATUTORY,
17 * INCLUDING, BUT NOT LIMITED TO, ANY (IF ANY) IMPLIED WARRANTIES,
18 * DUTIES OR CONDITIONS OF MERCHANTABILITY, OF FITNESS FOR A PARTICULAR
19 * PURPOSE, OF ACCURACY OR COMPLETENESS OF RESPONSES, OF RESULTS, OF
20 * WORKMANLIKE EFFORT, OF LACK OF VIRUSES, AND OF LACK OF NEGLIGENCE.
21 * ALSO, THERE IS NO WARRANTY OR CONDITION OF TITLE, QUIET ENJOYMENT,
22 * QUIET POSSESSION, CORRESPONDENCE TO DESCRIPTION OR NON-INFRINGEMENT
23 * WITH REGARD TO THE WORK.
24 * 1.2 IN NO EVENT WILL ANY AUTHOR OR DEVELOPER OF THE WORK BE LIABLE TO
25 * ANY OTHER PARTY FOR ANY DAMAGES, INCLUDING BUT NOT LIMITED TO THE
26 * COST OF PROCURING SUBSTITUTE GOODS OR SERVICES, LOST PROFITS, LOSS
27 * OF USE, LOSS OF DATA, OR ANY INCIDENTAL, CONSEQUENTIAL, DIRECT,
28 * INDIRECT, OR SPECIAL DAMAGES WHETHER UNDER CONTRACT, TORT, WARRANTY,
29 * OR OTHERWISE, ARISING IN ANY WAY OUT OF THIS OR ANY OTHER AGREEMENT
30 * RELATING TO THE WORK, WHETHER OR NOT SUCH AUTHOR OR DEVELOPER HAD
31 * ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES.
32 *
33 * Contributors
34 * - Charles Levine, Philip Durr, Doug Johnson, Cecil Reames, Matt Emmerton
35 */
36
37#include "utilities/Random.h"
38
39#include <cmath>
40#include <time.h>
41
42#include "utilities/BigMath.h"
43#include "utilities/MiscConsts.h"
44
45using namespace TPCE;
46
47inline RNGSEED CRandom::UInt64Rand(void) {
48
49 UINT64 a = (UINT64)UInt64Rand_A_MULTIPLIER;
50 UINT64 c = (UINT64)UInt64Rand_C_INCREMENT;
51 m_seed = (m_seed * a + c); // implicitly truncated to 64bits
52
53 return (m_seed);
54}
55
56RNGSEED CRandom::RndNthElement(RNGSEED nSeed, RNGSEED nCount) {
57 UINT64 a = UInt64Rand_A_MULTIPLIER;
58 UINT64 c = UInt64Rand_C_INCREMENT;
59 int nBit;
60 UINT64 Apow = a;
61 UINT64 Dsum = UInt64Rand_ONE;
62
63 // if nothing to do, do nothing !
64 if (nCount == 0) {
65 return nSeed;
66 }
67
68 // Recursively compute X(n) = A * X(n-1) + C
69 //
70 // explicitly:
71 // X(n) = A^n * X(0) + { A^(n-1) + A^(n-2) + ... A + 1 } * C
72 //
73 // we write this as:
74 // X(n) = Apow(n) * X(0) + Dsum(n) * C
75 //
76 // we use the following relations:
77 // Apow(n) = A^(n%2)*Apow(n/2)*Apow(n/2)
78 // Dsum(n) = (n%2)*Apow(n/2)*Apow(n/2) + (Apow(n/2) + 1) * Dsum(n/2)
79 //
80
81 // first get the highest non-zero bit
82 for (nBit = 0; (nCount >> nBit) != UInt64Rand_ONE; nBit++) {
83 }
84
85 // go 1 bit at the time
86 while (--nBit >= 0) {
87 Dsum *= (Apow + 1);
88 Apow = Apow * Apow;
89 if (((nCount >> nBit) % 2) == 1) { // odd value
90 Dsum += Apow;
91 Apow *= a;
92 }
93 }
94 nSeed = nSeed * Apow + Dsum * c;
95 return nSeed;
96}
97
98CRandom::CRandom(void) {
99 do {
100 // use portable way to get the seed
101 m_seed = (RNGSEED)time(NULL);
102 } while (m_seed == 0);
103}
104
105CRandom::CRandom(RNGSEED seed) {
106 SetSeed(seed);
107}
108
109void CRandom::SetSeed(RNGSEED seed) {
110 m_seed = seed;
111}
112
113#ifdef EGEN_USE_DEPRECATED_CODE
114
115// returns a random value in the range [0 .. 0.99999999999999999994578989137572]
116// care should be taken in casting the result as a float because of the
117// potential loss of precision.
118double CRandom::RndDouble(void) {
119 return ((double)UInt64Rand()) * (double)UInt64Rand_RECIPROCAL_2_POWER_64;
120}
121
122#endif // EGEN_USE_DEPRECATED_CODE
123
124int CRandom::RndIntRange(int min, int max) {
125 if (max <= min)
126 return min; // max <= min
127
128 UINT range = (max - min + 1);
129
130 if (range <= 1)
131 return min; // overflow happened
132
133 UInt64Rand(); // generate next seed value
134
135 return (min + (int)Mul6432WithShiftRight64(m_seed, range));
136}
137
138INT64 CRandom::RndInt64Range(INT64 min, INT64 max) {
139 if (max <= min)
140 return min;
141
142 UINT64 range = (max - min + 1);
143
144 if (range <= 1)
145 return min; // overflow happened
146
147 UInt64Rand(); // generate next seed value
148
149 return (min + (INT64)Mul6464WithShiftRight64(m_seed, range));
150}
151
152int CRandom::RndNthIntRange(RNGSEED Seed, RNGSEED N, int min, int max) {
153 if (max <= min)
154 return min; // max <= min
155
156 UINT range = (max - min + 1);
157
158 if (range <= 1)
159 return min; // overflow happened
160
161 RNGSEED nseed = RndNthElement(Seed, N); // generate next seed value
162
163 return (min + (int)Mul6432WithShiftRight64(nseed, range));
164}
165
166// return Nth element in the sequence over the integer range
167INT64 CRandom::RndNthInt64Range(RNGSEED Seed, RNGSEED N, INT64 min, INT64 max) {
168 if (max <= min)
169 return min;
170
171 UINT64 range = (max - min + 1);
172
173 if (range <= 1)
174 return min; // overflow happened
175
176 RNGSEED nseed = RndNthElement(Seed, N); // generate next seed value
177
178 return (min + (INT64)Mul6464WithShiftRight64(nseed, range));
179}
180
181int CRandom::RndIntRangeExclude(int low, int high, int exclude) {
182 int temp;
183
184 temp = RndIntRange(low, high - 1);
185 if (temp >= exclude)
186 temp += 1;
187
188 return temp;
189}
190
191INT64 CRandom::RndInt64RangeExclude(INT64 low, INT64 high, INT64 exclude) {
192 INT64 temp;
193
194 temp = RndInt64Range(low, high - 1);
195 if (temp >= exclude)
196 temp += 1;
197
198 return temp;
199}
200
201#ifdef EGEN_USE_DEPRECATED_CODE
202
203double CRandom::RndDoubleRange(double min, double max) {
204 return min + RndDouble() * (max - min);
205}
206
207#endif // EGEN_USE_DEPRECATED_CODE
208
209double CRandom::RndDoubleIncrRange(double min, double max, double incr) {
210 INT64 width = (INT64)((max - min) / incr); // need [0..width], so no +1
211 return min + ((double)RndInt64Range(0, width) * incr);
212}
213
214// returns a random double value from a negative exponential distribution with
215// the given mean
216double CRandom::RndDoubleNegExp(double mean) {
217 return ((-1.0 * std::log(RndDoubleIncrRange(0.0, 1.0, 0.000000000001))) * mean);
218}
219
220/* Returns a non-uniform random 64-bit integer in range of [P .. Q].
221 *
222 * NURnd is used to create a skewed data access pattern. The function is
223 * similar to NURand in TPC-C. (The two functions are identical when C=0
224 * and s=0.)
225 *
226 * The parameter A must be of the form 2^k - 1, so that Rnd[0..A] will
227 * produce a k-bit field with all bits having 50/50 probability of being 0
228 * or 1.
229 *
230 * With a k-bit A value, the weights range from 3^k down to 1 with the
231 * number of equal probability values given by C(k,i) = k! /(i!(k-i)!) for
232 * 0 <= i <= k. So a bigger A value from a larger k has much more skew.
233 *
234 * Left shifting of Rnd[0..A] by "s" bits gets a larger interval without
235 * getting huge amounts of skew. For example, when applied to elapsed time
236 * in milliseconds, s=10 effectively ignores the milliseconds, while s=16
237 * effectively ignores seconds and milliseconds, giving a granularity of
238 * just over 1 minute (65.536 seconds). A smaller A value can then give
239 * the desired amount of skew at effectively one-minute resolution.
240 */
241INT64 CRandom::NURnd(INT64 P, INT64 Q, INT32 A, INT32 s) {
242 return (((RndInt64Range(P, Q) | (RndInt64Range(0, A) << s)) % (Q - P + 1)) + P);
243}
244
245/*
246 * Returns an alphanumeric string in a specified format;
247 */
248
249void CRandom::RndAlphaNumFormatted(char *szReturnString, const char *szFormat) {
250 while (szFormat && *szFormat) {
251 switch (*szFormat) {
252 case 'a':
253 *szReturnString = UpperCaseLetters[RndIntRange(0, 25)]; // only uppercase
254 break;
255 case 'n':
256 *szReturnString = Numerals[RndIntRange(0, 9)];
257 break;
258 default:
259 *szReturnString = *szFormat;
260 }
261
262 ++szFormat;
263 ++szReturnString;
264 }
265 *szReturnString = '\0';
266}
267