1/* mpz_urandomm (rop, state, n) -- Generate a uniform pseudorandom 2 integer in the range 0 to N-1, using STATE as the random state 3 previously initialized by a call to gmp_randinit(). 4 5Copyright 2000, 2002 Free Software Foundation, Inc. 6 7This file is part of the GNU MP Library. 8 9The GNU MP Library is free software; you can redistribute it and/or modify 10it under the terms of the GNU Lesser General Public License as published by 11the Free Software Foundation; either version 3 of the License, or (at your 12option) any later version. 13 14The GNU MP Library is distributed in the hope that it will be useful, but 15WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 16or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 17License for more details. 18 19You should have received a copy of the GNU Lesser General Public License 20along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 21 22#include "gmp.h" 23#include "gmp-impl.h" 24#include "longlong.h" /* for count_leading_zeros */ 25 26 27#define MAX_URANDOMM_ITER 80 28 29void 30mpz_urandomm (mpz_ptr rop, gmp_randstate_t rstate, mpz_srcptr n) 31{ 32 mp_ptr rp, np, nlast; 33 mp_size_t nbits, size; 34 int count; 35 int pow2; 36 int cmp; 37 TMP_DECL; 38 39 size = ABSIZ (n); 40 if (size == 0) 41 DIVIDE_BY_ZERO; 42 43 nlast = &PTR (n)[size - 1]; 44 45 /* Detect whether n is a power of 2. */ 46 pow2 = POW2_P (*nlast); 47 if (pow2 != 0) 48 for (np = PTR (n); np < nlast; np++) 49 if (*np != 0) 50 { 51 pow2 = 0; /* Mark n as `not a power of two'. */ 52 break; 53 } 54 55 count_leading_zeros (count, *nlast); 56 nbits = size * GMP_NUMB_BITS - (count - GMP_NAIL_BITS) - pow2; 57 if (nbits == 0) /* nbits == 0 means that n was == 1. */ 58 { 59 SIZ (rop) = 0; 60 return; 61 } 62 63 TMP_MARK; 64 np = PTR (n); 65 if (rop == n) 66 { 67 mp_ptr tp; 68 tp = TMP_ALLOC_LIMBS (size); 69 MPN_COPY (tp, np, size); 70 np = tp; 71 } 72 73 /* Here the allocated size can be one too much if n is a power of 74 (2^GMP_NUMB_BITS) but it's convenient for using mpn_cmp below. */ 75 rp = MPZ_REALLOC (rop, size); 76 /* Clear last limb to prevent the case in which size is one too much. */ 77 rp[size - 1] = 0; 78 79 count = MAX_URANDOMM_ITER; /* Set iteration count limit. */ 80 do 81 { 82 _gmp_rand (rp, rstate, nbits); 83 MPN_CMP (cmp, rp, np, size); 84 } 85 while (cmp >= 0 && --count != 0); 86 87 if (count == 0) 88 /* Too many iterations; return result mod n == result - n */ 89 mpn_sub_n (rp, rp, np, size); 90 91 MPN_NORMALIZE (rp, size); 92 SIZ (rop) = size; 93 TMP_FREE; 94} 95