Насколько быстро деление?

Question

Когда-то я должен был сделать короткий ассемблерный код для деления на числа, которые не являются степенью 2. Мое решение заключалось в том, чтобы вычитать делитель в циклах, а количество циклов было реальным результатом. Есть ли что-нибудь быстрее? Какой обычный способ разобраться с этим?

Answer 1

Повторное вычитание - опасно неэффективный способ деления. В худшем случае N-битное деление может занять O(2**N) вычитаний !!

@ Ответ Йоханнеса содержит ссылку, которая дает вам алгоритмы, которые работают намного лучше.

Если бы меня попросили реализовать деление на ассемблере, я бы, вероятно, сделал бы обширный поиск существующей библиотеки числовых подпрограмм. Это такая проблема, когда требуется много опыта, чтобы найти оптимальный код.

РЕДАКТИРОВАТЬ : в ответ на комментарий ОП:

Просто сейчас я делаю какую-то программу на C ++ и решаю, использовать ли деление для решения одной проблемы или придумать что-то еще, чтобы сделать это быстрее.

Я предлагаю вам просто использовать деление и оставить его компилятору C ++ для генерации наиболее эффективной последовательности инструкций для достижения требуемого результата для вашей конкретной целевой платформы.

Answer 2

Существует множество алгоритмов, упомянутых и подробно описанных в Wikipedia .