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

Откуда: Запорожье
Сообщений: 51828
напомните, есть ли алгоритм вычисления максимума из двух чисел без if
20 ноя 14, 20:07    [16881432]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
andreymx
Member

Откуда: Запорожье
Сообщений: 51828
+ - * / and or xor
20 ноя 14, 20:11    [16881456]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
miksoft
Member

Откуда:
Сообщений: 37557
Придумать-то можно, но зачем?

Псевдокод:
int max(int a, int b)
(
  t[0]=a;
  t[1]=b;
  return a[sign(sign(b-a)+1)];
}
sign можно реализовать без if, например, сдвигами и бинарными операциями.
20 ноя 14, 20:39    [16881560]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
miksoft
Member

Откуда:
Сообщений: 37557
Поправка:
int max(int a, int b)
(
  t[0]=a;
  t[1]=b;
  return t[sign(sign(b-a)+1)];
}
20 ноя 14, 20:40    [16881567]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
White Owl
Member

Откуда:
Сообщений: 12384
c = a<b ? b : a;

c = max(a,b);

c=0;
while(a>0 && b>0) {
    c++;
    a--;
    b--;
}


Ну а если Си не любишь, то можно и на SQL сделать.
select @c = case when @a<@b then @b else @a end

select @c = max(v) from (select v=a union select b) t
20 ноя 14, 20:41    [16881569]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
miksoft
Member

Откуда:
Сообщений: 37557
White Owl
case when
Да, это не if, там и буковок-то таких нету!
20 ноя 14, 20:43    [16881579]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
no56892
Member

Откуда:
Сообщений: 588
andreymx
напомните, есть ли алгоритм вычисления максимума из двух чисел без if

А на брейнфаке генератор случайных чисел слабо?
20 ноя 14, 21:59    [16881960]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
MaytonsFuckenMaximumFunction.lisp
(defun maximum(x y) 
  (cond ((= x y) x) ((> x y) x) ((< x y) y)))
20 ноя 14, 22:26    [16882034]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Яростный Меч
Member [скрыт]

Откуда:
Сообщений: 28868
(a + b + abs(a-b)) / 2
21 ноя 14, 00:46    [16882400]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
На самом деле все предложенные алгоритмы содержат неявный if. Если вы видите знак больше или меньше, то мы уже говорим о каком-либо условии. Казалось бы вариант предложенный Яростным мечом подходит, но и это не так. Ибо вычисление модуля подразумевает условие, кроме того, модуль не был в числе допустимых операций

andreymx
+ - * / and or xor


потому, ответа на поставленный вопрос никто пока не дал.
21 ноя 14, 02:51    [16882533]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Можно было сделать так:

int t=a%b;

если а больше b то t>=1, в противном случае 0. Нужно установить t в 1, в том случае, если t>1. Это можно сделать следующим образом
t=(t+2)%(t+1);

если t было равно 0, то получим 2, если больше нуля, то получим число вида , это число не является целым, потому следующей операцией будет следующая
t=t%2;

Если t было равно 2, то мы получим 0, в противном случае, мы получим остаток 1. Таким образом, если a>b, то t=1, в противном случае, 0. Выражение вида
int max=t*(a-b)+(1-t)(b-a);

даст вам то, что требуется.

PS
скорее всего, в реализации операции % тем или иным образом присутствует условие, но в данном случае, оно менее явное чем в остальных случаях. И тут я так-же не использовал только те операции что вы предлагали. Код не тестировал, проверьте сами
21 ноя 14, 03:14    [16882543]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
miksoft
Придумать-то можно, но зачем?

Псевдокод:
int max(int a, int b)
(
  t[0]=a;
  t[1]=b;
  return a[sign(sign(b-a)+1)];
}
sign можно реализовать без if, например, сдвигами и бинарными операциями.


тогда уже
 a*sign[a-b]+b*(1-sign[a-b]);

так читабельней. Может и можно реализовать, не помню. Надеюсь автор доведёт дело до конца, и напомнит как это сделать.
Хотя тут и думать не нужно, это элементарно, вот так:
int sign(int x)
{
    return x>>31;
}

данная функция вернёт 1 если число отрицательно и 0 в противном случае, таким образом, получим следующий результирующий код
int a,b;
int max=sign(a-b)*b+(1-sign(a-b))*a;


В общем мысль и идея понятны, тестируйте, не проверял этот код.

PS
но опять таки, в данном коде присутствуют лишние операции
21 ноя 14, 03:26    [16882556]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
SashaMercury
На самом деле все предложенные алгоритмы содержат неявный if. Если вы видите знак больше или меньше, то мы уже говорим о каком-либо условии. Казалось бы вариант предложенный Яростным мечом подходит, но и это не так. Ибо вычисление модуля подразумевает условие, кроме того, модуль не был в числе допустимых операций

abs() можно реализовать так sqrt(x*x)
21 ноя 14, 07:11    [16882649]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Dima T,

покажите как вы реализуете корень :)
21 ноя 14, 07:13    [16882651]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
Второй вариант получить множитель 1 для положительного, -1 для отрицательного, т.е. sign()
в двоичном представлении 00000001 и 11111111 соответственно, старший бит это знак для типов со знаком.
далее
int my_sign(int x)
{
	unsigned int u = x & 0x80000000; // берем старший бит исходного числа
	for(int i = 0; i < 31; i++) { // заполняем им все биты
		u |= (u >> 1);
	}
	return u | 1; // устанавливаем младший бит в 1 для положительных
}
21 ноя 14, 07:39    [16882665]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
i < 31


явный if
21 ноя 14, 07:48    [16882679]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

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

покажите как вы реализуете корень :)

Корень можно вычислить как-то так:
#lang racket
(define (average x y)
  (/ (+ x y) 2))
(define tolerance 0.00000001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
(try first-guess))
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

(sqrt 1024)

32.0
>
21 ноя 14, 07:49    [16882682]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
SashaMercury
i < 31


явный if

а так?
int my_sign(int x)
{
	unsigned int u = x & 0x80000000; // берем старший бит исходного числа
	// заполняем им все биты
	u |= (u / 2);
	u |= (u / 2);
	... и еще 29 раз повторить эту строчку
	return u | 1; // устанавливаем младший бит в 1 для положительных
}

21 ноя 14, 07:50    [16882683]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
andreymx
напомните, есть ли алгоритм вычисления максимума из двух чисел без if

А вообще, по идее на scheme просто
(max 3 5)
5
>
21 ноя 14, 07:54    [16882685]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
XDiaBLo
SashaMercury
Dima T,

покажите как вы реализуете корень :)

Корень можно вычислить как-то так:
#lang racket
(define (average x y)
  (/ (+ x y) 2))
(define tolerance 0.00000001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
(try first-guess))
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

(sqrt 1024)

32.0
>


вы используете тернарный оператор, значит используете if
21 ноя 14, 07:55    [16882688]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
Dima T
	u |= (u / 2);
	u |= (u / 2);
	... и еще 29 раз повторить эту строчку


Кстати можно обойтись 8-ю строчками
21 ноя 14, 07:55    [16882689]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
SashaMercury
вы используете тернарный оператор, значит используете if

Да там и if есть самый настоящий. Но по сабжу я уже ответил
Программа:(max 5 3)
Результат: 5
21 ноя 14, 07:56    [16882690]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Dima T
Dima T
	u |= (u / 2);
	u |= (u / 2);
	... и еще 29 раз повторить эту строчку


Кстати можно обойтись 8-ю строчками




а чем это лучше предложенного кода ранее
SS
int sign(int x)
{
    return x>>31;
}
21 ноя 14, 07:58    [16882693]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
XDiaBLo
SashaMercury
вы используете тернарный оператор, значит используете if

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


а вы посмотрите как в Scheme реализована эта функция :)
21 ноя 14, 08:02    [16882700]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
SashaMercury
а чем это лучше предложенного кода ранее
SS
int sign(int x)
{
    return x>>31;
}

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

Только правильно так
int sign(int x)
{
    return (x>>31) | 1;
}
21 ноя 14, 08:05    [16882707]     Ответить | Цитировать Сообщить модератору
 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]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

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

Кстати Common-Lisp запретил переопределять max, поэтому я сделал maximum.

Не, ну в Scheme переопределить ничто не мешает похоже, но для уверенности я my везде добавил в название.
21 ноя 14, 14:17    [16885378]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Кстати... Scheme написан на Scheme?
21 ноя 14, 14:19    [16885396]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
mayton
Кстати... Scheme написан на Scheme?

Никогда этого не понимал, как можно что то написать на нём же самом? Ядро ведь всё равно на чём то другом будет?
21 ноя 14, 14:23    [16885435]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
XDiaBLo
mayton
Кстати... Scheme написан на Scheme?

Никогда этого не понимал, как можно что то написать на нём же самом? Ядро ведь всё равно на чём то другом будет?

Думаю да. Самый самый первый "C" скорее всего был написан на Асм-ах.
Иначе причинно следственная цепочка была-бы похерена и на земле воцарился-бы Сотона.
А так... Кернинган и Ричи..

Другое дело што Лиспы вроде-как умеют exe-шник готовить.
21 ноя 14, 14:32    [16885522]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

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

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

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

Условие задачи "без if" - это (как и всякие размотки циклов) оптимизация переходов путем сокращения количества этих самых переходов.
Довольно существенно может поднять скорость. Да и снизить тоже :)
21 ноя 14, 19:05    [16887451]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6359
Правда для Лиспа вообще бесполезна :)
21 ноя 14, 19:06    [16887453]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
mayton
XDiaBLo
Никогда этого не понимал, как можно что то написать на нём же самом? Ядро ведь всё равно на чём то другом будет?

Думаю да. Самый самый первый "C" скорее всего был написан на Асм-ах.

Компилятор асма тоже был на чем-то написан. Просто тогда уровень сложности был такой что можно было код написать в тетрадке, там же перевести в байт-код и потом забить в комп и запустить. Я с этого начинал. Компилировал ручкой на бумаге.
21 ноя 14, 19:17    [16887484]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
У ассемблера нет компилятора.
Есть символьные ассемблеры, позволяющие использовать более-менее человеко-читабельные мнемоники вместо кодов.
21 ноя 14, 19:29    [16887524]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Изопропил
Member

Откуда:
Сообщений: 31163
mayton
Думаю да. Самый самый первый "C" скорее всего был написан на Асм-ах.

на подмножестве С
http://habrahabr.ru/post/180523/
21 ноя 14, 19:37    [16887550]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Dima T
Member

Откуда:
Сообщений: 13717
Basil A. Sidorov
У ассемблера нет компилятора.
Есть символьные ассемблеры, позволяющие использовать более-менее человеко-читабельные мнемоники вместо кодов.

ИМХУ: Компилировение это не что иное как преобразование человеко-читабельного в машинно-исполняемое
21 ноя 14, 20:14    [16887680]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
White Owl
Member

Откуда:
Сообщений: 12384
Basil A. Sidorov
У ассемблера нет компилятора.
Есть символьные ассемблеры, позволяющие использовать более-менее человеко-читабельные мнемоники вместо кодов.
Ошибаешься. У ассемблера компиляторы есть. Собственно говоря, без компилятора ассемблер не возможен.
Ассемблер это и есть набор мнемоник превращающий кода в человеко-читабельный текст.
21 ноя 14, 23:23    [16888327]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Изопропил
Member

Откуда:
Сообщений: 31163
White Owl
Ошибаешься. У ассемблера компиляторы есть.

Не согласен

Возможно, формулировки зависят от учебного заведения.
21 ноя 14, 23:28    [16888342]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
White Owl
Member

Откуда:
Сообщений: 12384
Изопропил
White Owl
Ошибаешься. У ассемблера компиляторы есть.

Не согласен

Возможно, формулировки зависят от учебного заведения.
При чем здесь учебное заведение?
Чисто из определения ассемблера:
https://ru.wikipedia.org/wiki/Язык_ассемблера
Язык ассемблера (англ. assembly language) — машинно-ориентированный язык низкого уровня с командами, обычно соответствующими командам машины, который может обеспечить дополнительные возможности вроде макрокоманд; автокод, расширенный конструкциями языков программирования высокого уровня, такими как выражения, макрокоманды, средства обеспечения модульности программ.

Может вас смущает то что "ассемблером" называют и программу которая переводит из мнемоники в машинные кода? Но эта программа по существу и есть компилятор.

В принципе можно и вручную сделать перевод из мнемоники в кода (по существу делая ручную компиляцию). Но процесс компиляции есть всегда. Правда в этом случае компилятором будет служить человек с карандашом.
21 ноя 14, 23:59    [16888460]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Изопропил
Member

Откуда:
Сообщений: 31163
White Owl
Но эта программа по существу и есть компилятор.

я привык называть эту программу ассемблером и не называю компилятором.
Так учили.
22 ноя 14, 00:04    [16888480]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
White Owl
Member

Откуда:
Сообщений: 12384
Изопропил
White Owl
Но эта программа по существу и есть компилятор.

я привык называть эту программу ассемблером и не называю компилятором.
Так учили.
Ааа... ну да, ну да... Курица не птица, ЗАЗ 965 не автомобиль, и разные другие "не" из этой же серии :)
22 ноя 14, 00:38    [16888594]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6359
Ассемблер - частный случай компилятора, т.к. производит трансляцию из более высокоуровневого текстового представления кода в низкоуровневый бинарный, пригодный для запуска либо скармливания линкеру, что полностью соответствует определению компилятора.
22 ноя 14, 03:44    [16888885]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
Anatoly Moskovsky
Ассемблер - частный случай компилятора, т.к. производит трансляцию из более высокоуровневого текстового представления кода в низкоуровневый бинарный, пригодный для запуска либо скармливания линкеру, что полностью соответствует определению компилятора.

Как его ни назови, суть останется та же самая. У вас просто спор про определения, что в принципе обычное дело. Часто читаешь книжку по какой то теме, и там несколько разных определений одного и того же. Сколько людей, столько мнений.
22 ноя 14, 09:14    [16889011]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
White Owl
Собственно говоря, без компилятора ассемблер не возможен.
debug древнего DOS содержал ассемблер.
Никаких компиляторов - достаточно прямолинейное превращение мнемоник в последовательность байт.
Ну и стандартная для (этой) программы возможность сброса участка памяти на диск, что давало com-файл.

P.S. Видел пример изощрённого bat-файла, где debug использовался, чтобы вывести строку без завершающего CRLF
22 ноя 14, 09:39    [16889040]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
Basil A. Sidorov
White Owl
Собственно говоря, без компилятора ассемблер не возможен.
debug древнего DOS содержал ассемблер.
Никаких компиляторов - достаточно прямолинейное превращение мнемоник в последовательность байт.
Ну и стандартная для (этой) программы возможность сброса участка памяти на диск, что давало com-файл.

P.S. Видел пример изощрённого bat-файла, где debug использовался, чтобы вывести строку без завершающего CRLF

У меня однажды давно Винда 98 не ставилась, из-за скандиска, он на что-то ругался. Удаление скандиска не помогало. Так я сделал исполняемый файл с одной командой "ret", и заменил им скандиск. Винда поставилась, и всё было нормально :) Дебаг тот я использовал чтобы вспомнить как будет "ret" в 16-ричном коде.
22 ноя 14, 09:42    [16889043]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9184
Насколько мне изменяет склероз, у виндового установщика был штатный ключ, пропускающий фазу проверки диска.
22 ноя 14, 09:46    [16889047]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
Basil A. Sidorov
Насколько мне изменяет склероз, у виндового установщика был штатный ключ, пропускающий фазу проверки диска.

:) Может быть. Я наверное не в курсе про него был.
22 ноя 14, 09:48    [16889048]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
Мне вот другое интересно. Я провёл многие часы дни и анализируя и упрощая предикаты в if.
Метод карт Карно или диаграм Вейча. Мне нравилось сворачивать сложные проверки или
оптимизировать скорость просто меняя их порядок в expression.
22 ноя 14, 10:45    [16889106]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
XDiaBLo
Member

Откуда: Екатеринбург
Сообщений: 71568
mayton
Мне вот другое интересно. Я провёл многие часы дни и анализируя и упрощая предикаты в if.
Метод карт Карно или диаграм Вейча. Мне нравилось сворачивать сложные проверки или
оптимизировать скорость просто меняя их порядок в expression.

А мне раньше нравилось на ассемблере писать, ну это интересно конечно, но обычно для работы недостаточно быстро код пишется. Потому как перестал быть студентом, ассемблер забросил :(
22 ноя 14, 10:54    [16889117]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 57518
Блог
XDiaBLo
Никогда этого не понимал, как можно что то написать на нём же самом? Ядро ведь всё равно на чём то другом будет?

Нет, не обязательно. Первую версию надо писать на чём-то другом. А вторую версию уже можно написать на первой.
22 ноя 14, 16:26    [16890030]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Вася Уткин
Guest
White Owl
c = a<b ? b : a;

c = max(a,b);

c=0;
while(a>0 && b>0) {
    c++;
    a--;
    b--;
}


Ну а если Си не любишь, то можно и на SQL сделать.
select @c = case when @a<@b then @b else @a end

select @c = max(v) from (select v=a union select b) t

Все 3 варианта хоть и без if, но скомпилируются с условным переходом.

Если нужен без jump-ов, но c cmp, то такой вариант:
http://ideone.com/aQW2D6
#include <iostream>
using namespace std;

inline int func(int a, int b) {
	int ab[2] = {a, b};
	return ab[a<b];
}


int main() {
	
	cout << func(5, 4);
	
	// your code goes here
	return 0;
}
22 ноя 14, 22:39    [16890922]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34452
andreymx
напомните, есть ли алгоритм вычисления максимума из двух чисел без if


вычислить разность двух чисел и поверить знак результата.
23 ноя 14, 09:51    [16891559]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6359
Вася Уткин,

Походу нашелся победитель с правильным решением :)
23 ноя 14, 12:54    [16891799]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Вася Уткин
Guest
Anatoly Moskovsky
Вася Уткин,

Походу нашелся победитель с правильным решением :)

Я только не на 100% уверен, всегда ли по стандарту в C/C++ выражение a<b обязано быть равно 0 или 1, или может принимать и другие значения?
23 ноя 14, 13:32    [16891834]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 57518
Блог
White Owl
Может вас смущает то что "ассемблером" называют и программу которая переводит из мнемоники в машинные кода? Но эта программа по существу и есть компилятор.

Нет, эта программа по существу не есть компилятор. Она есть по существу транслятор. Надеюсь, разницу объяснять не надо.
23 ноя 14, 13:39    [16891838]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6359
Вася Уткин
Я только не на 100% уверен, всегда ли по стандарту в C/C++ выражение a<b обязано быть равно 0 или 1, или может принимать и другие значения?

Да, обязано.

"a<b" имеет тип bool в С++ и _Bool в С
bool в С++ это нечисловой тип, который при приведении к числовому (в данном случае для индексации массива) принимает значения 0 или 1.
_Bool в С - это числовой тип который принимает значения 0 или 1.
23 ноя 14, 13:53    [16891866]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Вася Уткин
Guest
Anatoly Moskovsky
Вася Уткин
Я только не на 100% уверен, всегда ли по стандарту в C/C++ выражение a<b обязано быть равно 0 или 1, или может принимать и другие значения?

Да, обязано.

"a<b" имеет тип bool в С++ и _Bool в С
bool в С++ это нечисловой тип, который при приведении к числовому (в данном случае для индексации массива) принимает значения 0 или 1.
_Bool в С - это числовой тип который принимает значения 0 или 1.

Значит я угадал :)
Но обращение к кэшу L1 все равно будет дольше, чем переходы jg/jl, так что с практической точки зрения это мало имеет смысла. В обоих случаях в конвейере не получится внеочередное выполнение команд завязанных на результат такого сравнения - только в случае с массивом потеряем ещё несколько тактов на обмен с L1.

А других вариантов решения не знаете случайно?
23 ноя 14, 14:15    [16891923]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1742
Вася Уткин,

ну, например, из той же серии: a + (b-a) and (ord(a>b) - 1)
23 ноя 14, 14:49    [16892004]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Вася Уткин
Guest
Aleksandr Sharahov
Вася Уткин,

ну, например, из той же серии: a + (b-a) and (ord(a>b) - 1)

А что такое ord? :)


Получается что-то типа:
http://ideone.com/1zCiYa
#include <iostream>
#include <cstdlib>
using namespace std;

inline constexpr int func(int a, int b) {
	return a + ((b-a) & ((unsigned)(a>b) - 1));
}
 

int main() {
	
	cout << func(5, 4);
	
	cout << endl << func(rand()%10, rand()%10);
	
	// your code goes here
	return 0;
}


Причем, 1-й раз в compile-time отработает, даже в C++11(не 14), а второй раз в run-time без jump-ов.
23 ноя 14, 17:59    [16892548]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6359
Вася Уткин,

Сорри, приз переходит к Aleksandr Sharahov :)
24 ноя 14, 00:38    [16893980]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Anatoly Moskovsky
Вася Уткин,

Походу нашелся победитель с правильным решением :)


нет, там есть сравнение, причём явное.

Anatoly Moskovsky

Сорри, приз переходит к Aleksandr Sharahov :)

а знак больше это не if разве ?


Правильно решение было у Дмитрия (Dima_T) и у меня. Только в этих двух решения не содержался явный if (и знаки больше меньше etc)
24 ноя 14, 01:48    [16894078]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6359
SashaMercury
а знак больше это не if разве ?

Нет конечно. Там же нет ветвления.
24 ноя 14, 06:49    [16894226]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6359
SashaMercury
нет, там есть сравнение, причём явное.

Правильно решение было у Дмитрия (Dima_T) и у меня. Только в этих двух решения не содержался явный if (и знаки больше меньше etc)

Поясню. Сравнение - это просто вычитание, а вовсе не if где требуется проверка на 0 и условный переход.
Таким образом в коде который предложил Aleksandr Sharahov есть операции "-", "+", "&".
А в вашем коде есть в разных его вариантах были операция * и даже % которые медленнее на порядки.

Если сравнивать алгоритмы по скорости выполнения (а других причин для такого идиотского условия задачи нет) то самый быстрый будет код от Aleksandr Sharahov.
24 ноя 14, 07:07    [16894230]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
SS
miksoft
Придумать-то можно, но зачем?

Псевдокод:
int max(int a, int b)
(
  t[0]=a;
  t[1]=b;
  return a[sign(sign(b-a)+1)];
}
sign можно реализовать без if, например, сдвигами и бинарными операциями.


тогда уже
 a*sign[a-b]+b*(1-sign[a-b]);

так читабельней.


Чем тогда плох этот пример(приводил его намного раньше) ? Выше псевдокод и использованием нотации Айверсона, присутствующей в Си/С++ по умолчанию, вот код на С++.
int max=a*(a>b)+b*(1-(a>b));
24 ноя 14, 07:16    [16894234]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Anatoly Moskovsky,

не знал что операция сравнения это разность.
Но тем не менее, позже был показан вариант включающий только & >> и +, без умножения и %
24 ноя 14, 07:24    [16894237]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6359
SashaMercury
Чем тогда плох этот пример

Я не говорю что он плох. Я говорю что есть лучше :)
24 ноя 14, 07:47    [16894255]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Anatoly Moskovsky,
кстати, в этом примере, умножение смело можно заменить на побитовое умножение &

int t=a>b;
nt max=a&t+b&(1-t);


мне эти ord непонятны, поверю вам, лучше так лучше :)
24 ноя 14, 07:58    [16894264]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6359
SashaMercury
мне эти ord непонятны, поверю вам, лучше так лучше :)

Не надо мне верить.
Я же не проверял экспериментом :)

А ord это просто приведение типа к числу.
24 ноя 14, 08:41    [16894335]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Barlone
Member

Откуда:
Сообщений: 1213
Развели тут длинное обсуждение, а при этом современный компилятор сгенерирует код для такого "if(a) b=c" без условных переходов, используя conditional move
24 ноя 14, 09:12    [16894416]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
mayton
Member

Откуда: loopback
Сообщений: 41068
SashaMercury
Anatoly Moskovsky,
кстати, в этом примере, умножение смело можно заменить на побитовое умножение &

int t=a>b;
nt max=a&t+b&(1-t);


мне эти ord непонятны, поверю вам, лучше так лучше :)

Это из Паскалей. ИМХО.

Автор некисло вбросил навоза на реактивную турбину. Он в сабже не указал язык
программирования. Перечислил какой-то сомнительный список операций (или функций)
или макросов типа and or xor.

Вот мы и крутимся то в ассемблер то в С++ то в математику.

О базисах и минимизации я уже писал. Так что добавить нечего.
24 ноя 14, 12:25    [16895654]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Гость_11111
Guest
Не думаю, что автору было нужно узнать максимум любых двух чисел. Наверное, было достаточно и для положительных. Потому

def f(a, b):
c = - ((a % b - a) // a)
return c * a + (1 - c) * b

Для произвольных чисел алгоритм не подойдет, но думаю двигаться нужно в этом направлении, так как такие задачки часто задают школьникам на "подумать" прежде, чем рассказать о if и т.п.

К примеру

http://informatics.mccme.ru/mod/statements/view3.php?id=2296&chapterid=2958
14 авг 15, 22:16    [18020493]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2650
Anatoly Moskovsky
Вася Уткин,

Сорри, приз переходит к Aleksandr Sharahov :)


Всё-таки нет. Правильных решений на этих 4х страницах практически нет(в том числе и мое первое рассуждение содержит ошибку)
8 авг 16, 14:22    [19515825]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: максимум без if  [new]
jksfj23jk
Member

Откуда:
Сообщений: 1
на Python 3.4.2
a = int(input())
b = int(input())
r= a * (a // b)
rr = b * (b // a)
rrr = int((r + rr) / (a//b + b//a))
print(rrr)
18 окт 18, 01:58    [21707297]     Ответить | Цитировать Сообщить модератору
 Re: максимум без if  [new]
Лысый дядька
Member

Откуда:
Сообщений: 356
jksfj23jk
на Python 3.4.2


max = lambda x, y: (x,0,y)[(y-x)//abs(y-x)+1]
20 окт 18, 13:35    [21709741]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4      [все]
Все форумы / Программирование Ответить