div.txt (1530B)
1 Division 2 3 This describes the division algorithm used by the MPI library. 4 5 Input: a, b; a > b 6 Compute: Q, R; a = Qb + R 7 8 The input numbers are normalized so that the high-order digit of b is 9 at least half the radix. This guarantees that we have a reasonable 10 way to guess at the digits of the quotient (this method was taken from 11 Knuth, vol. 2, with adaptations). 12 13 To normalize, test the high-order digit of b. If it is less than half 14 the radix, multiply both a and b by d, where: 15 16 radix - 1 17 d = ----------- 18 bmax + 1 19 20 ...where bmax is the high-order digit of b. Otherwise, set d = 1. 21 22 Given normalize values for a and b, let the notation a[n] denote the 23 nth digit of a. Let #a be the number of significant figures of a (not 24 including any leading zeroes). 25 26 Let R = 0 27 Let p = #a - 1 28 29 while(p >= 0) 30 do 31 R = (R * radix) + a[p] 32 p = p - 1 33 while(R < b and p >= 0) 34 35 if(R < b) 36 break 37 38 q = (R[#R - 1] * radix) + R[#R - 2] 39 q = q / b[#b - 1] 40 41 T = b * q 42 43 while(T > L) 44 q = q - 1 45 T = T - b 46 endwhile 47 48 L = L - T 49 50 Q = (Q * radix) + q 51 52 endwhile 53 54 At this point, Q is the quotient, and R is the normalized remainder. 55 To denormalize R, compute: 56 57 R = (R / d) 58 59 At this point, you are finished. 60 61 ------------------------------------------------------------------ 62 This Source Code Form is subject to the terms of the Mozilla Public 63 # License, v. 2.0. If a copy of the MPL was not distributed with this 64 # file, You can obtain one at http://mozilla.org/MPL/2.0/.