1 /* mpn_jacobi_base -- limb/limb Jacobi symbol with restricted arguments. 2 3 THIS INTERFACE IS PRELIMINARY AND MIGHT DISAPPEAR OR BE SUBJECT TO 4 INCOMPATIBLE CHANGES IN A FUTURE RELEASE OF GMP. 5 6 Copyright 1999, 2000, 2001, 2002, 2010 Free Software Foundation, Inc. 7 8 This file is part of the GNU MP Library. 9 10 The GNU MP 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 MP 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 MP Library. If not, see http://www.gnu.org/licenses/. */ 22 23 #include "gmp.h" 24 #include "gmp-impl.h" 25 #include "longlong.h" 26 27 28 /* Use the simple loop by default. The generic count_trailing_zeros is not 29 very fast, and the extra trickery of method 3 has proven to be less use 30 than might have been though. */ 31 #ifndef JACOBI_BASE_METHOD 32 #define JACOBI_BASE_METHOD 2 33 #endif 34 35 36 /* Use count_trailing_zeros. */ 37 #if JACOBI_BASE_METHOD == 1 38 #define PROCESS_TWOS_ANY \ 39 { \ 40 mp_limb_t twos; \ 41 count_trailing_zeros (twos, a); \ 42 result_bit1 ^= JACOBI_TWOS_U_BIT1 (twos, b); \ 43 a >>= twos; \ 44 } 45 #define PROCESS_TWOS_EVEN PROCESS_TWOS_ANY 46 #endif 47 48 /* Use a simple loop. A disadvantage of this is that there's a branch on a 49 50/50 chance of a 0 or 1 low bit. */ 50 #if JACOBI_BASE_METHOD == 2 51 #define PROCESS_TWOS_EVEN \ 52 { \ 53 int two; \ 54 two = JACOBI_TWO_U_BIT1 (b); \ 55 do \ 56 { \ 57 a >>= 1; \ 58 result_bit1 ^= two; \ 59 ASSERT (a != 0); \ 60 } \ 61 while ((a & 1) == 0); \ 62 } 63 #define PROCESS_TWOS_ANY \ 64 if ((a & 1) == 0) \ 65 PROCESS_TWOS_EVEN; 66 #endif 67 68 /* Process one bit arithmetically, then a simple loop. This cuts the loop 69 condition down to a 25/75 chance, which should branch predict better. 70 The CPU will need a reasonable variable left shift. */ 71 #if JACOBI_BASE_METHOD == 3 72 #define PROCESS_TWOS_EVEN \ 73 { \ 74 int two, mask, shift; \ 75 \ 76 two = JACOBI_TWO_U_BIT1 (b); \ 77 mask = (~a & 2); \ 78 a >>= 1; \ 79 \ 80 shift = (~a & 1); \ 81 a >>= shift; \ 82 result_bit1 ^= two ^ (two & mask); \ 83 \ 84 while ((a & 1) == 0) \ 85 { \ 86 a >>= 1; \ 87 result_bit1 ^= two; \ 88 ASSERT (a != 0); \ 89 } \ 90 } 91 #define PROCESS_TWOS_ANY \ 92 { \ 93 int two, mask, shift; \ 94 \ 95 two = JACOBI_TWO_U_BIT1 (b); \ 96 shift = (~a & 1); \ 97 a >>= shift; \ 98 \ 99 mask = shift << 1; \ 100 result_bit1 ^= (two & mask); \ 101 \ 102 while ((a & 1) == 0) \ 103 { \ 104 a >>= 1; \ 105 result_bit1 ^= two; \ 106 ASSERT (a != 0); \ 107 } \ 108 } 109 #endif 110 111 #if JACOBI_BASE_METHOD < 4 112 /* Calculate the value of the Jacobi symbol (a/b) of two mp_limb_t's, but 113 with a restricted range of inputs accepted, namely b>1, b odd. 114 115 The initial result_bit1 is taken as a parameter for the convenience of 116 mpz_kronecker_ui() et al. The sign changes both here and in those 117 routines accumulate nicely in bit 1, see the JACOBI macros. 118 119 The return value here is the normal +1, 0, or -1. Note that +1 and -1 120 have bit 1 in the "BIT1" sense, which could be useful if the caller is 121 accumulating it into some extended calculation. 122 123 Duplicating the loop body to avoid the MP_LIMB_T_SWAP(a,b) would be 124 possible, but a couple of tests suggest it's not a significant speedup, 125 and may even be a slowdown, so what's here is good enough for now. */ 126 127 int 128 mpn_jacobi_base (mp_limb_t a, mp_limb_t b, int result_bit1) 129 { 130 ASSERT (b & 1); /* b odd */ 131 ASSERT (b != 1); 132 133 if (a == 0) 134 return 0; 135 136 PROCESS_TWOS_ANY; 137 if (a == 1) 138 goto done; 139 140 if (a >= b) 141 goto a_gt_b; 142 143 for (;;) 144 { 145 result_bit1 ^= JACOBI_RECIP_UU_BIT1 (a, b); 146 MP_LIMB_T_SWAP (a, b); 147 148 a_gt_b: 149 do 150 { 151 /* working on (a/b), a,b odd, a>=b */ 152 ASSERT (a & 1); 153 ASSERT (b & 1); 154 ASSERT (a >= b); 155 156 if ((a -= b) == 0) 157 return 0; 158 159 PROCESS_TWOS_EVEN; 160 if (a == 1) 161 goto done; 162 } 163 while (a >= b); 164 } 165 166 done: 167 return JACOBI_BIT1_TO_PN (result_bit1); 168 } 169 #endif 170 171 #if JACOBI_BASE_METHOD == 4 172 /* Computes (a/b) for odd b > 1 and any a. The initial bit is taken as a 173 * parameter. We have no need for the convention that the sign is in 174 * bit 1, internally we use bit 0. */ 175 176 /* FIXME: Could try table-based count_trailing_zeros. */ 177 int 178 mpn_jacobi_base (mp_limb_t a, mp_limb_t b, int bit) 179 { 180 int c; 181 182 ASSERT (b & 1); 183 ASSERT (b > 1); 184 185 if (a == 0) 186 /* This is the only line which depends on b > 1 */ 187 return 0; 188 189 bit >>= 1; 190 191 /* Below, we represent a and b shifted right so that the least 192 significant one bit is implicit. */ 193 194 b >>= 1; 195 196 count_trailing_zeros (c, a); 197 bit ^= c & (b ^ (b >> 1)); 198 199 /* We may have c==GMP_LIMB_BITS-1, so we can't use a>>c+1. */ 200 a >>= c; 201 a >>= 1; 202 203 do 204 { 205 mp_limb_t t = a - b; 206 mp_limb_t bgta = LIMB_HIGHBIT_TO_MASK (t); 207 208 if (t == 0) 209 return 0; 210 211 /* If b > a, invoke reciprocity */ 212 bit ^= (bgta & a & b); 213 214 /* b <-- min (a, b) */ 215 b += (bgta & t); 216 217 /* a <-- |a - b| */ 218 a = (t ^ bgta) - bgta; 219 220 /* Number of trailing zeros is the same no matter if we look at 221 * t or a, but using t gives more parallelism. */ 222 count_trailing_zeros (c, t); 223 c ++; 224 /* (2/b) = -1 if b = 3 or 5 mod 8 */ 225 bit ^= c & (b ^ (b >> 1)); 226 a >>= c; 227 } 228 while (b > 0); 229 230 return 1-2*(bit & 1); 231 } 232 #endif /* JACOBI_BASE_METHOD == 4 */ 233