Cryptography Reference
In-Depth Information
As preparation for determining
q
the three most-significant digits of part
(
a
i
a
i
−
1
...a
i
−
n
)
B
of the dividend multiplied by the scaling factor
d
are calcu-
lated and stored in the variables
ri
,
ri_1
,and
ri_2
. The case where the part of the
dividend under consideration has only three digits is handled as a special case.
In the first pass through the loop there are at least three digits present: On the
assumption that the divisor
b
itself has at least two digits, there exist the most-
significant digits
a
m
+
n
−
1
and
a
m
+
n
−
2
of the dividend, and the digit
a
m
+
n
was
set to zero during the initialization of
r_l
.
ri = (USHORT)((*msdptrr_l << d) + (*(msdptrr_l - 1) >> sbitsminusd));
ri_1 = (USHORT)((*(msdptrr_l - 1) << d) + (*(msdptrr_l - 2) >> sbitsminusd));
if (msdptrr_l-3>r_l)
/* there are four dividend digits */
{
ri_2 = (USHORT)((*(msdptrr_l - 2) << d) +
(*(msdptrr_l - 3) >> sbitsminusd));
}
else /* there are only three dividend digits */
{
ri_2 = (USHORT)(*(msdptrr_l - 2) << d);
}
Now comes the determination of
q
, stored in the variable
qhat
. Corresponding to
step 4 of the algorithm, we distinguish the cases
ri
=
bn_1
(frequent) and
ri
=
bn_1
(rare). The case
ri
>
bn_1
is excluded, on account of
r/b < B
. Therefore,
q
is set to the minimum of
(
r
i
B
+
r
i
−
1
)
/b
n
−
1
and
B −
1
.
if (ri != bn_1)
/* almost always */
{
qhat = (USHORT)((rhat = ((ULONG)ri << BITPERDGT) + (ULONG)ri_1) / bn_1);
right = ((rhat = (rhat - (ULONG)bn_1 * qhat)) << BITPERDGT) + ri_2;
If
bn_2 * qhat > right
,then
qhat
is too large by at least
1
and by at most
2
.
if ((left = (ULONG)bn_2 * qhat) > right)
{
qhat--;
