1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2  * gmpy2_mpz_divmod2exp.c                                                  *
3  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
4  * Python interface to the GMP or MPIR, MPFR, and MPC multiple precision   *
5  * libraries.                                                              *
6  *                                                                         *
7  * Copyright 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,               *
8  *           2008, 2009 Alex Martelli                                      *
9  *                                                                         *
10  * Copyright 2008, 2009, 2010, 2011, 2012, 2013, 2014,                     *
11  *           2015, 2016, 2017, 2018, 2019, 2020 Case Van Horsen            *
12  *                                                                         *
13  * This file is part of GMPY2.                                             *
14  *                                                                         *
15  * GMPY2 is free software: you can redistribute it and/or modify it under  *
16  * the terms of the GNU Lesser General Public License as published by the  *
17  * Free Software Foundation, either version 3 of the License, or (at your  *
18  * option) any later version.                                              *
19  *                                                                         *
20  * GMPY2 is distributed in the hope that it will be useful, but WITHOUT    *
21  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or   *
22  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public    *
23  * License for more details.                                               *
24  *                                                                         *
25  * You should have received a copy of the GNU Lesser General Public        *
26  * License along with GMPY2; if not, see <http://www.gnu.org/licenses/>    *
27  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
28 
29 
30 /* This file contains functions related to division and remainder by a power
31  * of two.
32  */
33 
34 /*
35  **************************************************************************
36  * Ceiling division and remainder by power of two.
37  **************************************************************************
38  */
39 
40 PyDoc_STRVAR(doc_c_divmod_2exp,
41 "c_divmod_2exp(x ,n) -> (quotient, remainder)\n\n"
42 "Return the quotient and remainder of x divided by 2**n. The quotient\n"
43 "is rounded towards +Inf (ceiling rounding) and the remainder will\n"
44 "be negative. x must be an integer. n must be >0.");
45 
46 static PyObject *
GMPy_MPZ_c_divmod_2exp(PyObject * self,PyObject * args)47 GMPy_MPZ_c_divmod_2exp(PyObject *self, PyObject *args)
48 {
49     mp_bitcnt_t nbits;
50     PyObject *result = NULL;
51     MPZ_Object *q = NULL, *r = NULL, *tempx = NULL;
52 
53     if (PyTuple_GET_SIZE(args) != 2) {
54         TYPE_ERROR("c_divmod_2exp() requires 'mpz','int' arguments");
55         return NULL;
56     }
57 
58     nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
59     if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
60         return NULL;
61     }
62 
63     if (!(tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL)) ||
64         !(q = GMPy_MPZ_New(NULL)) ||
65         !(r = GMPy_MPZ_New(NULL)) ||
66         !(result = PyTuple_New(2))) {
67 
68         Py_XDECREF(result);
69         Py_XDECREF((PyObject*)tempx);
70         Py_XDECREF((PyObject*)q);
71         Py_XDECREF((PyObject*)r);
72         return NULL;
73     }
74 
75     mpz_cdiv_q_2exp(q->z, tempx->z, nbits);
76     mpz_cdiv_r_2exp(r->z, tempx->z, nbits);
77 
78     Py_DECREF((PyObject*)tempx);
79     PyTuple_SET_ITEM(result, 0, (PyObject*)q);
80     PyTuple_SET_ITEM(result, 1, (PyObject*)r);
81     return result;
82 }
83 
84 PyDoc_STRVAR(doc_c_div_2exp,
85 "c_div_2exp(x, n) -> quotient\n\n"
86 "Returns the quotient of x divided by 2**n. The quotient is rounded\n"
87 "towards +Inf (ceiling rounding). x must be an integer. n must be >0.");
88 
89 static PyObject *
GMPy_MPZ_c_div_2exp(PyObject * self,PyObject * args)90 GMPy_MPZ_c_div_2exp(PyObject *self, PyObject *args)
91 {
92     mp_bitcnt_t nbits;
93     MPZ_Object *result, *tempx;
94 
95     if (PyTuple_GET_SIZE(args) != 2) {
96         TYPE_ERROR("c_div_2exp() requires 'mpz','int' arguments");
97         return NULL;
98     }
99 
100     nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
101     if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
102         return NULL;
103     }
104 
105     tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL);
106     result = GMPy_MPZ_New(NULL);
107     if (!tempx || !result) {
108         Py_XDECREF((PyObject*)result);
109         Py_XDECREF((PyObject*)tempx);
110         return NULL;
111     }
112 
113     mpz_cdiv_q_2exp(result->z, tempx->z, nbits);
114     Py_DECREF((PyObject*)tempx);
115     return (PyObject*)result;
116 }
117 
118 PyDoc_STRVAR(doc_c_mod_2exp,
119 "c_mod_2exp(x, n) -> remainder\n\n"
120 "Return the remainder of x divided by 2**n. The remainder will be\n"
121 "negative. x must be an integer. n must be >0.");
122 
123 static PyObject *
GMPy_MPZ_c_mod_2exp(PyObject * self,PyObject * args)124 GMPy_MPZ_c_mod_2exp(PyObject *self, PyObject *args)
125 {
126     mp_bitcnt_t nbits;
127     MPZ_Object *result, *tempx;
128 
129     if (PyTuple_GET_SIZE(args) != 2) {
130         TYPE_ERROR("c_mod_2exp() requires 'mpz','int' arguments");
131         return NULL;
132     }
133 
134     nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
135     if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
136         return NULL;
137     }
138 
139     tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL);
140     result = GMPy_MPZ_New(NULL);
141     if (!tempx || !result) {
142         Py_XDECREF((PyObject*)result);
143         Py_XDECREF((PyObject*)tempx);
144         return NULL;
145     }
146 
147     mpz_cdiv_r_2exp(result->z, tempx->z, nbits);
148     Py_DECREF((PyObject*)tempx);
149     return (PyObject*)result;
150 }
151 
152 /*
153  **************************************************************************
154  * Floor division and remainder by power of two.
155  **************************************************************************
156  */
157 
158 PyDoc_STRVAR(doc_f_divmod_2exp,
159 "f_divmod_2exp(x, n) -> (quotient, remainder)\n\n"
160 "Return quotient and remainder after dividing x by 2**n. The quotient\n"
161 "is rounded towards -Inf (floor rounding) and the remainder will be\n"
162 "positive. x must be an integer. n must be >0.");
163 
164 static PyObject *
GMPy_MPZ_f_divmod_2exp(PyObject * self,PyObject * args)165 GMPy_MPZ_f_divmod_2exp(PyObject *self, PyObject *args)
166 {
167     mp_bitcnt_t nbits;
168     PyObject *result;
169     MPZ_Object *q, *r, *tempx;
170 
171     if (PyTuple_GET_SIZE(args) != 2) {
172         TYPE_ERROR("f_divmod_2exp() requires 'mpz','int' arguments");
173         return NULL;
174     }
175 
176     nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
177     if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
178         return NULL;
179     }
180 
181     tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL);
182     q = GMPy_MPZ_New(NULL);
183     r = GMPy_MPZ_New(NULL);
184     result = PyTuple_New(2);
185     if (!tempx || !q || !r || !result) {
186         Py_XDECREF(result);
187         Py_XDECREF((PyObject*)tempx);
188         Py_XDECREF((PyObject*)q);
189         Py_XDECREF((PyObject*)r);
190         return NULL;
191     }
192 
193     mpz_fdiv_q_2exp(q->z, tempx->z, nbits);
194     mpz_fdiv_r_2exp(r->z, tempx->z, nbits);
195 
196     Py_DECREF((PyObject*)tempx);
197     PyTuple_SET_ITEM(result, 0, (PyObject*)q);
198     PyTuple_SET_ITEM(result, 1, (PyObject*)r);
199     return result;
200 }
201 
202 PyDoc_STRVAR(doc_f_div_2exp,
203 "f_div_2exp(x, n) -? quotient\n\n"
204 "Return the quotient of x divided by 2**n. The quotient is rounded\n"
205 "towards -Inf (floor rounding). x must be an integer. n must be >0.");
206 
207 static PyObject *
GMPy_MPZ_f_div_2exp(PyObject * self,PyObject * args)208 GMPy_MPZ_f_div_2exp(PyObject *self, PyObject *args)
209 {
210     mp_bitcnt_t nbits;
211     MPZ_Object *result, *tempx;
212 
213     if (PyTuple_GET_SIZE(args) != 2) {
214         TYPE_ERROR("f_div_2exp() requires 'mpz','int' arguments");
215         return NULL;
216     }
217 
218     nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
219     if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
220         return NULL;
221     }
222 
223     tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL);
224     result = GMPy_MPZ_New(NULL);
225     if (!tempx || !result) {
226         Py_XDECREF((PyObject*)result);
227         Py_XDECREF((PyObject*)tempx);
228         return NULL;
229     }
230 
231     mpz_fdiv_q_2exp(result->z, tempx->z, nbits);
232     Py_DECREF((PyObject*)tempx);
233     return (PyObject*)result;
234 }
235 
236 PyDoc_STRVAR(doc_f_mod_2exp,
237 "f_mod_2exp(x, n) -> remainder\n\n"
238 "Return remainder of x divided by 2**n. The remainder will be\n"
239 "positive. x must be an integer. n must be >0.");
240 
241 static PyObject *
GMPy_MPZ_f_mod_2exp(PyObject * self,PyObject * args)242 GMPy_MPZ_f_mod_2exp(PyObject *self, PyObject *args)
243 {
244     mp_bitcnt_t nbits;
245     MPZ_Object *result, *tempx;
246 
247     if (PyTuple_GET_SIZE(args) != 2) {
248         TYPE_ERROR("f_mod_2exp() requires 'mpz','int' arguments");
249         return NULL;
250     }
251 
252     nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
253     if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
254         return NULL;
255     }
256 
257     tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL);
258     result = GMPy_MPZ_New(NULL);
259     if (!tempx || !result) {
260         Py_XDECREF((PyObject*)result);
261         Py_XDECREF((PyObject*)tempx);
262         return NULL;
263     }
264 
265     mpz_fdiv_r_2exp(result->z, tempx->z, nbits);
266     Py_DECREF((PyObject*)tempx);
267     return (PyObject*)result;
268 }
269 
270 /*
271  **************************************************************************
272  * Truncating division and remainder by power of two.
273  **************************************************************************
274  */
275 
276 PyDoc_STRVAR(doc_t_divmod_2exp,
277 "t_divmod_2exp(x, n) -> (quotient, remaidner)\n\n"
278 "Return the quotient and remainder of x divided by 2**n. The quotient\n"
279 "is rounded towards zero (truncation) and the remainder will have the\n"
280 "same sign as x. x must be an integer. n must be >0.");
281 
282 static PyObject *
GMPy_MPZ_t_divmod_2exp(PyObject * self,PyObject * args)283 GMPy_MPZ_t_divmod_2exp(PyObject *self, PyObject *args)
284 {
285     mp_bitcnt_t nbits;
286     MPZ_Object *q, *r, *tempx;
287     PyObject *result;
288 
289     if (PyTuple_GET_SIZE(args) != 2) {
290         TYPE_ERROR("t_divmod_2exp() requires 'mpz','int' arguments");
291         return NULL;
292     }
293 
294     nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
295     if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
296         return NULL;
297     }
298 
299     tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL);
300     q = GMPy_MPZ_New(NULL);
301     r = GMPy_MPZ_New(NULL);
302     result = PyTuple_New(2);
303     if (!tempx || !q || !r || !result) {
304         Py_XDECREF(result);
305         Py_XDECREF((PyObject*)tempx);
306         Py_XDECREF((PyObject*)q);
307         Py_XDECREF((PyObject*)r);
308         return NULL;
309     }
310 
311     mpz_tdiv_q_2exp(q->z, tempx->z, nbits);
312     mpz_tdiv_r_2exp(r->z, tempx->z, nbits);
313 
314     Py_DECREF((PyObject*)tempx);
315     PyTuple_SET_ITEM(result, 0, (PyObject*)q);
316     PyTuple_SET_ITEM(result, 1, (PyObject*)r);
317     return result;
318 }
319 
320 PyDoc_STRVAR(doc_t_div_2exp,
321 "t_div_2exp(x, n) -> quotient\n\n"
322 "Return the quotient of x divided by 2**n. The quotient is rounded\n"
323 "towards zero (truncation). n must be >0.");
324 
325 static PyObject *
GMPy_MPZ_t_div_2exp(PyObject * self,PyObject * args)326 GMPy_MPZ_t_div_2exp(PyObject *self, PyObject *args)
327 {
328     mp_bitcnt_t nbits;
329     MPZ_Object *result, *tempx;
330 
331     if (PyTuple_GET_SIZE(args) != 2) {
332         TYPE_ERROR("t_div_2exp() requires 'mpz','int' arguments");
333         return NULL;
334     }
335 
336     nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
337     if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
338         return NULL;
339     }
340 
341     tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL);
342     result = GMPy_MPZ_New(NULL);
343     if (!tempx || !result) {
344         Py_XDECREF((PyObject*)result);
345         Py_XDECREF((PyObject*)tempx);
346         return NULL;
347     }
348 
349     mpz_tdiv_q_2exp(result->z, tempx->z, nbits);
350     Py_DECREF((PyObject*)tempx);
351     return (PyObject*)result;
352 }
353 
354 PyDoc_STRVAR(doc_t_mod_2exp,
355 "t_mod_2exp(x, n) -> remainder\n\n"
356 "Return the remainder of x divided by 2**n. The remainder will have\n"
357 "the same sign as x. x must be an integer. n must be >0.");
358 
359 static PyObject *
GMPy_MPZ_t_mod_2exp(PyObject * self,PyObject * args)360 GMPy_MPZ_t_mod_2exp(PyObject *self, PyObject *args)
361 {
362     mp_bitcnt_t nbits;
363     MPZ_Object *result, *tempx;
364 
365     if (PyTuple_GET_SIZE(args) != 2) {
366         TYPE_ERROR("t_mod_2exp() requires 'mpz','int' arguments");
367         return NULL;
368     }
369 
370     nbits = mp_bitcnt_t_From_Integer(PyTuple_GET_ITEM(args, 1));
371     if (nbits == (mp_bitcnt_t)(-1) && PyErr_Occurred()) {
372         return NULL;
373     }
374 
375     tempx = GMPy_MPZ_From_Integer(PyTuple_GET_ITEM(args, 0), NULL);
376     result = GMPy_MPZ_New(NULL);
377     if (!tempx || !result) {
378         Py_XDECREF((PyObject*)result);
379         Py_XDECREF((PyObject*)tempx);
380         return NULL;
381     }
382 
383     mpz_tdiv_r_2exp(result->z, tempx->z, nbits);
384     Py_DECREF((PyObject*)tempx);
385     return (PyObject*)result;
386 }
387