for use by Divide(), corrects the underestimated quotient {Q1,Q0}
| 883 | |
| 884 | // for use by Divide(), corrects the underestimated quotient {Q1,Q0} |
| 885 | static void CorrectQuotientEstimate(word *R, word *T, word &Q0, word &Q1, const word *B, unsigned int N) |
| 886 | { |
| 887 | assert(N && N%2==0); |
| 888 | |
| 889 | if (Q1) |
| 890 | { |
| 891 | T[N] = T[N+1] = 0; |
| 892 | unsigned i; |
| 893 | for (i=0; i<N; i+=4) |
| 894 | AtomicMultiply(T+i, Q0, Q1, B[i], B[i+1]); |
| 895 | for (i=2; i<N; i+=4) |
| 896 | if (AtomicMultiplyAdd(T+i, Q0, Q1, B[i], B[i+1])) |
| 897 | T[i+5] += (++T[i+4]==0); |
| 898 | } |
| 899 | else |
| 900 | { |
| 901 | T[N] = LinearMultiply(T, B, Q0, N); |
| 902 | T[N+1] = 0; |
| 903 | } |
| 904 | |
| 905 | word borrow = Subtract(R, R, T, N+2); |
| 906 | assert(!borrow && !R[N+1]); |
| 907 | |
| 908 | while (R[N] || Compare(R, B, N) >= 0) |
| 909 | { |
| 910 | R[N] -= Subtract(R, R, B, N); |
| 911 | Q1 += (++Q0==0); |
| 912 | assert(Q0 || Q1); // no overflow |
| 913 | } |
| 914 | } |
| 915 | |
| 916 | // R[NB] -------- remainder = A%B |
| 917 | // Q[NA-NB+2] --- quotient = A/B |
no test coverage detected