Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4   вперед  Ctrl      все
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
SashaMercury
XDiaBLo
пропущено...

Да там и if есть самый настоящий. Но по сабжу я уже ответил
Программа:(max 5 3)
Результат: 5


а вы посмотрите как в Scheme реализована эта функция :)

Хмм, исходники компилятора чтоль поискать? Там это похоже ключевое слово, даже не из библиотек, а основы языка.
21 ноя 14, 08:09    [16882715]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Dima T
SashaMercury
а чем это лучше предложенного кода ранее
пропущено...

Тем что я его не заметил выше :)

Только правильно так
int sign(int x)
{
    return (x>>31) | 1;
}


почему так ? ведь у меня после сдвига в младшем разряде будет либо 1, либо 0
21 ноя 14, 08:20    [16882739]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
SashaMercury
    return x>>31;

Ну и битовые сдвиги не перечислены в разрешенных операциях
andreymx
+ - * / and or xor
21 ноя 14, 08:22    [16882745]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
Dima T
SashaMercury
    return x>>31;


Ну и битовые сдвиги не перечислены в разрешенных операциях
andreymx
+ - * / and or xor

А это же не циклический сдвиг? Деление нацело сойдёт тогда.
21 ноя 14, 08:26    [16882757]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
SashaMercury
почему так ? ведь у меня после сдвига в младшем разряде будет либо 1, либо 0

обычно принято что sign() возвращает +1 для положительных, -1 для отрицательных и 0 для 0.
В данном случае 0 не важен, т.к. нам в итоге надо получить модуль числа, т.е.
abs(x) = x * sign(x)
21 ноя 14, 08:26    [16882759]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
XDiaBLo
Dima T
пропущено...

Ну и битовые сдвиги не перечислены в разрешенных операциях
пропущено...

А это же не циклический сдвиг? Деление нацело сойдёт тогда.

А мля, 31 а не 32...
21 ноя 14, 08:26    [16882761]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
XDiaBLo
XDiaBLo
пропущено...

А это же не циклический сдвиг? Деление нацело сойдёт тогда.

А мля, 31 а не 32...
Впрочем 2 в 31 степени же.
21 ноя 14, 08:26    [16882764]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
XDiaBLo
А это же не циклический сдвиг? Деление нацело сойдёт тогда.

Это оказывается сдвиг с учетом знака
http://msdn.microsoft.com/ru-ru/library/vstudio/k2ay192e(v=vs.100).aspx
Для заполнения позиций слева используется бит знака значения

Я не знал, если честно.
21 ноя 14, 08:35    [16882791]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Dima T, тогда надо будет результат побитово умножить на 1. Но если уж уходить от побитового сдвига, то нужно использовать ваш вариант
21 ноя 14, 08:40    [16882818]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
Dima T
XDiaBLo
А это же не циклический сдвиг? Деление нацело сойдёт тогда.

Это оказывается сдвиг с учетом знака
http://msdn.microsoft.com/ru-ru/library/vstudio/k2ay192e(v=vs.100).aspx
Для заполнения позиций слева используется бит знака значения

Я не знал, если честно.

Ясно, деление нацело не сойдёт.
21 ноя 14, 08:52    [16882855]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
SashaMercury
Dima T, тогда надо будет результат побитово умножить на 1.

не поможет т.к. 0&1 = 0.
Твой сдвиг дает либо 0000 либо 1111, т.е. для положительных надо дополнительно 0000 превратить в 0001, что и делает |1
21 ноя 14, 08:55    [16882861]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Dima T
SashaMercury
Dima T, тогда надо будет результат побитово умножить на 1.

не поможет т.к. 0&1 = 0.
Твой сдвиг дает либо 0000 либо 1111, т.е. для положительных надо дополнительно 0000 превратить в 0001, что и делает |1


нет, мне это не нужно. Для положительных я буду иметь 0, для отрицательных 1. И дальше такой код
int t=sign(a-b);
int res=b*t+a(1-t);
21 ноя 14, 09:04    [16882901]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Коллеги а какова цена вопроса? Что мы хотим?

1) Оптимизировать скорость?

В этом случае нам надо искать Ассемблер для целевой конфигурации и внимательно
смотреть в нём команды, abs(x,y), sgn(x,y) или их более атомарные декомпозиции.
Далее считать такты и делать бенчмарки.

2) Перейти в другой базис?

Актуально для цифровой системотехники. Искать программно-аппаратное решение.
Можно рисовать логическую машину на вентилях AND/OR/NOT и линиях задержки.
Но это-ли спрашивал автор?

3) Перейти в другой ЯП?

Ну тут вроде примеры уже были. Большая часть - самообман. Трудно доказать
ОТСУТСТВИЕ операции IF внтри них.

4) Делать обфускацию и запутывать читателя?

Нечего добавить. Можно сколь угодно усложнять функцию abs вычисляя ее через
числовые ряды и умножения векторов и матриц. Усложнять вообще может
любой дурак.

Вы попробуйте упростить. Вобщем Генри Уоррен тычет вам свою книжку
и тихо ругается сквозь зубы.
21 ноя 14, 09:27    [16883000]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
mayton
Что мы хотим?

Фигней позаниматься

Иногда полезно, я вот например узнал что >> для заполнения позиций слева использует бит знака значения.
21 ноя 14, 09:38    [16883063]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
(define (mymax a b)
  (/ (+ a b
        (abs (- a b))
     ) 2
  )
)
(mymax 5 8)

Осталось придумать как abs без использования if сделать.
21 ноя 14, 09:40    [16883078]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
XDiaBLo
Осталось придумать как abs без использования if сделать.

так уже придумано
Яростный Меч
(a + b + abs(a-b)) / 2

Dima T
abs(x) = x * sign(x)

Dima T & SashaMercury
int sign(int x)
{
return (x>>31) | 1;
}
21 ноя 14, 09:47    [16883140]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
Dima T
XDiaBLo
Осталось придумать как abs без использования if сделать.

так уже придумано
Яростный Меч
(a + b + abs(a-b)) / 2

Dima T
abs(x) = x * sign(x)

Dima T & SashaMercury
int sign(int x)
{
return (x>>31) | 1;
}

Да, только я пока Scheme не так хорошо знаю, чтобы это реализовать.
21 ноя 14, 09:50    [16883158]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
Ладно, сделал :)
(define (myabs x)
  (* x (sgn x))
)
(define (mymax a b)
  (/ (+ a b
        (myabs (- a b))
     ) 2
  )
)
(max 9 -18)
(max 1 3)
(max 8 115)
21 ноя 14, 09:56    [16883212]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
XDiaBLo
Ладно, сделал :)
(define (myabs x)
  (* x (sgn x))
)
(define (mymax a b)
  (/ (+ a b
        (myabs (- a b))
     ) 2
  )
)
(mymax 9 -18)
(mymax 1 3)
(mymax 8 115)

Поправил. Результат таков
автор
9
3
115
21 ноя 14, 09:57    [16883219]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
XDiaBLo
Да, только я пока Scheme не так хорошо знаю, чтобы это реализовать.

могу только подсказать как по правильному операции называются
>> "битовый арифметический сдвиг вправо"
| "побитовое сложение" или "логическое или"

может поможет нагуглить нужное
21 ноя 14, 09:59    [16883242]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
Короче вот конечная версия:
#lang racket
(define (mysign x)
  (bitwise-ior 1 (arithmetic-shift x -31))
)
(define (myabs x)
  (* x (mysign x))
)
(define (mymax a b)
  (/ (+ a b
        (myabs (- a b))
     ) 2
  )
)
(mymax 9 -18)
(mymax 1 3)
(mymax 8 115)
21 ноя 14, 10:07    [16883278]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
Просто я взялся дочитать однажды заброшенный мной SICP, поэтому стараюсь при любой возможности практиковаться. Этим и обусловлен выбор языка.
21 ноя 14, 10:10    [16883299]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
XDiaBLo
Просто я взялся дочитать однажды заброшенный мной SICP, поэтому стараюсь при любой возможности практиковаться. Этим и обусловлен выбор языка.

+1
Это мега-похвально.

А что такое "racket" ? Я использовал Common Lisp.
21 ноя 14, 12:02    [16884205]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
mayton
XDiaBLo
Просто я взялся дочитать однажды заброшенный мной SICP, поэтому стараюсь при любой возможности практиковаться. Этим и обусловлен выбор языка.

+1
Это мега-похвально.

А что такое "racket" ? Я использовал Common Lisp.

В среде DrRacket по умолчанию используется язык Racket, который хоть и отличается от Scheme, но пока всё компилится, я часто забываю указать "#lang scheme" вместо "#lang racket". В общем он похож на Scheme очень, пока ещё я не наткнулся на различия.

И кстати в книге же Scheme используется а не Common Lisp, я предпочёл использовать то что авторы сказали, правда не осилил компиляцию в mit-scheme, поэтому взял DrRacket, который тоже Scheme поддерживает. В нём вполне удобно.
21 ноя 14, 12:11    [16884315]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Всегда удивляло это многообразие (defun ..) (def ..) (define ..).

Кстати Common-Lisp запретил переопределять max, поэтому я сделал maximum.
21 ноя 14, 14:15    [16885350]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4   вперед  Ctrl      все
Все форумы / Программирование Ответить