Реализация арифметических операций. Как устроена?

Question

[AUN]

Здравствуйте.
Преамбула: мне необходимо разработать быстродействующий алгоритм, либо улучшить аналоги, улучшив их скорость.
Суть вопроса: у меня же нет четкого понимания как устроены непосредственно операции деления, умножения, вычисление корня и прочие. Что работает быстрее, что медленнее. Раньше не задумывался об этом. Хочу восполнить пробел. Посоветуйте литературу и куда копать.
Спасибо!

Answer 1

[tsarevfs]

Реализация зависит от платформы. Вы можете посмотреть во что компилируются интересующие вас операции для конкретного компилятора с помощью дизассемблера (в студии есть встроенный, для unix есть objdump -D > somefile.asm).
Вообще, оптимизации на уровне арифметических команд это последнее дело. Для начала желательно убедиться, что нет алгоритма с лучшей ассимптотикой (считая что все арифметические операции работают за 1).
Для обработки однотипных данных возможно получить ускорение за счет векторных операций из расширений процессора SSE* или на GPU.

Answer 2

[Evsign]

Читайте Чарльз Петцольд "К.О.Д"
Примерно к ~250 странице найдёте ответы на все вопросы.

Если вкратце:
Все операции производятся на битовом уровне.
Сложение - Базовая операция с помощью которой реализуются все другие.
Стандартный сумматор состоит из совокупности логических вентилей, т.е. из элементов И, ИЛИ, ИЛИ-НЕ, ИСКЛ-ИЛИ. Происходит по-битово от младших разрядов к старшим.
Вычитание - Реализуется с помощью дополнения до 1 (инвертация на битовом уровне и +1) и последующим сложением. Грубо говоря 5-2 == 5+(-2)
Умножение - Многократное сложение.
Деление - Многократное вычитание.

По-поводу скорости логично, что самое быстрое - сложение. Потом вычитание, ну и деление/умножение - одинаково.

Answer 3

[globuzer]

любые книги (как правило встречались советских времен) с математической обработкой ЭВМ, вплоть до схемотехники (дешифраторы, регистры и тд, там описываются очень подробно двоичные коды и системы) и начиная от различных базовых учебников по информатике (операции в двоичных кодах, дополнительные коды, системы счисления, как представляется информация в ЭВМ). очень доходчиво можно постичь весь низовой уровень операций ЭВМ (не важно какой платформы и архитектуры, так как это база) в книгах наших соотечественников, западных и восточных коллег (советских времен)

Answer 4

[AxisPod]

Берите спеки процессоров, там всё расписано. Все алгоритмы в обязательном порядке будут расписаны. Как вариант можно поискать быстрые реализации для Z80, он не умеет умножать и делить из коробки, во времена разработки для Z80 находил быстрые реализации.

Answer 5

[Don Kaban]

Увеличить скорость арифметических операций x86? В рамках x86? Че то Геделем пахнуло :)