Нет разветвления пожалуйста

14

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

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

Для следующих задач все переменные представляют собой 32-разрядные целые числа без знака, и единственным допустимым кодом являются операторы простого набора, включающие только следующие операторы:

+ addition
- subtraction
* multiplication
/ integer division, rounds down, division by 0 not allowed
% modulo
& binary and
| binary or
^ binary exclusive or
>> bitshift right
<< bitshift left

Logic operators, return 1 if the expression is true and 0 if it is false.
== equal
!= not equal
< less than
<= less than or equal
> greater than
>= greater than or equal

Set operator
=

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

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

Игра в гольф учитывает только количество операторов.

Пример:

myvar = ( ( ( foo + 5 ) * bar ) % 7 ) == 3

Имеет оценку 5 операторов.

Решение может включать столько переменных, сколько автор сочтет нужным.
Переменные, которые не были установлены, имеют значение 0.
Переполнение и сгущенного допускаются, все отрицательные числа Underflow, так 3 - 5это 4294967294, даже как часть большего заявления.

Задача 1: Макс

Два значения Aи Bсуществуют в области видимости, чтобы RESULTпеременная содержала наибольшее из этих значений при завершении программы.

Задача 2: Медиана

Три значения, A, Bи C, существует в объеме, сделать RESULTпеременный содержат медиану тех значений , когда программа завершает свою работу .

Задача 3: Квадратный корень

Одно значение, Aсуществующее в области действия, заставляет RESULTпеременную содержать квадратный корень A, округленный вниз, когда программа завершается.

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

AAAAAAAAAAAA
источник
Где унарные операторы? Мне все равно, -но ~может быть приятно (даже если я не знаю, для чего).
Джон Дворжак
Конечно, 0xFFFF_FFFF_FFFF_FFFF ^ xи 0 - x. Как я мог забыть?
Джон Дворжак
@JanDvorak Он сделал кратчайшее описание, полнота логики не !является также довольно тривиально: x == 0.
аааааааааааа
Каково поведение деления на ноль?
Джон Дворжак
В Mathematica (a> b) возвращает True или False. Boole преобразует False в 0 и True в 1. Законно ли это использовать Boole[a-b]?
DavidC

Ответы:

5

Задача 3, 23 операции

x = (A >> 16) + A / ((A >> 13) + 511) + 15
x = (x + A/x) >> 1
x = (x + A/x) >> 1
x = (x + A/x) >> 1
RESULT = x - (x > A/x)

Использование метода Ньютона, как и других решений, с более тактично выбранным начальным числом. Первый бит A >> 16удерживает верхнюю часть диапазона счастливым, второй - счастливую A / ((A >> 13) + 511)середину диапазона, а последний 15- нижнюю, а также предотвращает деление на ноль ошибок (15 - наибольшее возможное значение, которое позволяет 0правильно сходиться - делится пополам трижды минус коррекция равна нулю). Для входных значений 225, 275625, 82137969, 2908768489(и близлежащих значений) начальное начальное число является точным. Все граничные случаи (идеальные квадраты, идеальные квадраты + 1 и идеальные квадраты - 1) в диапазоне 0 .. 2**32-1были проверены и являются правильными.

Несколько комментариев о правилах:
допускается переполнение и недополнение, все отрицательные числа недопустимы, поэтому 3 - 5 равно 4294967294, даже как часть более крупного оператора .

Этот последний бит оказывается чем-то вроде убийцы инноваций. Сначала я попытался найти решение, используя обобщенную форму метода Галлея , но понял, что оно недопустимо с учетом вышеуказанного ограничения. Итерация (применительно к квадратным корням) такова:

x = x * (3*A + x*x) / (A + 3*x*x)

Эта итерация обладает хорошими качествами, которых нет у Ньютона. Он сходится кубически (а не квадратично), он сходится сверху или снизу (а не только сверху) и не так чувствителен к плохо выбранному семени (если итерация Ньютона обеспечит семя, которое является слишком низким, оно будет сильно перебить точку схождения, а затем нужно вернуться обратно вниз).

У метода Ньютона также есть проблема (по крайней мере, когда речь идет о целых числах), что он довольно часто достигает x, такого что A / x - x = 2 - в этом случае он будет сходиться к значению, которое на единицу больше, чем правильный целочисленный корень, который должен быть исправлен; Метод Галлея не нуждается в такой коррекции. Но, к сожалению, значение 3*A + x*xчасто будет больше, чем допустимое 32-разрядное целочисленное пространство.

Существует ряд других обобщенных n- х корневых алгоритмов, но все они имеют одну и ту же характеристику:

x = x + x*(v - x**n)/(v*n)
x = (x*(n+1) - x**(n+1)/v)/n
x = ((n-2)*x + (4*v*x)/(v + x**n))/n
x = x*((n+2)*v + (n-2)*x**n)/(v + x**n)/n
x = ((n-2)*x + (n*x*v)/(v + (n-1)*x**n))/(n-1)
x = ((n-2)*x + x*((n*2-1)*v + x**n)/(v + (n*2-1)*x**n))/(n-1)

x = x + 2*x*(v - x**n)/(v + x**n)/n
x = x + x*31*(v - x**n)/(10*v + 21*x**n)/n
x = x + x*561*(v - x**n)/(181*v + 380*x**n)/n
x = x + x*1153*(v - x**n)/(372*v + 781*x**n)/n

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

Примо
источник
Довольно мило, но не для 4294967295. Что касается правил, они должны быть жесткими, чтобы сделать его интересным. Вы можете поспорить, какие именно условия создают наилучшую проблему, но в конечном итоге гораздо важнее, чтобы правила были ясными и однозначными, чем то, что именно они позволяют.
аааааааааааа
Я не думаю, что в любом случае Галлея стоила бы этого, из далекого предположения, что он улучшится чуть менее чем в 3 раза, Ньютон - чуть менее, чем в 2 раза. Аналогично из хорошего предположения, Галлея утроится точность, Ньютон удвоит его. Так что одна итерация Галлея стоит в точности log(3)/log(2) ~= 1.585итераций Ньютона.
аааааааааааа
@eBusiness Первоначально у меня было 2 Хэлли с подобным образом выбранным семенем на общую сумму 25 операций - с ошибкой, когда A = 0- так что это на самом деле короче. Приблизительно 4294967295 , это был недосмотр: при 65536² ≡ 0 итерация исправления не может быть исправлена. Я посмотрю, смогу ли я найти альтернативу.
Примо
@eBusiness исправлено.
Примо
Изящный квадратный корень пакета, отличная работа и официальный значок победы.
aaaaaaaaaaaa
5

65 (61) операций (5 + 13 + 47 (43))

Задача 1 - Макс (A, B)

RESULT = A + (B - A) * (A <= B)

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

Задача 2 - Середина (A, B, C)

RESULT = A                               \
       + (B - A) * (A > B) ^ (B <= C)    \
       + (C - A) * (A > C) ^ (C <  B)

Это улучшение по сравнению с моим предыдущим 15-операционным решением, которое обусловило все три переменные - это спасло два вычитания, но оно ввело еще один тест центральности. Сам тест прост: элемент находится посередине, если только один из двух находится выше.

Задача 3 - sqrt (A)

X1     = 1024 + A / 2048
X2     = (X1  + A / X1 ) / 2
...
X10    = (X9 + A / X9 ) / 2
RESULT = X16 - (X16 * X16 > A)

Одиннадцать раундов приближения Ньютона. Волшебная постоянная 1024 уже побита WolframW (а 512 вызывает деление на ноль при a = 0 до того, как a = 2 ** 32 сходится), но если мы можем определить 0/0 как ноль, десять итераций будут работать с начальным значением из 512. Я признаю, что мое утверждение о десяти итерациях не совсем чисто, но я все еще претендую на них в скобках. Я должен исследовать, если девять возможно, как бы то ни было.Решение WolframH состоит из девяти итераций.

Джон дворак
источник
Я думаю, что первая строка Задачи 3 не верна: вторая константа должна быть в 4 раза больше первой константы (чтобы иметь «чистый» Ньютон).
Восстановить Монику
@WolframH Лучшее начальное предположение может объяснить, почему я теряю циклы. Где вы взяли 4 *? Это выглядит как две итерации, объединенные в одну.
Джон Дворжак
(1024 + A/1024)/2 == (512 + A/2048)(что, как X0 = 1024, а затем запуск Ньютона).
Восстановить Монику
Хорошее решение задачи 1. Яйцо Колумба.
DavidC
@DavidCarraher, конечно, правильное решение было бы MOV RESULT, A; CMP A,B; CMOVA RESULT, B;-)
Джон Дворжак
5

1: 5 операторов

RESULT = B ^ (A ^ B)*(A > B)

Операторы 2: 13

RESULT = B ^ (A ^ B)*(A > B) ^ (A ^ C)*(A > C) ^ (B ^ C)*(B > C)

3: 27 операторов

g = 47|((0x00ffffff & A)>>10)|(A>>14)
r = (g + A/g)/3
r = (r + A/r)>>1
r = (r + A/r)>>1
r = (r + A/r)>>1
RESULT = r - (r*r-1>=A)
AAAAAAAAAAAA
источник
5

Задача 3, 39 Операции

РЕДАКТИРОВАТЬ: изменена последняя строка; смотрите комментарии.

Это реализация метода Newthon. Проверено со всеми положительными квадратами, а также с положительными квадратами минус один, а также миллион случайных чисел в диапазоне от 0 до 2 ^ 32-1. На первый взгляд забавное начальное значение является коротким, для (1022 + A/1022) / 2которого требуется наименьшее количество итераций (я думаю), а также делает правильное значение RESULTfor A=0(что было бы не так 1024вместо 1022).

r = (511 + A/2044)
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
RESULT = r - (r > A/r)
Восстановить Монику
источник
Должен ли я сохранить свою низшую копию метода Ньютона, которая была оптимизирована параллельно с вашей и опубликована через некоторое время? Великие умы думают одинаково, а разделение решения на два или два ответа - это плохо, но таково текущее положение дел, поскольку вы еще не ответили №2.
Джон Дворжак
@JanDvorak: Спасибо, что спросили. Это нормально, если вы добавите мой немного более короткий метод в свой ответ. Кроме того, спасибо, что дали мне кредит :-)
Восстановите Монику
Действительно хорошая попытка, но не для ввода с 4294965360 по 4294967295.
aaaaaaaaaaaa
@eBusiness: Какой результат вы получите за эти материалы? Я получаю 65535 в моих тестах, и это нормально.
Восстановить Монику
Я получаю 65536. Возможно, вы не используете предписанный формат целого числа.
аааааааааааа