1139790Simp/* mpn_dc_div_q -- divide-and-conquer division, returning exact quotient 2135783Smarcel only. 3135783Smarcel 4135783Smarcel Contributed to the GNU project by Torbjorn Granlund and Marco Bodrato. 5135783Smarcel 6135783Smarcel THE FUNCTION IN THIS FILE IS INTERNAL WITH A MUTABLE INTERFACE. IT IS ONLY 7135783Smarcel SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST 8135783Smarcel GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE. 9135783Smarcel 10135783SmarcelCopyright 2006, 2007, 2009, 2010 Free Software Foundation, Inc. 11135783Smarcel 12135783SmarcelThis file is part of the GNU MP Library. 13135783Smarcel 14135783SmarcelThe GNU MP Library is free software; you can redistribute it and/or modify 15135783Smarcelit under the terms of either: 16135783Smarcel 17135783Smarcel * the GNU Lesser General Public License as published by the Free 18135783Smarcel Software Foundation; either version 3 of the License, or (at your 19135783Smarcel option) any later version. 20135783Smarcel 21135783Smarcelor 22135783Smarcel 23135783Smarcel * the GNU General Public License as published by the Free Software 24135783Smarcel Foundation; either version 2 of the License, or (at your option) any 25135783Smarcel later version. 26135783Smarcel 27135783Smarcelor both in parallel, as here. 28135783Smarcel 29135783SmarcelThe GNU MP Library is distributed in the hope that it will be useful, but 30135783SmarcelWITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 31135783Smarcelor FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 32135783Smarcelfor more details. 33135783Smarcel 34135783SmarcelYou should have received copies of the GNU General Public License and the 35135783SmarcelGNU Lesser General Public License along with the GNU MP Library. If not, 36135783Smarcelsee https://www.gnu.org/licenses/. */ 37135783Smarcel 38135783Smarcel#include "gmp-impl.h" 39160764Sjhb 40135783Smarcel 41135783Smarcelmp_limb_t 42135783Smarcelmpn_dcpi1_div_q (mp_ptr qp, mp_ptr np, mp_size_t nn, 43135798Smarcel mp_srcptr dp, mp_size_t dn, gmp_pi1_t *dinv) 44135783Smarcel{ 45135783Smarcel mp_ptr tp, wp; 46135783Smarcel mp_limb_t qh; 47135783Smarcel mp_size_t qn; 48135783Smarcel TMP_DECL; 49162361Srwatson 50162361Srwatson TMP_MARK; 51208453Skib 52135832Smarcel ASSERT (dn >= 6); 53208453Skib ASSERT (nn - dn >= 3); 54208453Skib ASSERT (dp[dn-1] & GMP_NUMB_HIGHBIT); 55135783Smarcel 56135783Smarcel tp = TMP_ALLOC_LIMBS (nn + 1); 57208453Skib MPN_COPY (tp + 1, np, nn); 58135783Smarcel tp[0] = 0; 59208453Skib 60135783Smarcel qn = nn - dn; 61135783Smarcel wp = TMP_ALLOC_LIMBS (qn + 1); 62135783Smarcel 63135783Smarcel qh = mpn_dcpi1_divappr_q (wp, tp, nn + 1, dp, dn, dinv); 64135783Smarcel 65135783Smarcel if (wp[0] == 0) 66135783Smarcel { 67135783Smarcel mp_limb_t cy; 68135783Smarcel 69135783Smarcel if (qn > dn) 70135783Smarcel mpn_mul (tp, wp + 1, qn, dp, dn); 71135783Smarcel else 72135783Smarcel mpn_mul (tp, dp, dn, wp + 1, qn); 73135783Smarcel 74135783Smarcel cy = (qh != 0) ? mpn_add_n (tp + qn, tp + qn, dp, dn) : 0; 75135783Smarcel 76135783Smarcel if (cy || mpn_cmp (tp, np, nn) > 0) /* At most is wrong by one, no cycle. */ 77135783Smarcel qh -= mpn_sub_1 (qp, wp + 1, qn, 1); 78135783Smarcel else /* Same as below */ 79135783Smarcel MPN_COPY (qp, wp + 1, qn); 80208453Skib } 81135783Smarcel else 82135783Smarcel MPN_COPY (qp, wp + 1, qn); 83135783Smarcel 84135783Smarcel TMP_FREE; 85135783Smarcel return qh; 86135783Smarcel} 87135783Smarcel