1 1.1 mrg /* mpn_sbpi1_bdiv_qr -- schoolbook Hensel division with precomputed inverse, 2 1.1 mrg returning quotient and remainder. 3 1.1 mrg 4 1.1.1.4 mrg Contributed to the GNU project by Niels Mller and Torbjrn Granlund. 5 1.1 mrg 6 1.1 mrg THE FUNCTIONS IN THIS FILE ARE INTERNAL FUNCTIONS WITH MUTABLE INTERFACES. 7 1.1 mrg IT IS ONLY SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS 8 1.1 mrg ALMOST GUARANTEED THAT THEY'LL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE. 9 1.1 mrg 10 1.1.1.4 mrg Copyright 2006, 2009, 2011, 2012, 2017 Free Software Foundation, Inc. 11 1.1 mrg 12 1.1 mrg This file is part of the GNU MP Library. 13 1.1 mrg 14 1.1 mrg The GNU MP Library is free software; you can redistribute it and/or modify 15 1.1.1.3 mrg it under the terms of either: 16 1.1.1.3 mrg 17 1.1.1.3 mrg * the GNU Lesser General Public License as published by the Free 18 1.1.1.3 mrg Software Foundation; either version 3 of the License, or (at your 19 1.1.1.3 mrg option) any later version. 20 1.1.1.3 mrg 21 1.1.1.3 mrg or 22 1.1.1.3 mrg 23 1.1.1.3 mrg * the GNU General Public License as published by the Free Software 24 1.1.1.3 mrg Foundation; either version 2 of the License, or (at your option) any 25 1.1.1.3 mrg later version. 26 1.1.1.3 mrg 27 1.1.1.3 mrg or both in parallel, as here. 28 1.1 mrg 29 1.1 mrg The GNU MP Library is distributed in the hope that it will be useful, but 30 1.1 mrg WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 31 1.1.1.3 mrg or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 32 1.1.1.3 mrg for more details. 33 1.1 mrg 34 1.1.1.3 mrg You should have received copies of the GNU General Public License and the 35 1.1.1.3 mrg GNU Lesser General Public License along with the GNU MP Library. If not, 36 1.1.1.3 mrg see https://www.gnu.org/licenses/. */ 37 1.1 mrg 38 1.1 mrg #include "gmp-impl.h" 39 1.1 mrg 40 1.1 mrg 41 1.1.1.4 mrg /* Computes a binary quotient of size qn = un - dn. 42 1.1 mrg Output: 43 1.1 mrg 44 1.1.1.4 mrg Q = -U * D^{-1} mod B^qn, 45 1.1 mrg 46 1.1.1.4 mrg R = (U + Q * D) * B^(-qn) 47 1.1 mrg 48 1.1.1.4 mrg Stores the dn least significant limbs of R at {up + un - dn, dn}, 49 1.1.1.4 mrg and returns the carry from the addition N + Q*D. 50 1.1 mrg 51 1.1 mrg D must be odd. dinv is (-D)^-1 mod B. */ 52 1.1 mrg 53 1.1 mrg mp_limb_t 54 1.1 mrg mpn_sbpi1_bdiv_qr (mp_ptr qp, 55 1.1.1.4 mrg mp_ptr up, mp_size_t un, 56 1.1 mrg mp_srcptr dp, mp_size_t dn, mp_limb_t dinv) 57 1.1 mrg { 58 1.1 mrg mp_size_t i; 59 1.1.1.4 mrg mp_limb_t cy; 60 1.1 mrg 61 1.1 mrg ASSERT (dn > 0); 62 1.1.1.4 mrg ASSERT (un > dn); 63 1.1 mrg ASSERT ((dp[0] & 1) != 0); 64 1.1.1.4 mrg ASSERT (-(dp[0] * dinv) == 1); 65 1.1.1.4 mrg ASSERT (up == qp || !MPN_OVERLAP_P (up, un, qp, un - dn)); 66 1.1 mrg 67 1.1.1.4 mrg for (i = un - dn, cy = 0; i != 0; i--) 68 1.1 mrg { 69 1.1.1.4 mrg mp_limb_t q = dinv * up[0]; 70 1.1.1.4 mrg mp_limb_t hi = mpn_addmul_1 (up, dp, dn, q); 71 1.1.1.4 mrg *qp++ = q; 72 1.1.1.4 mrg 73 1.1.1.4 mrg hi += cy; 74 1.1.1.4 mrg cy = hi < cy; 75 1.1.1.4 mrg hi += up[dn]; 76 1.1.1.4 mrg cy += hi < up[dn]; 77 1.1.1.4 mrg up[dn] = hi; 78 1.1.1.4 mrg up++; 79 1.1 mrg } 80 1.1 mrg 81 1.1.1.4 mrg return cy; 82 1.1 mrg } 83
Indexes created Sat Jun 27 00:24:51 UTC 2026