ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013
10
На первом этапе в теле функции
ByteBitDiv
(
) выполняется поиск
частного от деления с использованием функции дихотомического
поиска множителя
DMultiplier
( ) [2]. Результат поиска помещается в
переменную
nc = DMultiplier
(
c, a, na, b, nb, s
), для чего затрачивает-
ся еще одна операция:
(
)
1min
min
1
1 7 43 10 43
DMultiplier
W W
nb na nb na nb
= +
= + + + +
− =
(
)
8 47 10 43
;
nb na na na nb
= + + +
−
(
)
1max
max
1
1 109 367 106 251
DMultiplier
W W
nb na nb na nb
= +
= + +
−
+
− =
(
)
110 367 106 251
.
nb na nb na nb
= +
−
+
−
На втором этапе вычисляется позиция старшей цифры частного
int k = nc – 1
, для чего требуется выполнить две операции:
2
2.
W
=
На третьем этапе проводится корректировка позиции знака с по-
мощью инструкции условия
if
(
c
[
k
]
!= 0
)
k += 1
. По две операции
затрачиваются на проверку условия
c
[
k
]
!= 0
и на корректировку
k += 1
:
3 min
2;
W
=
3 max
2 2 4.
W
= + =
На четвертом этапе частное получает соответствующий знак
if
(
a
[
na – 1
]
== b
[
nb – 1
] )
c
[
k
]
= 43
;
else c
[
k
]
= 45
, что занимает семь
операций:
4
7.
W
=
На заключительном, пятом этапе выполняется инструкция
return
k + 1
:
5
1
W
=
.
Теперь можно получить общую оценку количества операций, вы-
полняемых при делении целых чисел произвольного размера:
min
1min
2
3 min
4
5
ByteBitDiv
W W W W W W
= + + + + =
(
)
8 47 10 43
2 2 7 1
nb na nb na nb
= + + +
− + + + + =
(
)
20 47
43
;
nb na nb na nb
= + + +
−
1,2,3,4,5,6,7,8,9 11