Программистская задачка

[spamsink]

Постом Аввы навеяло.

Известна задача для интервью: написать int f(int x), которая для x==a возвращает b, а для x==b возвращает a. Один из вариантов ответа при данной спецификации: int f(int x) { return a+b-x; }

Напишите целое арифметико-логическое выражение (не использующее тернарного оператора и сравнений) с переменной х, которое для данных 32-битных целых a, b, c при x==a принимает значение b, при x==b - значение c, при x==c - значение a, в остальных случаях результат произволен. Для каких a, b, c решение существует?

Comments

[ygam.livejournal.com]

(int)(1.0*a*(x-a)*(x-b)/(c-a)/(c-b) + 1.0*b*(x-b)*(x-c)/(a-b)/(a-c) + 1.0*c*(x-a)*(x-c)/(b-a)/(b-c))

[maksa.livejournal.com]

Ну вот, опередили…

[avva.livejournal.com]

да, я то же самое примерно собирался.

[spamsink]

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

[spamsink]

Это слишком в лоб, да и работать не всегда будет. Я хотел целое выражение.

[maksa.livejournal.com]

Тогда это действительно программистское. И я пас.

[spamsink]

В решении существенную роль играет математический трюк, малоизвестный большинству программистов.

[maksa.livejournal.com]

Я про то, что требуется учитывать разрядность чисел и их представление. Это уже не математическая задача. Не мой профиль, не буду мучиться.

[sab123.livejournal.com]

Для ограниченных случаев:

делим 32 бит на 3 10-битовых поля и два старших бита оставляем неиспользованными.

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

#define MASK ((1<<10)-1)
#define MASKHI ((MASK << 10)|(MASK << 20))

int f(int x) {
return ((x & MASK)<<20)
| ((x &MASKHI) >> 10);
}

Соответственно, a, b, и c - такие, которые можно представить этими сдвигами. Ну и, естественно, можно брать меньше 10 бит, и неиспользуемые биты раскидывать по числу произвольным образом, и сдвиги делать в разные стороны.

[spamsink]

С какой вероятностью для произвольных трех чисел этот алгоритм будет работать? Мое решение, которое я покажу завтра, работает в 75% случаев.

[spamsink]

А с некоторыми модификациями - для любой тройки попарно различных чисел.

[sab123.livejournal.com]

А не знаю. Очевидного подсчета я не вижу, а много думать как-то лень.

то что результат == 0 или 1 ?

[zhengxi.livejournal.com]

(x==a)*b + (x==b)*c + (x==c)*a

(-(x==a))&b | (-(x==b))&c | (-(x==c))&a

Re: то что результат == 0 или 1 ?

[zhengxi.livejournal.com]

а, сравнения нелься, не заметил

Re: то что результат == 0 или 1 ?

[zhengxi.livejournal.com]

хотя.. функцию сравнения можно сделать используя вычитание(или xor) и последующее сранение с нулём.
а сравнение с нулём - это -(x|(x<<1)|...|(x<<31))

Re: то что результат == 0 или 1 ?

[spamsink]

Это, конечно, сработает, но уж очень утомительно и печально. Мое решение гораздо более короткое и красивое - и недалеко ушло от решений, использующих плавающую точку (это подсказка).

Вот

[zhengxi.livejournal.com]

unsigned change(unsigned x,unsigned a,unsigned b)
{
unsigned y=x^a;
y|=y<<1; y|=y<<2; y|=y<<4; y|=y<<8; y|=y<<16;
y|=y>>1; y|=y>>2; y|=y>>4; y|=y>>8; y|=y>>16; /* y=x==a ? 0 : 0xffffffff */
return b&~y;
}

unsigned f(unsigned x, unsigned a, unsigned b, unsigned c)
{
return change(x,a,b) | change(x,b,c) | change(x,c,a);
}

Re: Вот

[spamsink]

Формально да, но по существу - издевательство. :) Завтра ближе к вечеру GMT-8 напишу свое решение. Авось кто до этого времени догадается, как пересобачить решение с плавающей точкой на целые числа.

[ivan-ghandhi.livejournal.com]

Модуль можно? ;)

[spamsink]

В смысле % ? Можно, конечно.

Re: Вот

[arno1251.livejournal.com]

Голову сломал, но не вижу. Жду с нетерпением.

[kcmamu.livejournal.com]

Если все a, b, c разные: (b*!(x-a)) + (c*!(x-b)) + (a*!(x-c))

Если два совпадают, решения нет.

Если все три совпадают, то просто x или a.

[arno1251.livejournal.com]

Класс! :)

[spamsink]

Увы, не пойдет. Оператор !х - это синоним запрещенного x == 0.

Два числа совпадать не могут - этот случай противоречит условию.

[spamsink]

Не годится. !х - это то же самое, что и x == 0, что по условию нельзя.

Re: Вот

[zhengxi.livejournal.com]

Издевательство будет если написать class 96-битного инта и иcпользовать его в первой формуле вместо float :)

[(Anonymous)]

Значит, логические операторы не все годятся?
Тогда на всякий случай сделаем чистой арифметикой.
Пусть (unsigned)a < (unsigned)b < (unsigned)c (в остальных пяти случаях аналогично).

int f(int x)
{
unsigned ua = a;
unsigned ub = b;
unsigned uc = c;
unsigned ux = x;
unsigned mu = -1;
// начало места, зависящего от порядка между ua, ub, uc
// индикатор максимальной из трех точек
int ic = ux/uc;
// индикатор минимальной из трех точек
int ia = (mu - ux)/(mu - ua);
// индикатор оставшейся (средней) точки
int ib = 1 - ic - ia;
// конец особенного места
return ia*b + ib*c + ic*a;
}

[kcmamu.livejournal.com]

Анонимный ответ сейчас был от меня.

[spamsink]

Спасибо, это будет еще одним вариантом.

[kcmamu.livejournal.com]

А такое устроит?

b*(1+( ((x-a)|(a-x)) >> 31 )) +
c*(1+( ((x-b)|(b-x)) >> 31 )) +
a*(1+( ((x-c)|(c-x)) >> 31 ))

[spamsink]

Не в этом виде (сдвиг вправо не обязан размножать знак), но идея понятна.

[kcmamu.livejournal.com]

А вот еще "теоретический" метод.

Пусть p -- наименьшее простое число, на которое не делится (в обычном математическом смысле) ни одна из разностей a-b, a-c, b-c.

Оно не больше 79, так как произведение простых от 2 до 79 больше, чем 2⁹⁶.

Функция y(x) = ((x%p)+p)%p отобразит a, b, c в три разных числа A, B, C, лежащие в [0,p-1].

А дальше замечаем, что Z_p -- поле, поэтому можно пользоваться интерполяционной формулой и построить три квадратных трехчлена PA(y), PB(y), PC(y), равных 1 (mod p) в одной из точек y=A, y=B, y=C, и 0 (mod p) в двух оставшихся. Коэффициенты можно, не ограничивая общности, брать из [0,p-1]. Тогда значения этих трехчленов (как обычные целые числа) на [0,p-1] будут лежать между 0 и (p-1)+(p-1)*(p-1)+(p-1)*(p-1)*(p-1), что с огромным запасом укладывается в диапазон представимых положительных чисел.

Далее стандартное разложение:
b*(PA(y(x))%p) + c*(PB(y(x))%p) + a*(PC(y(x))%p)

[spamsink]

Кайф какой! Это самое строгое решение - ни единого неарифметического действия.

[ivan-ghandhi.livejournal.com]

Я чё про модуль-то спрашивал:

!x = (abs(x+1) + x + 1) * (abs(x-1) - x + 1) / 4

Если abs нельзя, то определим его как
abs(x) = x * sign(x), where
sign(x) = 1 & (x >>> 32)

[spamsink]

Это красивая реализация !х, не видел такой раньше.

бессмысленное полурешение

[ilya-dogolazky.livejournal.com]

Наверное это не то, что имеется в виду, но всё ж: вот доказательство, что при попарно различных а,б,в такое выражение существует (ну а если они НЕ попарно различны, то оно и подавно существует и указано вами в предисловии). Представим себе множество 32-битных значений как 32 мерное пространство над полем вычетов по модулю два. Операция сложения векторов (побитовое исключающее или) к счастью имеется в Си, а умножение на скаляр нам не нужно, так как никаких скаляров кроме 0,1 в нашем поле и нет. Требуемое в задаче отображение можно выбрать афинным (тут единственное место, где требуется попарная различность --- пользуемся тем, что б-а и в-а не совпадают и не равны нулю, а следовательно --- линейно независимы). Значит формула такая: Ф(х)=Л(х+а)+б, где плюс это сложение векторов, и Л это произвольное (тут произвол огромен) линейное отображение отображающее б+а на в+а и в+б на а+б. Остался вопрос --- как закодировать на Си произвольное линейное отображение? Очень просто, рассмотрим стандартный базис нашего пространства, то есть слова с единственным битиком. Имея матрицу Л относительно этого базиса можно запрсто записать Л как комбинацию кучи побитовых И и ИЛИ и сдвигов на константные расстояния вправо-влево.

Re: бессмысленное полурешение

[ilya-dogolazky.livejournal.com]

Вкралась ошибка в определении Л, следует читать Л(б+а)=в+б, Л(в+а)=а+б, ну это и так понятно :-)

Re: бессмысленное полурешение

[spamsink]

В целом правильно. Размер кучи равен двум.

[ilya-dogolazky.livejournal.com]

двум? ну тогда здорово получилось :-) Но я сейчас ходил гулять и придумал решение, которое сильно лучше --- оно вообще не испльзует тот факт, что аппроксимируемая функция задана значениями именно в трёх точках, а допускает произвольное число пар точка/значение. Если вам интересно (и если в моём решении не окажется дырок :-), то могу записать его.

[spamsink]

Для произвольного числа пар - интересно. Если это работает, то можно использовать в качестве совершенной хеш-функции.

[ilya-dogolazky.livejournal.com]

Обозначим точки буквами а,б,...,я. Обозначим требуемые значения через Фа,Фб,...,Фя. Если мы сумеем написать для каждой буквы й функцию Гй, принимающую значения 0 на всех буквах кроме й и Гй(й)=1, то всё готово: Ф=сумма{Фй*Гй по всем й от а до я}. Ну понятно куда я клоню --- к аппроксимации многочленом. Осталось найти выражение для Га. Напишем на бумажке стандартную формулу: Га(х)=((х-б)...(х-я)) / ((а-б)...(а-я)). Обратите внимание на скобки --- сначала вычисляем числитель и знаменатель, и лишь когда они целиком вычислены, применяем оператор деления. Что тут может обломиться? С обычным переполнением проблем нет, так как для х=а сверху и снизу стоят одинаковые вещи, а для х=б,...,я сверху стоит ноль. Единственная проблема это «переполнение-обнуление», то есть всё перестаёт работать, если в знаменателе стоит ноль. Как такое может случиться? Только в том случае, когда среди сомножителей знаменателя слишком много чисел, делящихся на слишком большие степени двойки. Вот если бы они все были нечётными (мечты-мечты), всё было бы ништяк. Но эти сомножители --- константы, так что давайте их возьмём и поделим, каждое на максимально возможную степень двойки.


Теперь медленно и аккуратно. Добавим к языку Си ещё одну операцию --- для двух неравных констант времени компиляции обозначим через х\у минимальное неотрицательное целое число, такое что (х-у)»(х\у) кончается на битик 1, то бишь является нечётным. Ну вот вроде и всё, осталось в формуле для Га заменить в числителе все выражения вида (х-б) на ((х-б)»(а\б)), да в знаменателе заменить (а-б) на ((а-б)»(а\б)) [ну и аналогично для остальных в,...,я вместо б]. Теперь в знаменателе стоит произведение нечётнных чисел, так что во всяком случае не ноль. Что происходит с числителем? Если он вычисляется с х=а, то он идентичен знаменателю, то есть сверху и снизу одинаковые ненулевые значения (пусть бы даже и настало переполнение), а если вычисляется с х=б или в,...,я, то числитель благополучно обнуляется.

Ну вот как-то так. Ну ещё конечно надо подуматть, как эту формулу быстро вычислить, банальное вычисление даёт О(м²), где «м» размер алфавита, то есть количество точек аппроксимации, но так как я не имею ни малейшего представления о конкретном применении, тут вам и карты в руки :-)

[spamsink]

Увы, дороговато получается. Есть более дешевые совершенные хеш-функции.

[ilya-dogolazky.livejournal.com]

Здорово, мне понравилось! Я подумывал некоторое время, как бы поле подходящее найти, но в результате сделал совсем по-другому, увы не так изящно, как у Вас.

[ilya-dogolazky.livejournal.com]

А о какой задаче речь? Что есть ввод, что есть вывод, сколько дано времени и памяти?

[spamsink]

Задача ставится как нахождение функции, которая на данных N элементах из какого-либо множества (обычно строк на данном алфавите) принимает N разных целых значений. Минимальной называется такая из совершенных хеш-функций, которая принимает значения от 0 до N-1 включительно (в произвольном порядке), и тогда начинает иметь смысл формулировка "найти биекцию между данными N целых и 0...N-1".

Памяти O(N), времени - константа, или, в случае строк, O(длина строки)