Cryptography Reference
In-Depth Information
product “divisor times quotient digit” from what is left of the dividend. Then for
the last time
q
must be reduced by
1
and the remainder updated. The algorithm
for division with remainder is now essentially the following procedure.
Algorithm for division with remainder of
a
=
a
m
+
n
−
1
a
m
+
n
−
2
...a
0
B
≥
0
by
b
=(
b
n
−
1
b
n
−
2
...b
0
)
B
>
0
1.
Determine the scaling factor
d
as given above.
2.
Set
r
:= (
r
m
+
n
r
n
+
m
−
1
r
m
+
n
−
2
...r
0
)
B
←
(0
a
m
+
n
−
1
a
m
+
n
−
2
...a
0
)
B
.
3.
Set
i ← m
+
n
,
j ← m
.
min
r
i
B
+
r
i
−
1
b
n
−
1
,B
1
with the digits
r
i
,
r
i
−
4.
Set
q
1
,
and
b
n
−
1
obtained from scaling by
d
(see above). If
b
n
−
2
ˆ
q>
←
−
r
i
B
+
r
i
−
1
− qb
n
−
1
B
+
r
i
−
2
, set
q ← q −
1
and repeat this
test.
5.
If
r
−
bq<
0
, set
q
←
q
−
1
.
6.
Set
r
:= (
r
i
r
i
−
1
...r
i
−
n
)
B
←
(
r
i
r
i
−
1
...r
i
−
n
)
B
− bq
and
q
j
← q
.
7.
Set
i ← i −
1
and
j ← j −
1
;if
i ≥ n
, go to step 4.
8.
Output
q
=(
q
m
q
m
−
1
...q
0
)
B
and
r
=(
r
n
−
1
r
n
−
2
...r
0
)
B
.
If the divisor has only a single digit
b
0
, then the process can be shortened
by initializing
r
with
r
0
and dividing the two digits
(
ra
i
)
B
by
b
0
with
remainder. Here
r
is overwritten by the remainder,
r ←
(
ra
i
)
B
− q
i
b
0
, and
a
i
runs through all the digits of the dividend. At the end,
r
contains the remainder
and
q
=(
q
m
q
m
−
1
...q
0
)
B
forms the quotient.
Now that we have at hand all the requisite processes for implementing
division, we present the C function for the above algorithm.
←
Function
:
division with remainder
int div_l (CLINT d1_l, CLINT d2_l, CLINT quot_l,
CLINT rem_l);
Syntax:
Input:
d1_l
(dividend),
d2_l
(divisor)
quot_l
(quotient),
rem_l
(remainder)
Output:
E_CLINT_OK
if all is ok
E_CLINT_DBZ
if division by 0
Return:
