Как реализовать деление по сложению?

Question

Вопрос для интервью.

Как реализовать деление по сложению?Предположим, что они все int.

Моя идея

1. Добавляйте делитель в себя, пока он не станет больше, чем дивиденд.Каждую итерацию сохраняйте результат суммирования перед добавлением.
2. Частное есть сумма результата до последнего добавления.остаток можно посчитать, добавив 1 до quotient * divisor + reminder == dividend.

Это O(e^n), есть идеи получше?битовая операция?

Answer 1

деление 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 - остаток.

Алгоритм имеет явно полиномиальное (не экспоненциальное) время выполнения.

Answer 2

В цифровой арифметике мы можем назвать восстановительные и невосстанавливающие методы как простые алгоритмы деления, основанные на сложении / вычитании. Количество итераций в этих методах составляет O(n) (где n - количество битов). Существуют такие методы, как Ньютон-Рафсон или обратный расчет, основанные на умножении, и число итераций в них составляет O(log n). Взгляните на http://en.wikipedia.org/wiki/Division_%28digital%29

Answer 3

Вы бы разбили деление на его логарифмические компоненты и затем вычислили их.