Разница между сравнением и добавлением

Является ли операция сложения (+) более сложной, чем операция сравнения (>), как в целых числах, так и в арифметике с плавающей запятой? Буду признателен за ответ в контексте как микропроцессорных, так и FPGA-систем.

Моя мысль: я думаю, что сравнение и сложение — это одно и то же, когда мы говорим о микропроцессорных системах, потому что сравнение a>b может быть решено путем проверки бита знака (a-b), то есть операции сложения. Но в контексте систем на основе FPGA, я полагаю, сложность оператора сравнения может быть уменьшена?


fpga
person ubaabd    schedule 25.06.2012    source источник
comment
Как это связано с С++? В языке (и для целочисленных типов) это просто базовые примитивные операции. Язык не учитывает, насколько они сложны в той или иной конкретной архитектуре.   -  person David Rodríguez - dribeas    schedule 25.06.2012
comment
Как вы определяете сложность? На FPGA, я думаю, вы говорите об использовании ресурсов. На микропроцессоре, я думаю, вы говорите о количестве циклов? В любом случае, это, вероятно, не по теме, и вместо этого должно быть на electronics.stackexchange.com   -  person Oliver Charlesworth    schedule 25.06.2012
comment
так что я также могу иметь мнение о разработчиках C++ (для настольных ПК). Я знаю, что они не очень заинтересованы в этом, но просто хотели узнать, как обстоят дела с микропроцессорами для настольных ПК.   -  person ubaabd    schedule 25.06.2012
comment
@ Оли Чарльзворт О, мой плохой. Я искал аппаратный стековый обмен, но оказалось, что такого понятия, как аппаратный точечный стековый обмен, не существует, поэтому я разместил его здесь! Я не знал о electronics.stackexchange.   -  person ubaabd    schedule 25.06.2012
comment
@Oli Charlesworth: Мой вопрос можно сформулировать следующим образом: если я сконструирую специальное оборудование для сравнения и не выполню его с использованием знакового бита (a-b)›0, сэкономит ли это мне количество циклов (системы на основе микропроцессоров) или использование ресурсов (системы на базе fpga).   -  person ubaabd    schedule 25.06.2012
comment
@DavidRodríguez-dribeas Да, я пропустил эту часть! Я снимаю тег C++ с вопроса.   -  person ubaabd    schedule 25.06.2012
comment
Может быть, agner.org/optimize/#manuals?   -  person BoBTFish    schedule 25.06.2012
comment
@BoBTFish Спасибо! Это удивительная ссылка. В нем говорится следующее: 1. Сравнение с плавающей запятой выполняется медленно, если не включен Pentium-II или более поздний набор инструкций. 2. Простые целочисленные операции, такие как сложение, вычитание, сравнение, битовые операции и операции сдвига, на большинстве микропроцессоров занимают всего один такт.   -  person ubaabd    schedule 25.06.2012

Ответы (2)


arrow_upward
1
arrow_downward

Сравнение немного «проще» для целых чисел, потому что нам нужно сравнить только каждый бит от старшего бита до младшего бита (без бита переноса, который необходим при сложении). Однако с точки зрения сложности оба являются O (log n).

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

person timos    schedule 25.06.2012
comment
Значит, бесполезно, если я преобразую алгоритм, основанный на дополнениях, в алгоритм, основанный на сравнениях? - person ubaabd; 25.06.2012
comment
Почему вы просто не задали свой реальный вопрос как свой вопрос - о том, как что-то оптимизировать? - person tenfour; 25.06.2012
comment
@tenfour На мой взгляд, всегда лучше задать конкретный вопрос на этих форумах, чем задавать его в общем. На вопрос «Как оптимизировать?» будет много ответов. тогда как единственное, что я хотел знать, является ли «сложение более сложным, чем сравнение» в современных системах. - person ubaabd; 25.06.2012

arrow_upward
2
arrow_downward

Теоретически сравнение может быть быстрее, вам просто нужно сравнить каждый бит, и это можно сделать параллельно. Это сравнение выполняется в два этапа: на одном сравниваются все биты, а на втором проверяется, включен ли один бит. (технически это (a0^b0)|(a1^b1)|...(an^bn). Все ai^bi можно выполнять одновременно. Это должно быть O(log(n))

Однако для добавления вам нужно распространить перенос от каждого бита к другому, чтобы вы получили O (n).

person mb14    schedule 25.06.2012