Нужна функция Sign без проверки условий

@Hrethgir · 09.07.2015, 15:11. **Показов** 4527. **Ответов** 40

Студворк — интернет-сервис помощи студентам

Я пока не нашёл способа, но ищу.

@x128 · 11.07.2015, 17:44

Странная постановка задачи... Что значит "без проверки условий"?
Если под этим термином подразумевается проверка значения и переход в зависимости от результата, а задача стоит в отказе от джампа в качестве оптимизации, в таком случае данную функцию можно написать так:

Delphi
1
2
3
4
function Sign(const a: Integer):ShortInt;
begin
  Result:=Ord(a>0)-Ord(a<0);
end;

эквивалент на ASMе:

Assembler
1
2
3
4
  or    eax, eax
  sets  ah
  setg  al
  sub   al, ah

@Shamil1 · 11.07.2015, 21:08

Сообщение от x128

эквивалент на ASMе:

И это работает? Можете дать ссылку на ideone?

Добавлено через 14 минут
Я предлагаю такой вариант (4 инструкции, не считая загрузки и выгрузки):

Assembler
1
2
3
4
5
6
    movl    x, %eax      #  x = signum(x);
    addl    %eax, %eax       
    sbbl    %ebx, %ebx
    negl    %eax
    adcl    %ebx, %ebx
    movl    %ebx, x

Добавлено через 1 минуту
http://ideone.com/3TrXQE
Перед тем как запускать, можно кликнуть edit, затем кликнуть input и ввести какое-нибудь число.

Добавлено через 12 минут
eax = eax + eax (при этом carry = 1 для отрицательных eax)
ebx = ebx - ebx - carry == -carry
eax = -eax (при этом carry = 1 для всех eax кроме 0)
ebx = ebx +ebx + carry (-1 + -1 + 1 для отрицательных eax, 0 + 0 + 1 для положительных, 0 + 0 + 0 для нуля)

@x128 · 11.07.2015, 23:56

Сообщение от Shamil1

И это работает? Можете дать ссылку на ideone?

Конечно работает. http://ideone.com/6OWFXM

@castorsky · 12.07.2015, 00:29

Сообщение от Shamil1

И это работает?

С такими языками где не сильно строгая типизация - конечно.

@Shamil1 · 12.07.2015, 02:34

Оказывается, там магия в строке:

Pascal
1
function Sign(const a: Integer):ShortInt;

И почему-то у меня вот эта строка даёт другой результат:

Assembler
1
    sub     %al, %ah

@x128 · 12.07.2015, 10:48

Сообщение от Shamil1

И почему-то у меня вот эта строка даёт другой результат:

Я плохо знаком с синтаксисом AT&T, но если я не ошибаюсь, порядок операндов должен быть обратным, т.е. "subb %ah, %al".

Code
1
2
3
if eax>0 then al:=1 else al:=0
if eax<0 then ah:=1 else ah:=0
result:=al-ah

т.е. для любого положительного числа al:=1; ah:=0, для нуля al:=0; ah:=0, для отрицательного al:=0; ah:=1

@castorsky · 12.07.2015, 12:29

Не по теме:

Не понимаю зачем вы полезли в ассемблер

Всё просто:

C
1
2
3
4
int
sign (int n) {
  return (n > 0) - (n < 0);
}

и прыжков нет, и задача решена.

Добавлено через 2 минуты
Согласно стандарту языка си сравнения дают результат 0 как ложь или 1 как истина. Других значений быть не может. А вот стандарта паскаля я не знаю.

@Shamil1 · 12.07.2015, 12:39

Сообщение от x128

если я не ошибаюсь, порядок операндов должен быть обратным

Вроде заработало:

Assembler
1
2
3
4
5
6
7
8
    movl    x, %eax      #  x = signum(x);
    or      %eax, %eax       
    sets    %ah
    setg    %al
    sub     %ah, %al
    cbw
    cwde
    movl    %eax, x

Сообщение от x128

т.е. для любого положительного числа al:=1; ah:=0, для нуля al:=0; ah:=0, для отрицательного al:=0; ah:=1

Это понятно. Магия была в слове shortint, на которое я сначала не обратил внимания. Ну и вообще, весь процесс перемещения значений из переменных в регистры и обратно не очевиден и остаётся за кадром.

@Hrethgir · 12.07.2015, 16:42 **[ТС]**

проверять на 0 надо, потому что на 0 делить нельзя, а математика правил математики не знает.
возвращаясь к выражению, нужно в первую очередь определить x на линейке, для чего производится операция
x+1
и в дальнейшем нужно привести всё это к следующему виду
x=(x+1)/x,
если результат больше входящих данных, то x положительный, если результат меньше входящих данных, то x отрицательный.
но, похоже, это ёмко очень для компьютера. по крайней мере, ёмче обычных сравнений, пусть даже через while

@x128 · 12.07.2015, 17:18

Сообщение от castorsky

Всё просто:

Капитан очевидность собственной персоной

Вот мой первый ответ с примером реализации "кликать сюда", предлагаю найти 10 отличий.

Сообщение от castorsky

Не понимаю зачем вы полезли в ассемблер

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

Сообщение от Shamil1

Магия была в слове shortint

Тут скорее не магия, а желание сэкономить на спичках. Результат функции ложится в байт и команда setcc принимает только байт. В случае с возвратом двойного слова пришлось бы выполнить еще одну команду "movsx eax, al".

Сообщение от Hretgir

ёмче обычных сравнений, пусть даже через while

Использование циклов это вообще за гранью зла, тут и проверка условий с джампами, и плохая читаемость, хуже этого только предложение использовать try/except.

@castorsky · 12.07.2015, 19:51

Сообщение от x128

Капитан очевидность собственной персоной
Вот мой первый ответ с примером реализации "кликать сюда", предлагаю найти 10 отличий.

Если Вы заметили, я отметил Ваш пост как "лучшый ответ", написал то же на си, и написал свои пояснения относительно возможнных проблем.

@x128 · 12.07.2015, 20:11

castorsky, не собирался обидеть, просто ответ выглядит как "всё просто, а вы залезли в дебри", вероятно это я торможу...

@Hrethgir · 13.07.2015, 17:13 **[ТС]**

Сообщение от x128

Использование циклов это вообще за гранью зла, тут и проверка условий с джампами

В смысле...? Джампы будут и в обычной проверке условий, не могу представить себе технической разницы для машины, кроме самой структуры кода. Тем более While, просто цикл и всё, не соблюдено условие-обход... с until ни одного лишнего джампа. Не зло, а систематизация.

@x128 · 13.07.2015, 18:21

Сообщение от Hretgir

В смысле...?

В контексте решения данной задачи.

Сообщение от Hretgir

Джампы будут и в обычной проверке условий

Нет! И я наглядно это продемонстрировал.

Сообщение от Hretgir

не могу представить себе технической разницы для машины

Проверка условия - это логическая операция, которая устанавливает флаги. Как обрабатывать флаги уже зависит от конкретной задачи, чаще это условный переход, но не всегда.
Пример:

Delphi
1
if a<0 then b:=1 else b:=0;

и

Delphi
1
b:=ord(a<0);

Смысл один, в обоих случаях мы присваиваем переменной 0 или 1 по результату проверки условия, но в первом случае будет переход (джамп), во втором нет.

Сообщение от Hretgir

с until ни одного лишнего джампа. Не зло, а систематизация.

Цикл и переход неразлучны и в данном контексте это зло - это как забивать гвозди микроскопом, можно, но не правильно.

@Shamil1 · 13.07.2015, 19:14

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

Именно по этой причине придумывались алгоритмы для вычисления функций типа signum, max, abs и т.п. без условных переходов.

@Igor3D · 14.07.2015, 11:00

Сообщение от Shamil1

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

Не процессор а компилятор - он не знает какую ветку поставить вперед. Это решается указаниями likely/unlikely, напр

C++
1
if (likely(a != 0)) ..

Но эффект такой оптимизации достаточно скромен. Т.е. да, при выполнении перехода кеш считанных команд будет утерян и потребуется какое-то доп время, но это не имеет фатальных/ужасных последствий.

@Hrethgir · 14.07.2015, 15:00 **[ТС]**

Да, в общем, компилятор разрабатывали не нубы. Я всё равно программировать буду через циклы, массивы процедур, ну и Sign. Что могу сказать, пусть будет такая проверка условий, но, написание кода в такой манере будет вести меня к накоплению опыта и к систематизации. Условности я откидываю из учёта. Если я хочу создать свою систему и базу знаний (накопление опыта )быстро - я не должен брать в расчёт то, что является условным, так я эффективно достигну цели, а всё что условно - пыль. Пусть в Sign происходит проверка условий, но я не должен брать это в расчёт, пусть будут джампы, но это явление не физическое а архитектурное - значит я не должен это брать в расчёт.
В первую очередь - придерживаться физики, логика - это фаза физических процессов, и работает она, как ни крути, в рамках законов физики, а в законах физики никто ничего не проверяет. Да пусть будет цикл, но это не та проверка условий, пусть проверка условий - но не та система, как у человека.

@Shamil1 · 14.07.2015, 15:03

Сообщение от Igor3D

при выполнении перехода кеш считанных команд будет утерян и потребуется какое-то доп время, но это не имеет фатальных/ужасных последствий

Конечно, ничего фатального.

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

Сообщение от Igor3D

Не процессор а компилятор

Процессор.

"Древние" процессоры использовали самый примитивный алгоритм предсказания: предполагали, что условный переход никогда не выполнится. Именно поэтому указания likely/unlikely имели эффект.
Современные процессоры используют динамические (времени исполнения) алгоритмы предсказания.

Сообщение от https://ru.wikipedia.org/wiki/Предсказатель_переходов

Модуль предсказания переходов (прогнозирования ветвлений) (англ. branch prediction unit) — устройство, входящее в состав микропроцессоров, имеющих конвейерную архитектуру, предсказывающее, будет ли выполнен условный переход в исполняемой программе. Предсказание ветвлений позволяет сократить время простоя конвейера, за счёт предварительной загрузки и исполнения инструкций, которые должны выполниться после выполнения инструкции условного перехода. Прогнозирование ветвлений играет критическую роль, так как в большинстве случаев (точность предсказания переходов в современных процессорах превышает 90%) позволяет оптимально использовать вычислительные ресурсы процессора[1].

https://ru.wikipedia.org/wiki/... _переходов

@Igor3D · 15.07.2015, 08:33

Сообщение от Shamil1

"Древние" процессоры использовали самый примитивный алгоритм предсказания: предполагали, что условный переход никогда не выполнится. Именно поэтому указания likely/unlikely имели эффект.

Использую интеловские open-source которые "древними" никак не назовешь - там likely/unlikely везде. Хотя возможно это всего лишь стиль авторов. А вообще вещи такого плана (напр эффект inline, вызова виртуальных методов и.т.п.) давно "канули в лету". Это крохи. Практически если оптимизация не сулит хотя бы "в полтора раза" - нет смысла с ней связываться, она не окупает усложнение кода. А упорное обсуждение таких вещей (под флагом вики

) есть просто желание сачкануть и увильнуть от реальной работы - не более того

@Hrethgir · 15.07.2015, 15:11 **[ТС]**

Не знаю, кажется на первый взгляд быстро, если:
псевдокод

Pascal
1
2
3
4
5
6
7
проверка: если x равно нулю то оборвать с предписаной операцией
начало:
проверка (предписание:  оборвать);
x:=x-x;
проверка (предписание: x:=1, оборвать);
x=-1;
конец

Ну данная конструкция может пригодится ещё часто, вроде так ничего, главное система отслеживается.
Что скажут критики?

Новые блоги и статьи Все статьи Все блоги /
Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .

@Hrethgir Заблокирован

	Нужна функция Sign без проверки условий 09.07.2015, 15:11. Показов 4527. Ответов 40 Метки нет (Все метки) Я пока не нашёл способа, но ищу. 0

@Hrethgir Заблокирован
	12.07.2015, 16:42 [ТС]
	проверять на 0 надо, потому что на 0 делить нельзя, а математика правил математики не знает. возвращаясь к выражению, нужно в первую очередь определить x на линейке, для чего производится операция x+1 и в дальнейшем нужно привести всё это к следующему виду x=(x+1)/x, если результат больше входящих данных, то x положительный, если результат меньше входящих данных, то x отрицательный. но, похоже, это ёмко очень для компьютера. по крайней мере, ёмче обычных сравнений, пусть даже через while 0

@x128 240 / 218 / 46 Регистрация: 17.04.2010 Сообщений: 526
	12.07.2015, 20:11
	castorsky, не собирался обидеть, просто ответ выглядит как "всё просто, а вы залезли в дебри", вероятно это я торможу... 0

@Shamil1 Модератор 3140 / 2288 / 469 Регистрация: 26.03.2015 Сообщений: 8,900
	13.07.2015, 19:14
	Условный переход принципиально отличается от логической операции. Условный переход означает ветвление "потока" исполнения кода. Процессор не может точно знать заранее, какую ветку кода нужно загрузить, а может только строить догадки. И если он ошибётся и загрузит не ту ветку, то "потеряет" несколько десятков тактов (будет простаивать, пока загружается нужная ветка). Именно по этой причине придумывались алгоритмы для вычисления функций типа signum, max, abs и т.п. без условных переходов. 0

@Hrethgir Заблокирован
	14.07.2015, 15:00 [ТС]
	Да, в общем, компилятор разрабатывали не нубы. Я всё равно программировать буду через циклы, массивы процедур, ну и Sign. Что могу сказать, пусть будет такая проверка условий, но, написание кода в такой манере будет вести меня к накоплению опыта и к систематизации. Условности я откидываю из учёта. Если я хочу создать свою систему и базу знаний (накопление опыта )быстро - я не должен брать в расчёт то, что является условным, так я эффективно достигну цели, а всё что условно - пыль. Пусть в Sign происходит проверка условий, но я не должен брать это в расчёт, пусть будут джампы, но это явление не физическое а архитектурное - значит я не должен это брать в расчёт. В первую очередь - придерживаться физики, логика - это фаза физических процессов, и работает она, как ни крути, в рамках законов физики, а в законах физики никто ничего не проверяет. Да пусть будет цикл, но это не та проверка условий, пусть проверка условий - но не та система, как у человека. 0

Нужна функция Sign без проверки условий

Решение