Há uma recompensa não oficial de 500 representantes por vencer a melhor resposta atual .
Objetivo
Seu objetivo é multiplicar dois números usando apenas um conjunto muito limitado de operações aritméticas e atribuição de variáveis.
- Adição
x,y -> x+y
- Recíproco
x -> 1/x
( não divisãox,y -> x/y
) - Negação
x -> -x
( não subtraçãox,y -> x-y
, embora você possa fazer isso como duas operaçõesx + (-y)
) - A constante
1
(nenhuma outra constante é permitida, exceto como produzida pelas operações de1
) - Atribuição variável
[variable] = [expression]
Pontuação: Os valores começam nas variáveis a
e b
. Seu objetivo é salvar o produto a*b
na variável c
usando o mínimo de operações possível. Cada operação e atribuição +, -, /, =
custa um ponto (equivalentemente, cada uso de (1), (2), (3) ou (4)). As constantes 1
são gratuitas. A solução com menos pontos ganha. O desempate é o primeiro post.
Permissão: Sua expressão deve estar aritmeticamente correta para reais a
e "aleatórios" b
. Ele pode falhar num subconjunto medida de zero de R 2 , isto é, um conjunto que não tem nenhuma área se representados graficamente na a
- b
plano cartesiano. (É provável que isso seja necessário devido a recíprocas de expressões que possam ser 0
semelhantes 1/a
.)
Gramática:
Este é um código-atômico-golfe . Nenhuma outra operação pode ser usada. Em particular, isso significa que não há funções, condicionais, loops ou tipos de dados não numéricos. Aqui está uma gramática para as operações permitidas (as possibilidades são separadas por |
). Um programa é uma sequência de <statement>
s, onde a <statement>
é dada da seguinte maneira.
<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
Na verdade, você não precisa postar código nesta gramática exata, desde que fique claro o que você está fazendo e sua contagem de operações esteja correta. Por exemplo, você pode escrever a-b
para o a+(-b)
e contá-lo como duas operações, ou definir macros para brevidade.
(Havia uma pergunta anterior Multiplicar sem Multiplicar , mas permitia um conjunto de operações muito mais flexível.)
Respostas:
22 operações
Experimente online!
As operações são 10 adições, 7 inversas, 2 negações e 3 atribuições.
Então, como eu consegui isso? Comecei com o modelo de aparência promissora da soma de duas frações de dois andares, um motivo que havia aparecido em muitas tentativas anteriores.
c = 1/(1/x + 1/y) + 1/(1/z + 1/w)
Quando restringimos a soma
x+y+z+w=0
, ocorre um cancelamento bonito, fornecendo:c = (x+z)*(y+z)/(x+y)
,que contém um produto. (Muitas vezes é mais fácil obter
t*u/v
do quet*u
porque o primeiro tem o grau 1.)Existe uma maneira mais simétrica de pensar sobre essa expressão. Com a restrição
x+y+z+w=0
, seus valores são especificados por três parâmetrosp,q,r
de suas somas em pares.e nós temos
c=-q*r/p
. A somap
é distinguida como estando no denominador por corresponder aos pares(x,y)
e(z,w)
às variáveis que estão na mesma fração.Esta é uma boa expressão para
c
inp,q,r
, mas a fração de dois andares está em,x,y,z,w
portanto devemos expressar a primeira em termos da segunda:Agora, queremos escolher
p,q,r
para quec=-q*r/p
seja iguala*b
. Uma escolha é:Em seguida, os valores dobrados
q
er
são convenientemente divididos pela metade em:Salvar
2
como variávelt
e conectá-los à equação dec
fornece uma solução 24-op.Existem 12 adições, 6 inversas, 4 negações e 2 atribuições.
Muitas operações são gastas expressando
x,y,z,w
em termos de1,a,b
. Para salvar ops, expressex
emp,q,r
(e assima,b,1
) e depois escrevay,z,w
em termos dex
.Escolhendo
e expressando
c
com uma negação comoc=-q*r/p
, temosInfelizmente, reduzir para metade
x
é caro. Isso precisa ser feito invertendo, adicionando o resultado a si próprio e invertendo novamente. Nós também negate para produzirnx
para-x
, uma vez que é o quey,z,w
uso. Isso nos dá a solução 23-op:itx
é 1 / (2 * x) enx
é-x
. Uma otimização final da expressão1/x
como emitx+itx
vez do modelo1/(-nx)
corta um caractere e reduz a solução para 22 operações.fonte
itx + itx
ocorre duas vezes, masitx
não ocorre em nenhum outro contexto. Defina em vez dissoix = (1+1)/(1+a+b)
e substitua duas adições por uma.m = -1
, é possível obter 20:nx = (1+a+b)/(m+m); c = m/(m/nx + 1/(1+nx)) + m/(1/(a+nx) + 1/(b+nx))
a
eb
são apenas um separados, então uma + nx = 0
ou outrob + nx = 0
, fazendo com que sua solução seja dividida por zero.23 operações
prova por explosão:
Eu abusei do wolfram alpha para obter essa imagem bonita (o wolfram alpha tentou me inscrever no pro para salvá-lo, mas depois ctrl-c ctrl-v ;-)):
score (com adição
+
de subtração):fonte
29 operações
Não funciona para o conjunto {(a, b) ∈ R 2 | a + b = 0 ou a + b = -1 ou ab = 0 ou ab = -1}. Provavelmente isso é zero?
A estrutura de
rfc
(Recíproco-Quatro-C) é mais evidente se definirmos uma macro:Vamos fazer as contas:
s(x)
, matematicamente, é o1/(1/x - 1/(x+1))
que é depois de um pouco de álgebra éx*(x+1)
oux*x + x
.rfc
, é realmente o1/((a+b)*(a+b) + a + b - (a-b)*(a-b) - a + b + (-b) + (-b))
que é justo1/((a+b)^2 - (a-b)^2)
.rfc
é1/(4*a*b)
.c
é o recíproco de 4 vezesrfc
, assim1/(4/(4*a*b))
se tornaa*b
.fonte
s(x)
encaixavam nos requisitos da pergunta, do cálculo, o que significava que eu tinha uma função quadrada. Depois de algumas perguntas, descobri que poderia conseguir uma*b
termo com o truque da diferença de quadrados. Uma vez que eu tive isso, era uma questão de experimentar quais atribuições salvavam operações.-1
três vezesrfc
, você não pode jogar fora um personagem atribuindo-o a uma variável?27 operações
Não há teoria por trás disso. Eu apenas tentei começar
(const1+a*b)/const2
e comecei com(1/(1-a)+1/(1+b))
e(-1/a+1/b)
.fonte
tmp
tem 23 anos, alcançando 27 pontos.