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-2018 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 http://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 } 139