1/* mpn_bdiv_qr -- Hensel division with precomputed inverse, returning quotient 2 and remainder. 3 4 Contributed to the GNU project by Torbjorn Granlund. 5 6 THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES. IT IS ONLY 7 SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST 8 GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE. 9 10Copyright 2006, 2007, 2009 Free Software Foundation, Inc. 11 12This file is part of the GNU MP Library. 13 14The GNU MP Library is free software; you can redistribute it and/or modify 15it under the terms of the GNU Lesser General Public License as published by 16the Free Software Foundation; either version 3 of the License, or (at your 17option) any later version. 18 19The GNU MP Library is distributed in the hope that it will be useful, but 20WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 21or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 22License for more details. 23 24You should have received a copy of the GNU Lesser General Public License 25along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 26 27#include "gmp.h" 28#include "gmp-impl.h" 29 30 31/* Computes Q = N / D mod B^n, 32 R = N - QD. */ 33 34mp_limb_t 35mpn_bdiv_qr (mp_ptr qp, mp_ptr rp, 36 mp_srcptr np, mp_size_t nn, 37 mp_srcptr dp, mp_size_t dn, 38 mp_ptr tp) 39{ 40 mp_limb_t di; 41 mp_limb_t rh; 42 43 if (BELOW_THRESHOLD (dn, DC_BDIV_QR_THRESHOLD) || 44 BELOW_THRESHOLD (nn - dn, DC_BDIV_QR_THRESHOLD)) 45 { 46 MPN_COPY (tp, np, nn); 47 binvert_limb (di, dp[0]); di = -di; 48 rh = mpn_sbpi1_bdiv_qr (qp, tp, nn, dp, dn, di); 49 MPN_COPY (rp, tp + nn - dn, dn); 50 } 51 else if (BELOW_THRESHOLD (dn, MU_BDIV_QR_THRESHOLD)) 52 { 53 MPN_COPY (tp, np, nn); 54 binvert_limb (di, dp[0]); di = -di; 55 rh = mpn_dcpi1_bdiv_qr (qp, tp, nn, dp, dn, di); 56 MPN_COPY (rp, tp + nn - dn, dn); 57 } 58 else 59 { 60 rh = mpn_mu_bdiv_qr (qp, rp, np, nn, dp, dn, tp); 61 } 62 63 return rh; 64} 65 66mp_size_t 67mpn_bdiv_qr_itch (mp_size_t nn, mp_size_t dn) 68{ 69 if (BELOW_THRESHOLD (dn, MU_BDIV_QR_THRESHOLD)) 70 return nn; 71 else 72 return mpn_mu_bdiv_qr_itch (nn, dn); 73} 74