1 /* mpfr_urandom (rop, state, rnd_mode) -- Generate a uniform pseudorandom
2 real number between 0 and 1 (exclusive) and round it to the precision of rop
3 according to the given rounding mode.
4
5 Copyright 2000-2004, 2006-2023 Free Software Foundation, Inc.
6 Contributed by the AriC and Caramba projects, INRIA.
7
8 This file is part of the GNU MPFR Library.
9
10 The GNU MPFR Library is free software; you can redistribute it and/or modify
11 it under the terms of the GNU Lesser General Public License as published by
12 the Free Software Foundation; either version 3 of the License, or (at your
13 option) any later version.
14
15 The GNU MPFR Library is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18 License for more details.
19
20 You should have received a copy of the GNU Lesser General Public License
21 along with the GNU MPFR Library; see the file COPYING.LESSER. If not, see
22 https://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
23 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */
24
25
26 #define MPFR_NEED_LONGLONG_H
27 #include "mpfr-impl.h"
28
29
30 /* The mpfr_urandom() function is implemented in the following way,
31 so that the exact number (the random value to be rounded) and the
32 final status of the random generator do not depend on the current
33 exponent range and on the rounding mode. However, they depend on
34 the target precision: from the same state of the random generator,
35 if the precision of the destination is changed, then the value may
36 be completely different (and the state of the random generator is
37 different too).
38 1. One determines the exponent exp: 0 with probability 1/2, -1 with
39 probability 1/4, -2 with probability 1/8, etc.
40 2. One draws a 1-ulp interval ]a,b[ containing the exact result (the
41 interval can be regarded as open since it has the same measure as
42 the closed interval).
43 One also draws the rounding bit. This is currently done with a
44 separate call to mpfr_rand_raw(), but it should be better to draw
45 the rounding bit as part of the significand; there is space for it
46 since the MSB is always 1.
47 3. Rounding is done. For the directed rounding modes, the rounded value
48 is uniquely determined. For rounding to nearest, ]a,m[ and ]m,b[,
49 where m = (a+b)/2, have the same measure, so that one gets a or b
50 with equal probabilities.
51 */
52
53 int
54 mpfr_urandom (mpfr_ptr rop, gmp_randstate_t rstate, mpfr_rnd_t rnd_mode)
55 {
56 mpfr_limb_ptr rp;
57 mpfr_prec_t nbits;
58 mp_size_t nlimbs;
59 mp_size_t n;
60 mpfr_exp_t exp;
61 mp_limb_t rbit;
62 int cnt;
63 int inex;
64 MPFR_SAVE_EXPO_DECL (expo);
65
66 /* We need to extend the exponent range in order to simplify
67 the case where one rounds upward (we would not be able to
68 use mpfr_nextabove() in the case emin = max). It could be
69 partly reimplemented under a simpler form here, but it is
70 better to make the code shorter and more readable. */
71 MPFR_SAVE_EXPO_MARK (expo);
72
73 rp = MPFR_MANT (rop);
74 nbits = MPFR_PREC (rop);
75 MPFR_SET_EXP (rop, 0);
76 MPFR_SET_POS (rop);
77 exp = 0;
78
79 /* Step 1 (exponent). */
80 #define DRAW_BITS 8 /* we draw DRAW_BITS at a time */
81 MPFR_STAT_STATIC_ASSERT (DRAW_BITS <= GMP_NUMB_BITS);
82 do
83 {
84 /* generate DRAW_BITS in rp[0] */
85 mpfr_rand_raw (rp, rstate, DRAW_BITS);
86 if (MPFR_UNLIKELY (rp[0] == 0))
87 cnt = DRAW_BITS;
88 else
89 {
90 count_leading_zeros (cnt, rp[0]);
91 cnt -= GMP_NUMB_BITS - DRAW_BITS;
92 }
93 /* Any value of exp < MPFR_EMIN_MIN - 1 are equivalent. So, we can
94 avoid a theoretical integer overflow in the following way. */
95 if (MPFR_LIKELY (exp >= MPFR_EMIN_MIN - 1))
96 exp -= cnt; /* no integer overflow */
97 }
98 while (cnt == DRAW_BITS);
99 /* We do not want the random generator to depend on the ABI or on the
100 exponent range. Therefore we do not use MPFR_EMIN_MIN or __gmpfr_emin
101 in the stop condition. */
102
103 /* Step 2 (significand): we need generate only nbits-1 bits, since the
104 most significant bit is 1. */
105 if (MPFR_UNLIKELY (nbits == 1))
106 {
107 rp[0] = MPFR_LIMB_HIGHBIT;
108 }
109 else
110 {
111 mpfr_rand_raw (rp, rstate, nbits - 1);
112 nlimbs = MPFR_LIMB_SIZE (rop);
113 n = nlimbs * GMP_NUMB_BITS - nbits;
114 if (MPFR_LIKELY (n != 0)) /* this will put the low bits to zero */
115 mpn_lshift (rp, rp, nlimbs, n);
116 rp[nlimbs - 1] |= MPFR_LIMB_HIGHBIT;
117 }
118
119 /* Rounding bit */
120 mpfr_rand_raw (&rbit, rstate, 1);
121 MPFR_ASSERTD (rbit == 0 || rbit == 1);
122
123 /* Step 3 (rounding). */
124 if (rnd_mode == MPFR_RNDU || rnd_mode == MPFR_RNDA
125 || (rnd_mode == MPFR_RNDN && rbit != 0))
126 {
127 mpfr_nextabove (rop);
128 inex = +1;
129 }
130 else
131 {
132 inex = -1;
133 }
134
135 MPFR_EXP (rop) += exp; /* may be smaller than emin */
136 MPFR_SAVE_EXPO_FREE (expo);
137 return mpfr_check_range (rop, inex, rnd_mode);
138 }