1 /* mpz_div -- divide two integers and produce a quotient.
3 Copyright (C) 1991 Free Software Foundation, Inc.
5 This file is part of the GNU MP Library.
7 The GNU MP Library is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 The GNU MP Library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with the GNU MP Library; see the file COPYING. If not, write to
19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
27 mpz_div (MP_INT *quot, const MP_INT *num, const MP_INT *den)
29 mpz_div (quot, num, den)
37 mp_size nsize = num->size;
38 mp_size dsize = den->size;
40 mp_size sign_quotient = nsize ^ dsize;
41 unsigned normalization_steps;
46 /* Ensure space is enough for quotient. */
48 qsize = nsize - dsize + 1; /* qsize cannot be bigger than this. */
55 if (quot->alloc < qsize)
56 _mpz_realloc (quot, qsize);
61 rp = (mp_ptr) alloca ((nsize + 1) * BYTES_PER_MP_LIMB);
63 count_leading_zeros (normalization_steps, dp[dsize - 1]);
65 /* Normalize the denominator and the numerator. */
66 if (normalization_steps != 0)
71 /* Shift up the denominator setting the most significant bit of
72 the most significant word. Use temporary storage not to clobber
73 the original contents of the denominator. */
74 tp = (mp_ptr) alloca (dsize * BYTES_PER_MP_LIMB);
75 (void) mpn_lshift (tp, dp, dsize, normalization_steps);
78 /* Shift up the numerator, possibly introducing a new most
79 significant word. Move the shifted numerator in the remainder
81 ndigit = mpn_lshift (rp, np, nsize, normalization_steps);
92 /* The denominator is already normalized, as required.
93 Copy it to temporary space if it overlaps with the quotient. */
96 dp = (mp_ptr) alloca (dsize * BYTES_PER_MP_LIMB);
97 MPN_COPY ((mp_ptr) dp, qp, dsize);
100 /* Move the numerator to the remainder. */
101 MPN_COPY (rp, np, nsize);
105 qsize = rsize - dsize + mpn_div (qp, rp, rsize, dp, dsize);
107 /* Normalize the quotient. We may have at most one leading
108 zero-word, so no loop is needed. */
110 qsize -= (qp[qsize - 1] == 0);
112 if (sign_quotient < 0)