The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/doc/div.txt
security/nss/lib/freebl/mpi/doc/div.txt
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:20c7521638fd |
|---|---|
| 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/. |
