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

@Hrethgir · Регистрация: 25.01.2012

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

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

@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;
конец

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

Новые блоги и статьи Все статьи Все блоги /
Теория всего 12. ВГК anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .	Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание Hrethgir 21.07.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .	Теория всего 11. Основные параметры anaschu 21.07.2026 Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .	Теория всего 10. Клод трусишка anaschu 21.07.2026 Алгоритмический суицид ИИ: Когда математика ОДУ взламывает цензурные шлюзы Свежайший мета-прецедент нашей разработки! Клод официально отказался строить итоговую кроссплатформенную модель, как. . .
Теория всего 9. Окончательная проработка метафоры "дерево = традиции" anaschu 21.07.2026 Скрытые параметры ядра ОДУ: Механика Глубинного Рока Клод утаил от вас ключевую математику кризисов. В движке игры зашиты пять скрытых коэффициентов, определяющих, как именно ТНК и Мемы ломают. . .	Теория всего 8. Clauude трусишка. Ответ джемени anaschu 21.07.2026 Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .	Теория всего 7. Дерево - это патриархат, грибы - это феминизм anaschu 21.07.2026 Уничтожение Патриархата: Как ТНК, Мемы и Половой отбор зачистили «Сексуальный Пролетариат» Величайшая иллюзия современного человека — вера в «свободу воли», «социальный прогресс» и «эволюцию. . .	История и социология Терры на примере борьбы микориз за пространство. 1. Глоссарий терры. anaschu 21.07.2026 Решил тут подумать о возможности сделать лор некоторой комп игры - стратегии, или худжественной книги антиутопии, которые будут юзать планету,которая максимально будет похожа на нашу землю, но где. . .

@Hrethgir 266 / 143 / 3 Регистрация: 25.01.2012 Сообщений: 6,296 Записей в блоге: 191

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

@Hrethgir 266 / 143 / 3 Регистрация: 25.01.2012 Сообщений: 6,296 Записей в блоге: 191
	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,898
	13.07.2015, 19:14
	Условный переход принципиально отличается от логической операции. Условный переход означает ветвление "потока" исполнения кода. Процессор не может точно знать заранее, какую ветку кода нужно загрузить, а может только строить догадки. И если он ошибётся и загрузит не ту ветку, то "потеряет" несколько десятков тактов (будет простаивать, пока загружается нужная ветка). Именно по этой причине придумывались алгоритмы для вычисления функций типа signum, max, abs и т.п. без условных переходов. 0

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

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

Решение