Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LAGraph_Random: generate a random vector (of any sparsity structure)
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : //
8 : // For additional details (including references to third party source code and
9 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
10 : // Contributors.txt for a full list of contributors. Created, in part, with
11 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
12 : // DM22-0790
13 :
14 : // Contributed by Timothy A. Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : // A very simple thread-safe parallel pseudo-random nuumber generator.
19 :
20 : // FUTURE: add LAGraph_Random_Init to LAGraph_Init,
21 : // and added LAGraph_Random_Finalize to LAGraph_Finalize.
22 :
23 : #include "LG_internal.h"
24 : #include "LAGraphX.h"
25 :
26 : //------------------------------------------------------------------------------
27 : // LG_RAND macros
28 : //------------------------------------------------------------------------------
29 :
30 : // Generate the next seed
31 : #define LG_RAND_NEXT(seed) ((seed) * 1103515245 + 12345)
32 :
33 : // extract a random 15-bit value from a seed (no longer used)
34 : // #define LG_RAND_15_MAX 32767
35 : // #define LG_RAND_15(seed) (((seed)/65536) % (LG_RAND_15_MAX + 1))
36 :
37 : //------------------------------------------------------------------------------
38 : // global operator
39 : //------------------------------------------------------------------------------
40 :
41 : // This operator can be shared by all threads in a user application, and thus
42 : // is safely declared as a global object.
43 :
44 : GrB_UnaryOp LG_rand_next_op = NULL ;
45 :
46 : //------------------------------------------------------------------------------
47 : // LG_rand_next_f: unary operator to construct the next seed
48 : //------------------------------------------------------------------------------
49 :
50 : // z = f(x), where x is the old seed and z is the new seed.
51 :
52 285699 : void LG_rand_next_f (void *z, const void *x)
53 : {
54 285699 : uint64_t seed = (*((uint64_t *) x)) ;
55 285699 : seed = LG_RAND_NEXT (seed) ;
56 285699 : seed = LG_RAND_NEXT (seed) ;
57 285699 : seed = LG_RAND_NEXT (seed) ;
58 285699 : seed = LG_RAND_NEXT (seed) ;
59 285699 : seed = LG_RAND_NEXT (seed) ;
60 285699 : (*((uint64_t *) z)) = seed ;
61 285699 : }
62 :
63 : //------------------------------------------------------------------------------
64 : // LAGraph_Random_Init: create the random seed operator
65 : //------------------------------------------------------------------------------
66 :
67 : #undef LG_FREE_WORK
68 : #define LG_FREE_WORK \
69 : { \
70 : GrB_UnaryOp_free (&LG_rand_next_op) ; \
71 : }
72 :
73 5 : int LAGraph_Random_Init (char *msg)
74 : {
75 5 : LG_CLEAR_MSG ;
76 5 : LG_rand_next_op = NULL ;
77 5 : GRB_TRY (GrB_UnaryOp_new (&LG_rand_next_op, LG_rand_next_f,
78 : GrB_UINT64, GrB_UINT64)) ;
79 5 : return (GrB_SUCCESS) ;
80 : }
81 :
82 : //------------------------------------------------------------------------------
83 : // LAGraph_Random_Finalize: free the random seed operator
84 : //------------------------------------------------------------------------------
85 :
86 5 : int LAGraph_Random_Finalize (char *msg)
87 : {
88 5 : LG_CLEAR_MSG ;
89 5 : LG_FREE_WORK ;
90 5 : return (GrB_SUCCESS) ;
91 : }
92 :
93 : //------------------------------------------------------------------------------
94 : // LAGraph_Random_Seed: create a vector of random seeds
95 : //------------------------------------------------------------------------------
96 :
97 : // Initializes a vector with random seed values. The Seed vector must be
98 : // allocated on input, and should be of type GrB_UINT64. Its sparsity
99 : // structure is unchanged.
100 :
101 : #undef LG_FREE_WORK
102 : #define LG_FREE_WORK GrB_free (&T) ;
103 :
104 : #if defined ( COVERAGE )
105 : // for testing only
106 : bool random_hack = false ;
107 : #endif
108 :
109 833 : int LAGraph_Random_Seed // construct a random seed vector
110 : (
111 : // input/output
112 : GrB_Vector Seed, // GrB_UINT64 vector of random number seeds
113 : // input
114 : uint64_t seed, // scalar input seed
115 : char *msg
116 : )
117 : {
118 : // check inputs
119 833 : LG_CLEAR_MSG ;
120 833 : GrB_Vector T = NULL ;
121 833 : LG_ASSERT (Seed != NULL, GrB_NULL_POINTER) ;
122 :
123 : // T = 1:n but only for entries present in the Seed vector. This
124 : // requires a typecast from int64 to uint64.
125 : GrB_Index n ;
126 833 : GRB_TRY (GrB_Vector_size (&n, Seed)) ;
127 833 : GRB_TRY (GrB_Vector_new (&T, GrB_UINT64, n)) ;
128 833 : GRB_TRY (GrB_Vector_apply_IndexOp_INT64 (T, NULL, NULL,
129 : GrB_ROWINDEX_INT64, Seed, 1, NULL)) ;
130 :
131 : // Seed = T * INT32_MAX
132 833 : GRB_TRY (GrB_apply (Seed, NULL, NULL, GrB_TIMES_UINT64, T,
133 : (uint64_t) INT32_MAX, NULL)) ;
134 :
135 : // Seed = Seed + seed
136 833 : GRB_TRY (GrB_apply (Seed, NULL, NULL, GrB_PLUS_UINT64, Seed, seed, NULL)) ;
137 :
138 : // Seed = next (Seed)
139 833 : GRB_TRY (GrB_Vector_apply (Seed, NULL, NULL, LG_rand_next_op, Seed, NULL)) ;
140 :
141 : #if defined ( COVERAGE )
142 833 : if (random_hack)
143 : {
144 : // Set all Seed values to 1, to break the random seed vector.
145 : // This is just for testing, to test algorithms that need to handle
146 : // extreme cases when the random number generator is non-random.
147 432 : GRB_TRY (GrB_Vector_apply_BinaryOp2nd_UINT64 (Seed, NULL, NULL,
148 : GrB_ONEB_UINT64, Seed, 0, NULL)) ;
149 : }
150 : #endif
151 :
152 833 : LG_FREE_WORK ;
153 833 : return (GrB_SUCCESS) ;
154 : }
155 :
156 : //------------------------------------------------------------------------------
157 : // LAGraph_Random_Next: return next vector of random seeds
158 : //------------------------------------------------------------------------------
159 :
160 : #undef LG_FREE_WORK
161 : #define LG_FREE_WORK ;
162 :
163 1108 : int LAGraph_Random_Next // advance to next random vector
164 : (
165 : // input/output
166 : GrB_Vector Seed, // the sparsity pattern of Seed is preserved
167 : char *msg
168 : )
169 : {
170 : // check inputs
171 1108 : LG_CLEAR_MSG ;
172 1108 : LG_ASSERT (Seed != NULL, GrB_NULL_POINTER) ;
173 : // Seed = next (Seed)
174 1108 : GRB_TRY (GrB_Vector_apply (Seed, NULL, NULL, LG_rand_next_op, Seed, NULL)) ;
175 1108 : return (GrB_SUCCESS) ;
176 : }
|
