деление m
на n
:
int r = m;
int q = 0;
while( r >= n )
{
int k = 1;
int x = n;
int t;
while( ( t = x+x ) < r )
{
x = t;
k += k;
}
q += k;
r -= x;
}
Результат q
- частное, r
- остаток.
Идея состоит в том, что x+x
так же, как x*2
.
UPD:
Некоторые могут жаловаться, что r -= x
не является дополнением.Ну, мы можем обновить алгоритм, чтобы не использовать вычитание:
int p = 0;
int q = 0;
while( p+n <= m )
{
int k = 1;
int x = n;
int t;
while( p + ( t = x+x ) < m )
{
x = t;
k += k;
}
q += k;
p += x;
}
Результат - q
- частное.
Если нам понадобится остаток, тогда мы будем действовать следующим образом (p
-вывод из вышеперечисленного):
int r = 0;
while( p < m )
{
int x = 1;
int t;
while( p + ( t = x+x ) < m )
{
x = t;
}
r += x;
p += x;
}
Результат r
- остаток.
Алгоритм имеет явно полиномиальное (не экспоненциальное) время выполнения.