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 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
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, and a<=b.
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 Future: The code doesn't demand a<=b actually, so maybe this could be
128 relaxed. All the places this is used currently call with a<=b though. */
129
130 int
mpn_jacobi_base(mp_limb_t a,mp_limb_t b,int result_bit1)131 mpn_jacobi_base (mp_limb_t a, mp_limb_t b, int result_bit1)
132 {
133 ASSERT (b & 1); /* b odd */
134 ASSERT (b != 1);
135 ASSERT (a <= b);
136
137 if (a == 0)
138 return 0;
139
140 PROCESS_TWOS_ANY;
141 if (a == 1)
142 goto done;
143
144 for (;;)
145 {
146 result_bit1 ^= JACOBI_RECIP_UU_BIT1 (a, b);
147 MP_LIMB_T_SWAP (a, b);
148
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