GIS Library - Pseudo-random number generation. More...
#include <errno.h>#include <inttypes.h>#include <stdint.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <grass/gis.h>#include <grass/glocale.h>#include <sys/time.h>#include <sys/types.h>#include <unistd.h>
Go to the source code of this file.
Macros | |
| #define | LRAND48_ATOMIC 0 |
| #define | LCG_A UINT64_C(0x5DEECE66D) |
| #define | LCG_B UINT64_C(0xB) |
| #define | MASK48 UINT64_C(0xFFFFFFFFFFFF) |
| #define | LCG_SPAN (UINT64_C(1) << 46) |
| #define | WHOLE_SPAN_MAX_UNITS (INT64_C(1) << 20) |
| #define | LO(x) ((x) & 0xFFFFU) |
| #define | HI(x) ((x) >> 16) |
Typedefs | |
| typedef unsigned short | uint16 |
| typedef unsigned int | uint32 |
| typedef signed int | int32 |
Functions | |
| void | G_srand48 (long seedval) |
| Seed the pseudo-random number generator. | |
| int64_t | G_random_generate_seed (void) |
| Generate a seed for a random number generator. | |
| long | G_srand48_auto (void) |
| Seed the pseudo-random number generator from the time and PID. | |
| long | G_lrand48 (void) |
| Generate an integer in the range [0, 2^31) | |
| long | G_mrand48 (void) |
| Generate an integer in the range [-2^31, 2^31) | |
| double | G_drand48 (void) |
| Generate a floating-point value in the range [0,1) | |
| void | G_random_state_from_seed (struct G_random_state *state, int64_t seed) |
| Seed a pseudo-random number generator of the program's own. | |
| void | G_random_init_layout_exact (struct G_random_layout *layout, int64_t seed, int64_t units, int64_t draws_per_unit) |
| Initialize a layout whose units draw an exact number of values. | |
| void | G_random_init_layout_bounded (struct G_random_layout *layout, int64_t seed, int64_t units, int64_t max_draws) |
| Initialize a layout whose units draw at most a number of values. | |
| void | G_random_init_layout (struct G_random_layout *layout, int64_t seed, int64_t units) |
| Initialize a layout which gives the units the whole span. | |
| int64_t | G_random_layout_batches (const struct G_random_layout *layout) |
| Return the number of batches that fit into the span. | |
| int64_t | G_random_layout_length (const struct G_random_layout *layout) |
| Return the number of values a unit may draw. | |
| void | G_random_state_for_batch (struct G_random_state *state, const struct G_random_layout *layout, int64_t batch, int64_t unit) |
| Put a generator state at the start of a unit's stream in a batch. | |
| void | G_random_state_for_unit (struct G_random_state *state, const struct G_random_layout *layout, int64_t unit) |
| Put a generator state at the start of a unit's stream. | |
| void | G_random_advance (struct G_random_state *state, int64_t draws) |
| Advance a generator of the program's own as if values had been drawn. | |
| double | G_random_double (struct G_random_state *state) |
| Generate a floating-point value in the range [0,1) from a generator of the program's own. | |
Detailed Description
GIS Library - Pseudo-random number generation.
The generator is the standard drand48 linear congruential generator X' = (A * X + B) mod 2^48 with A = 0x5DEECE66D and B = 0xB.
When C11 atomic operations are available, the generator state is advanced with an atomic compare-and-swap and the generating functions are thread-safe: the sequence of generated values for a given seed is the same as in a single-threaded run. Which thread receives which value depends on scheduling, so results are fully reproducible only with single-threaded execution. Without C11 atomics (notably MSVC, which defines STDC_NO_ATOMICS), the generator falls back to plain state updates, so multi-threaded usage is safe only when compiled with C11 atomics.
The seeding functions are not thread-safe; see G_srand48().
The G_random_*() functions instead advance generators owned by the program, one struct G_random_state per unit of work. The program keeps a state to one thread at a time; the functions then need neither atomics nor locks, behave identically on every build, and give each unit a sequence fixed by the seed and the unit's number, not by the thread that draws it. The library places the units within the span, the first 2^46 draws after the seed, a quarter of the generator's cycle: a layout gives every unit of every batch a stream of stride draws in it, and a state is put at the start of its unit's stream. See gislib_random_streams for the model.
SPDX-FileCopyrightText: 2014-2026 GRASS Development Team SPDX-License-Identifier: GPL-2.0-or-later
Definition in file lrand48.c.
Macro Definition Documentation
◆ HI
◆ LCG_A
◆ LCG_B
◆ LCG_SPAN
◆ LO
◆ LRAND48_ATOMIC
◆ MASK48
◆ WHOLE_SPAN_MAX_UNITS
Typedef Documentation
◆ int32
◆ uint16
◆ uint32
Function Documentation
◆ G_drand48()
Generate a floating-point value in the range [0,1)
This function is thread-safe only when compiled with C11 atomics (see the comment at the top of the file).
- Returns
- the generated value
Definition at line 351 of file lrand48.c.
References r.
Referenced by f_rand(), and G_math_rand().
◆ G_lrand48()
Generate an integer in the range [0, 2^31)
This function is thread-safe only when compiled with C11 atomics (see the comment at the top of the file).
- Returns
- the generated value
Definition at line 307 of file lrand48.c.
References r.
Referenced by Rast_make_random_colors().
◆ G_mrand48()
◆ G_random_advance()
| void G_random_advance | ( | struct G_random_state * | state, |
| int64_t | draws | ||
| ) |
Advance a generator of the program's own as if values had been drawn.
Moves the state by draws draws without taking them one at a time, so that the next G_random_double() returns what the draw after those would have returned.
A negative draws is a fatal error.
- Parameters
-
[in,out] state a seeded generator state [in] draws number of values to skip, not negative
Definition at line 748 of file lrand48.c.
References _, G_fatal_error(), and state.
◆ G_random_double()
| double G_random_double | ( | struct G_random_state * | state | ) |
Generate a floating-point value in the range [0,1) from a generator of the program's own.
Thread-safe as long as no two threads share a state. Unlike G_drand48(), this needs no atomics and so behaves identically on every build.
- Parameters
-
[in,out] state generator state, set with G_random_state_from_seed(), G_random_state_for_unit() or G_random_state_for_batch()
- Returns
- the generated value
Definition at line 771 of file lrand48.c.
References state.
◆ G_random_generate_seed()
Generate a seed for a random number generator.
The seed is the value of the environment variable GRASS_RANDOM_SEED, or of SOURCE_DATE_EPOCH when GRASS_RANDOM_SEED is not set or empty, and otherwise a weak hash of the current time and process ID. A value from the environment must be a decimal integer within the range of int64_t, with nothing after it (leading white space and a sign are allowed); anything else is a fatal error naming the variable. A value from -2^31 to 2^32 - 1 is returned as it is, and a value outside that range is reduced to its low 32 bits, between 0 and 2^32 - 1, with a warning. The result is therefore a seed G_random_state_from_seed(), the layout functions and G_srand48() accept. Record it, for example in the history of the output map, so that the run can be repeated with it as the seed.
The hash of the time and process ID lies between 0 and 2^32 - 1. Two calls in one process within the same microsecond, or within the same second on systems without gettimeofday(), return the same value, and two processes can get the same value too.
The function reads the environment and the clock and changes no generator; it may issue a warning or end with a fatal error.
- Returns
- the seed
Definition at line 196 of file lrand48.c.
References _, AMI_STREAM< T >::AMI_STREAM(), G_fatal_error(), getpid, gettimeofday(), NULL, and t.
Referenced by G_srand48_auto().
◆ G_random_init_layout()
| void G_random_init_layout | ( | struct G_random_layout * | layout, |
| int64_t | seed, | ||
| int64_t | units | ||
| ) |
Initialize a layout which gives the units the whole span.
For units whose number of draws is not known in advance. The span is divided into parts, as many as there are units, or one more when that number is even. The stride is 2^46 / parts rounded down, and then down to odd when there is more than one part, and unit u starts u * stride draws after the seed. The odd number of parts keeps the unit halfway or a quarter of the way along from starting 2^45 or 2^44 draws after unit 0, distances at which this generator's values relate (see gislib_random_streams): the unit nearest to 2^45 starts at least 0.48 of a stride away from it and the unit nearest to 2^44 at least 0.24, so a unit meets such a relation only after drawing about a quarter of its stride. The odd stride puts units 2^i apart in number an odd multiple of 2^i draws apart, as in a bounded layout. A single unit keeps the whole span of 2^46 draws, as a state from G_random_state_from_seed() does. The layout holds a single batch.
The number of units is limited to 2^20: the rounded stride loses up to two draws per unit, which accumulate along the span, so beyond that count the units nearest to 2^45 and 2^44 would drift toward them. A bounded layout serves any number of units.
The stride is the length of a part. G_random_layout_length() returns it, and G_random_layout_batches() returns 1.
A seed outside -2^31 to 2^32 - 1, or a number of units which is not positive or above 2^20, is a fatal error.
- Parameters
-
[out] layout layout to initialize [in] seed seed, see G_random_state_from_seed() [in] units number of units of work, from 1 to 2^20
Definition at line 606 of file lrand48.c.
References _, AMI_STREAM< T >::AMI_STREAM(), G_fatal_error(), LCG_SPAN, and WHOLE_SPAN_MAX_UNITS.
◆ G_random_init_layout_bounded()
| void G_random_init_layout_bounded | ( | struct G_random_layout * | layout, |
| int64_t | seed, | ||
| int64_t | units, | ||
| int64_t | max_draws | ||
| ) |
Initialize a layout whose units draw at most a number of values.
As G_random_init_layout_exact(), but each unit may draw any number of values up to max_draws: the streams are max_draws draws long, or max_draws + 1 when max_draws is even. With an odd stride, units 2^i apart in number start an odd multiple of 2^i draws apart, so the differences of their states are fixed in the low i + 2 bits only; an even stride would add its own power of two to that count.
The stride is max_draws rounded up to odd. G_random_layout_length() returns it, and G_random_layout_batches() returns the batches that fit, which is 0 when units times the stride draws do not fit into the span. See gislib_random_streams.
A seed outside -2^31 to 2^32 - 1, a number of units or a bound which is not positive, or a product of the units and the stride beyond the range of int64_t is a fatal error.
- Parameters
-
[out] layout layout to initialize [in] seed seed, see G_random_state_from_seed() [in] units number of units of work, positive [in] max_draws most values any unit draws, positive
Definition at line 551 of file lrand48.c.
References _, AMI_STREAM< T >::AMI_STREAM(), and G_fatal_error().
◆ G_random_init_layout_exact()
| void G_random_init_layout_exact | ( | struct G_random_layout * | layout, |
| int64_t | seed, | ||
| int64_t | units, | ||
| int64_t | draws_per_unit | ||
| ) |
Initialize a layout whose units draw an exact number of values.
The span is cut into streams of exactly draws_per_unit draws, one per unit, placed one after another from the seed. Unit u of batch 0 therefore draws what a single sequence from G_random_state_from_seed() draws at positions u * draws_per_unit to (u + 1) * draws_per_unit - 1, so the units together reproduce a serial run whatever order they are processed in. Further batches follow, see G_random_state_for_batch(). A unit which draws more than draws_per_unit values runs into the next unit's stream; when the number of draws is only bounded, use G_random_init_layout_bounded().
The stride is draws_per_unit. G_random_layout_length() returns it, and G_random_layout_batches() returns the batches that fit, which is 0 when units * draws_per_unit draws do not fit into the span. See gislib_random_streams.
A seed outside -2^31 to 2^32 - 1, a number of units or of draws which is not positive, or a product of the two beyond the range of int64_t is a fatal error.
- Parameters
-
[out] layout layout to initialize [in] seed seed, see G_random_state_from_seed() [in] units number of units of work, positive [in] draws_per_unit number of values each unit draws, positive
Definition at line 510 of file lrand48.c.
References _, and G_fatal_error().
◆ G_random_layout_batches()
| int64_t G_random_layout_batches | ( | const struct G_random_layout * | layout | ) |
◆ G_random_layout_length()
| int64_t G_random_layout_length | ( | const struct G_random_layout * | layout | ) |
◆ G_random_state_for_batch()
| void G_random_state_for_batch | ( | struct G_random_state * | state, |
| const struct G_random_layout * | layout, | ||
| int64_t | batch, | ||
| int64_t | unit | ||
| ) |
Put a generator state at the start of a unit's stream in a batch.
A batch is one stream for every unit of the layout, and the batches follow one another along the span. They start units * stride draws apart, or one more when that number is even, and the stream of unit in batch starts unit * stride draws after the start of the batch. With the odd distance, as with an odd stride, the same draw of different batches is as unrelated as the generator allows; what an even distance would relate there is related between draws whose numbers differ instead. The state is set whatever it held before, so the same call always restarts the same sequence. See gislib_random_streams.
A unit outside 0 to units - 1, a negative batch, a batch other than 0 of a layout of the whole span, or a batch beyond the batches that fit is a fatal error. When no batch fits, batch 0 is still allowed, and only batch 0: a tool which warned that its layout does not fit into the span may use it as earlier versions did.
Thread-safe as long as no two threads use the same state; the layout is only read.
- Parameters
-
[out] state generator state to set [in] layout an initialized layout [in] batch number of the batch, from 0 [in] unit number of the unit, from 0 to units - 1
Definition at line 682 of file lrand48.c.
References _, AMI_STREAM< T >::AMI_STREAM(), G_fatal_error(), n_, and state.
Referenced by G_random_state_for_unit().
◆ G_random_state_for_unit()
| void G_random_state_for_unit | ( | struct G_random_state * | state, |
| const struct G_random_layout * | layout, | ||
| int64_t | unit | ||
| ) |
Put a generator state at the start of a unit's stream.
The same as G_random_state_for_batch() with batch 0.
- Parameters
-
[out] state generator state to set [in] layout an initialized layout [in] unit number of the unit, from 0 to units - 1
Definition at line 730 of file lrand48.c.
References G_random_state_for_batch(), and state.
◆ G_random_state_from_seed()
| void G_random_state_from_seed | ( | struct G_random_state * | state, |
| int64_t | seed | ||
| ) |
Seed a pseudo-random number generator of the program's own.
Puts the state at the seed: it then produces the sequence G_srand48() followed by G_drand48() produces for the same seed, so code moving from the shared generator to one of its own reproduces its existing results. Use it for a single sequence, which then has the whole span to itself; for one sequence per unit of work, use a layout and G_random_state_for_unit().
A seed outside -2^31 to 2^32 - 1 is a fatal error. A negative seed means its two's complement 32-bit value, as for G_srand48().
Thread-safe as long as no two threads seed the same state.
- Parameters
-
[out] state generator state to seed [in] seed seed, from -2^31 to 2^32 - 1
Definition at line 477 of file lrand48.c.
References state.
◆ G_srand48()
Seed the pseudo-random number generator.
This function is not thread-safe. In a multi-threaded program, call G_srand48() once before starting the worker threads; it must not run concurrently with another thread seeding or generating values.
- Parameters
-
[in] seedval 32-bit integer used to seed the PRNG
Definition at line 117 of file lrand48.c.
References HI, LO, state, and x.
Referenced by G_math_srand(), and G_srand48_auto().
◆ G_srand48_auto()
Seed the pseudo-random number generator from the time and PID.
The seed is what G_random_generate_seed() returns: the value of GRASS_RANDOM_SEED or SOURCE_DATE_EPOCH, or a weak hash of the current time and PID.
This function is not thread-safe. In a multi-threaded program, call G_srand48_auto() once before starting the worker threads; it must not run concurrently with another thread seeding or generating values.
- Returns
- the seed passed to G_srand48(), between -2^31 and 2^32 - 1; where long has 32 bits, a value of 2^31 or more comes back negative, which G_srand48() and G_random_state_from_seed() read as the same seed
Definition at line 243 of file lrand48.c.
References AMI_STREAM< T >::AMI_STREAM(), G_random_generate_seed(), and G_srand48().
Referenced by G_math_srand_auto(), and Rast_make_random_colors().
