Умножить с ограниченными операциями

44

Есть 500 представителей неофициальной награды за лучший текущий ответ .

Цель

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

  1. прибавление x,y -> x+y
  2. Взаимный x -> 1/x( не деление x,y -> x/y)
  3. Отрицание x -> -x( не вычитание x,y -> x-y, хотя вы можете сделать это как две операции x + (-y))
  4. Константа 1(никакие другие константы не допускаются, кроме тех, которые получены операциями из 1)
  5. Переменная присваивание [variable] = [expression]

Оценка: значения начинаются с переменных aи b. Ваша цель - сохранить их продукт a*bв переменной, cиспользуя как можно меньше операций. Каждая операция и присвоение +, -, /, =стоит балл (эквивалентно каждому использованию (1), (2), (3) или (4)). Константы 1свободны. Решение с наименьшим количеством очков выигрывает. Tiebreak - самый ранний пост.

Допуск: Ваше выражение должно быть арифметически правильным для «случайных» реалов aи b. Он может не на меру нуль подмножества R 2 , то есть набор , который не имеет области , если график в a- bдекартовой плоскости. (Это, вероятно, понадобится из-за обратных выражений, которые могут быть 0похожи 1/a.)

Грамматика:

Это . Никакие другие операции не могут быть использованы. В частности, это означает отсутствие функций, условий, циклов или нечисловых типов данных. Вот грамматика для разрешенных операций (возможности разделены |). Программа представляет собой последовательность <statement>s, где a <statement>задается следующим образом.

<statement>: <variable> = <expr>
<variable>: a | b | c | [string of letters of your choice]
<expr>: <arith_expr> | <variable> | <constant>
<arith_expr>: <addition_expr> | <reciprocal_expr> | <negation_expr> 
<addition_expr>: <expr> + <expr>
<reciprocal_expr>: 1/(<expr>)
<negation_expr>: -<expr>
<constant>: 1

На самом деле вам не нужно публиковать код в этой точной грамматике, если ясно, что вы делаете, и ваш счет операций верен. Например, вы можете написать a-bдля a+(-b)и считать это как две операции, или определить макросы для краткости.

(Был предыдущий вопрос « Умножение без умножения» , но он позволял значительно более свободный набор операций.)

XNOR
источник
4
Это вообще возможно?
Ypnypn
1
@Ypnypn Да, и я написал пример, чтобы убедиться.
xnor
2
Это похоже на проблему, когда оптимальное решение может быть найдено (после того, как любое решение было найдено). Так что же такое в этом случае?
Мартин Эндер
1
@ MartinBüttner Tiebreak - самое раннее сообщение в этом случае. Я думаю, что есть много места для оптимизаций, поэтому я не думаю, что это будет просто гонка, чтобы найти тот, который работает, и написать его аккуратно. По крайней мере, это то, что я нашел, попробовав это; возможно кто-то найдет явно минимальное решение.
xnor
2
Хорошо, так как не все думали, что мой ответ был таким же забавным, как я, я удалил его и прокомментировал здесь: Правило о наборе нулей меры выбрано не очень разумно, так как рациональные числа - это набор нулей меры в отношении меры Лебега, я бы предложил используя определенный процент вместо этого. (Или другой вид) Но мне полностью нравится идея этого вызова!
flawr

Ответы:

34

22 операции

itx = 1/(1+a+b)     #4
nx = -1/(itx+itx)   #4
c = -( 1/(itx + itx + 1/(1+nx)) + 1/(1/(a+nx) + 1/(b+nx)) ) #14

Попробуйте онлайн!

Операции: 10 сложений, 7 инверсий, 2 отрицания и 3 задания.

Итак, как я получил это? Я начал с многообещающего шаблона суммы двух двухэтажных фракций, мотив, который появлялся во многих предыдущих попытках.

c = 1/(1/x + 1/y) + 1/(1/z + 1/w)

Когда мы ограничиваем сумму x+y+z+w=0, происходят прекрасные отмены, давая:

c = (x+z)*(y+z)/(x+y),

который содержит продукт. (Часто легче получить t*u/v, чем t*uпотому, что первый имеет степень 1.)

Есть более симметричный способ думать об этом выражении. С ограничением x+y+z+w=0их значения задаются тремя параметрами p,q,rих попарных сумм.

 p = x+y
-p = z+w
 q = x+z
-q = y+w
 r = x+w
-r = y+z

и у нас есть c=-q*r/p. Сумма pвыделяется в знаменателе как соответствующая парам (x,y)и (z,w)переменным, которые находятся в одной и той же дроби.

Это хорошее выражение для cin p,q,r, но двойная дробь в, x,y,z,wтак что мы должны выразить первое в терминах последнего:

x = ( p + q + r)/2
y = ( p - q - r)/2
z = (-p + q - r)/2
w = (-p - q + r)/2

Теперь мы хотим выбрать p,q,rтак, чтобы c=-q*r/pравнялись a*b. Один выбор:

p = -4
q = 2*a
r = 2*b

Затем удвоенные значения qи rудобно делить пополам на:

x = -2 + a + b
y = -2 - a - b
z =  2 + a - b
w =  2 - a + b

Сохранение 2в виде переменной tи включение их в уравнение для cдает решение с 24 операциями.

#24 ops
t = 1+1   #2
c = 1/(1/(-t+a+b) + 1/-(t+a+b))  +  1/(1/(-b+t+a) + 1/(-a+b+t)) #1, 10, 1, 10

Там 12 дополнений, 6 инверсий, 4 отрицания и 2 задания.

Много операций тратится на выражение x,y,z,wв терминах 1,a,b. Чтобы сохранить операции, вместо этого выражайте xв p,q,r(и, таким образом a,b,1), а затем пишите y,z,wв терминах x.

y = -x + p
z = -x + q
w = -x + r

Выбор

p = 1
q = a
r = b

и выражая cс отрицанием как c=-q*r/p, мы получаем

x = (1+a+b)/2
y = -x + 1
z = -x + a
w = -x + b

К сожалению, вдвое xдороже. Это нужно сделать путем инвертирования, добавления результата к себе и повторного инвертирования. Мы также NEGATE производить nxдля -x, так это то, что y,z,wиспользование. Это дает нам 23-операционное решение:

#23 ops
itx = 1/(1+a+b)     #4
nx = -1/(itx+itx)   #4
c = -( 1/(1/(-nx) + 1/(1+nx))  +  1/(1/(a+nx) + 1/(b+nx)) ) #15

itx1 / (2 * х) и nxесть -x. Окончательная оптимизация выражения, 1/xпоскольку itx+itxвместо шаблонного, 1/(-nx)вырезает символ и доводит решение до 22 операций.

XNOR
источник
Там легко оптимизировать до 21 операции. itx + itxпроисходит дважды, но itxне встречается ни в каком другом контексте. Вместо этого определите, ix = (1+1)/(1+a+b)и вы замените два дополнения одним.
Питер Тейлор
И, извлекая m = -1, можно получить 20:nx = (1+a+b)/(m+m); c = m/(m/nx + 1/(1+nx)) + m/(1/(a+nx) + 1/(b+nx))
Питер Тейлор
3
Ах, обе из этих оптимизаций терпят неудачу, потому что поддерживаемая операция является взаимной, а не делением.
Питер Тейлор
Если aи bтолько один, то либо, a + nx = 0либо b + nx = 0, в результате чего ваше решение делится на ноль.
MooseOnTheRocks
1
@MooseOnTheRocks Это нормально, посмотрите на «допуск» в проблеме, что код может дать сбой на подмножестве с нулем меры. Я думаю, что задача невозможна иначе.
xnor
26

23 операции

z = 1/(1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b))
res = z+z

доказательство взрывом:

z = 1/(1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b))
             1/(a+1)+1/(b+1)                            == (a+b+2) / (ab+a+b+1)
          1/(1/(a+1)+1/(b+1))                           == (ab+a+b+1) / (a+b+2)
          1/(1/(a+1)+1/(b+1))-1                         == (ab - 1) / (a+b+2)
          1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1)             == ab / (a+b+2)
       1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))            == (a+b+2) / ab
                                              1/a+1/b   == (a+b) / ab
       1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b)  == 2 / ab
    1/(1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b)) == ab / 2

z = ab / 2 and therefore z+z = ab

Я использовал wolfram alpha, чтобы получить это красивое изображение (wolfram alpha пытался заставить меня подписаться на pro, чтобы сохранить его, но затем ctrl-c ctrl-v ;-)):

оценка (с добавлением +вычитания):

z = ////++/++-+/++++-/+/
res = +
гордый хаскеллер
источник
Поздравляю с кратчайшим решением!
xnor
@xnor спасибо, что дали мне мой первый принятый ответ и мою первую награду!
гордый haskeller
Не быть придирчивым, но не должен ... (b + 1)) - 1 + 1 ... и ... 1)) - (1 / a + ... be ... (b + 1) )) + - 1 + 1 ... и ... 1)) + - (1 / a + ... соответственно?
tfitzger
@ tfitzger Я думаю, что так проще. Вопрос говорит, что это не имеет значения. Обратите внимание, что я правильно считаю счет (каждый минус два)
гордый haskeller
Wolfram Alpha имеет 7-дневную бесплатную пробную версию, к вашему сведению.
ghosts_in_the_code
13

29 операций

Не работает для множества {(a, b) ∈ R 2 | a + b = 0 или a + b = -1 или ab = 0 или ab = -1}. Это наверное мера ноль?

sum = a+b
nb = -b
diff = a+nb
rfc = 1/(1/(1/sum + -1/(sum+1)) + -1/(1/diff + -1/(diff+1)) + nb + nb)  # rfc = 1/4c
c = 1/(rfc + rfc + rfc + rfc)

# sum  is  2: =+
# nb   is  2: =-
# diff is  2: =+
# rfc  is 18: =///+-/++-//+-/+++
# c    is  5: =/+++
# total = 29 operations

Структура rfc(Reciprocal-Four-C) становится более очевидной, если мы определим макрос:

s(x) = 1/(1/x + -1/(x+1))              # //+-/+ (no = in count, macros don't exist)
rfc = 1/(s(sum) + - s(diff) + nb + nb) # =/s+-s++ (6+2*s = 18)

Давайте посчитаем:

  • s(x)математически, это то, 1/(1/x - 1/(x+1))что после немного алгебры это x*(x+1)или x*x + x.
  • Когда вы подчиняете все rfc, это действительно 1/((a+b)*(a+b) + a + b - (a-b)*(a-b) - a + b + (-b) + (-b))просто 1/((a+b)^2 - (a-b)^2).
  • После разницы квадратов или просто простого расширения вы получите то, что rfcесть 1/(4*a*b).
  • Наконец, cявляется обратной 4 раза rfc, так 1/(4/(4*a*b))становится a*b.
algorithmshark
источник
2
+1, я был в процессе завершения этого идентичного расчета
Эрик Тресслер
1
Это определенно мера ноль; это союз линий.
xnor
Не собираюсь комментировать объединение линий ... @algorithmshark Можете ли вы рассказать нам больше, как вы пришли к этой идентичности? Как вы подошли к проблеме?
flawr
1
@flawr Я вспомнил, что свойства s(x)соответствуют требованиям вопроса из исчисления, так что это означало, что у меня была квадратная функция. После некоторого недоразумения я обнаружил, что могу получить a*bтермин с разницей в квадратные трюки. Как только я это понял, нужно было попытаться определить, какие назначения сохранили операции.
алгоритмическая
Так как вы используете -1три раза rfc, не могли бы вы вывести персонажа из игры, присвоив его переменной?
Исаак
9

27 операций

tmp = 1/(1/(1+(-1/(1/(1+(-a))+1/(1+b))))+1/(1/(1/b+(-1/a))+1/(a+(-b))))
res = tmp+tmp+(-1)

# tmp is 23: =//+-//+-+/++///+-/+/+-
# res is 4: =++-

За этим нет теории. Я просто попытался получить (const1+a*b)/const2и начал с (1/(1-a)+1/(1+b))и (-1/a+1/b).


источник
Тебе tmpна самом деле 23, и ты набрал 27 баллов.
алгоритмическая