Multiplier avec des opérations restreintes

44

Il existe une prime non officielle de 500 représentants pour avoir battu la meilleure réponse actuelle .

Objectif

Votre objectif est de multiplier deux nombres en utilisant seulement un ensemble très limité d'opérations arithmétiques et d'affectation de variables.

  1. Une addition x,y -> x+y
  2. Réciproque x -> 1/x( pas division x,y -> x/y)
  3. Négation x -> -x( pas de soustraction x,y -> x-y, bien que vous puissiez le faire en deux opérations x + (-y))
  4. La constante 1(aucune autre constante n'est autorisée, sauf si elle est produite par les opérations de 1)
  5. Affectation variable [variable] = [expression]

Scoring: Les valeurs commencent par des variables aet b. Votre objectif est de sauvegarder leur produit a*bdans la variable en cutilisant le moins d'opérations possible. Chaque opération et affectation +, -, /, =coûte un point (de manière équivalente, chaque utilisation de (1), (2), (3) ou (4)). Les constantes 1sont gratuites. Le moins de points solution gagne. Tiebreak est le premier post.

Allocation: Votre expression doit être arithmétiquement correcte pour les réels aet "aléatoires" b. Il peut échouer sur un sous - ensemble mesure zéro de R 2 , à savoir un ensemble qui n'a pas de zone si elles sont tracées dans le a- bplan cartésien. (Cela sera probablement nécessaire en raison de la réciproque d'expressions pouvant 0ressembler à 1/a.)

Grammaire:

C'est un . Aucune autre opération ne peut être utilisée. En particulier, cela signifie aucune fonction, condition, boucle ou type de données non numérique. Voici une grammaire pour les opérations autorisées (les possibilités sont séparées par |). Un programme est une séquence de <statement>s, où a <statement>est donné comme suit.

<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

Vous n'avez pas réellement besoin de poster du code dans cette grammaire exacte, tant que ce que vous faites est clair et que le nombre d'opérations est correct. Par exemple, vous pouvez écrire a-bpour a+(-b)et compter comme deux opérations, ou définir des macros par souci de concision.

(Il y avait une question précédente Multiplier sans multiplier , mais cela permettait un ensemble d'opérations beaucoup plus souple.)

Xnor
la source
4
Est-ce seulement possible?
Ypnypn
1
@Ypnypn Oui, et j'ai écrit un exemple pour en être sûr.
xnor
2
Cela ressemble à un défi où une solution optimale est susceptible d'être trouvée (une fois que toute solution a été trouvée). Alors, quel est le bris d'égalité dans ce cas?
Martin Ender
1
@ MartinBüttner Tiebreak est la première publication dans ce cas. Je pense qu'il y a beaucoup de place pour les optimisations, donc je ne pense pas que ce sera une course pour en trouver une qui fonctionne et pour l'écrire proprement. Du moins, c'est ce que j'ai trouvé en l'essayant. peut-être que quelqu'un trouvera une solution clairement minimale.
xnor
2
Ok puisque tout le monde ne pensait pas que ma réponse était aussi drôle que la mienne, je l’ai supprimée et commentée ici: la règle concernant la mesure zéro n’est pas très judicieusement choisie car les nombres rationnels sont une mesure zéro définie pour la mesure de Lebesgue, je suggérerais en utilisant un certain pourcentage à la place. (Ou un autre genre) Mais j'aime vraiment l'idée de ce défi!
Flawr

Réponses:

34

22 opérations

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

Essayez-le en ligne!

Les ops sont 10 additions, 7 inverses, 2 négations et 3 assignations.

Alors, comment j'ai eu ça? J'ai commencé avec le modèle prometteur de la somme de deux fractions à deux étages, un motif qui était apparu lors de nombreuses tentatives précédentes.

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

Lorsque nous limitons la somme à x+y+z+w=0, une belle annulation se produit, donnant:

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

qui contient un produit. (C'est souvent plus facile à obtenir t*u/vque t*uparce que le premier a un degré 1.)

Il y a une manière plus symétrique de penser à cette expression. Avec la restriction x+y+z+w=0, leurs valeurs sont spécifiées par trois paramètres p,q,rde leurs sommes paires.

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

et nous avons c=-q*r/p. La somme pse distingue comme étant dans le dénominateur en correspondant aux paires (x,y)et (z,w)aux variables qui sont dans la même fraction.

Ceci est une belle expression pour cin p,q,r, mais la fraction à deux niveaux est dans x,y,z,w, nous devons donc exprimer le premier en termes de second:

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

Maintenant, nous voulons choisir p,q,rpour que c=-q*r/pégal a*b. Un choix est:

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

Ensuite, les valeurs doublées pour qet rsont commodément divisées par deux dans:

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

Enregistrer en 2tant que variable tet les brancher dans l’équation cdonne une solution à 24 opérations.

#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

Il y a 12 additions, 6 inverses, 4 négations et 2 assignations.

Beaucoup d'opérations sont consacrées à l'expression x,y,z,wen termes de 1,a,b. Pour enregistrer ops, au lieu d' exprimer xdans p,q,r(et donc a,b,1), puis écrire y,z,wen termes de x.

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

Choisir

p = 1
q = a
r = b

et en exprimant cavec une négation comme c=-q*r/p, nous obtenons

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

Malheureusement, diviser par deux xest coûteux. Cela doit être fait en inversant, en ajoutant le résultat à lui-même et en inversant à nouveau. Nous refusons également de produire nxpour -x, puisque c'est ce qui y,z,wsert. Cela nous donne la solution 23-op:

#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

itxest 1 / (2 * x) et nxest -x. Une optimisation finale consistant à exprimer 1/xcomme itx+itxau lieu du modèle 1/(-nx)réduit le caractère et ramène la solution à 22 opérations.

Xnor
la source
Il y a une optimisation facile à 21 opérations. itx + itxse produit deux fois, mais itxne se produit dans aucun autre contexte. Définissez plutôt ix = (1+1)/(1+a+b)et vous remplacez deux ajouts par un.
Peter Taylor
Et en extrayant, m = -1il est possible d'obtenir 20:nx = (1+a+b)/(m+m); c = m/(m/nx + 1/(1+nx)) + m/(1/(a+nx) + 1/(b+nx))
Peter Taylor
3
Ah, ces deux optimisations échouent parce que l'opération prise en charge est réciproque plutôt que division.
Peter Taylor
Si aet bne font qu'un, alors soit, a + nx = 0soit b + nx = 0, ce qui divise votre solution par zéro.
MooseOnTheRocks
1
@MooseOnTheRocks C'est bien, voir la "tolérance" dans le défi que le code peut échouer sur un sous-ensemble de mesure zéro. Je pense que le défi est impossible autrement.
xnor
26

23 opérations

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

preuve par explosion:

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

J'ai abusé de wolfram alpha pour obtenir cette belle image (wolfram alpha a essayé de me faire abonner à pro pour l'enregistrer, mais ensuite ctrl-c ctrl-v ;-)):

score (avec ajout +de soustraction):

z = ////++/++-+/++++-/+/
res = +
fier haskeller
la source
Félicitations pour la solution la plus courte!
xnor
@xnor merci de m'avoir donné ma première réponse acceptée et ma première prime!
fier haskeller
Ne pas être tatillon, mais ne devrait pas ... (b + 1)) - 1 + 1 ... et ... 1)) - (1 / a + ... être ... (b + 1 )) + - 1 + 1 ... et ... 1)) + - (1 / a + ... respectivement?
tfitzger
@tfitzger Je pense que c'est plus facile comme ça. La question dit que cela n'a pas d'importance. Notez que je compte correctement le score (chaque moins est
égal à
Wolfram Alpha dispose d'un essai gratuit de 7 jours, à titre d'information.
ghosts_in_the_code
13

29 opérations

Ne fonctionne pas pour l'ensemble {(a, b) ∈ R 2 | a + b = 0 ou a + b = -1 ou ab = 0 ou ab = -1}. C'est probablement la mesure zéro?

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

La structure de rfc(Reciprocal-Four-C) est plus évidente si nous définissons une macro:

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)

Faisons le calcul:

  • s(x), mathématiquement, est 1/(1/x - 1/(x+1))ce qui est après un peu d'algèbre est x*(x+1)oux*x + x .
  • Lorsque vous inscrivez tout rfc, c'est vraiment 1/((a+b)*(a+b) + a + b - (a-b)*(a-b) - a + b + (-b) + (-b))ce qui est juste 1/((a+b)^2 - (a-b)^2).
  • Après différence de carrés, ou tout simplement expansion, vous obtenez ce qui rfcest 1/(4*a*b).
  • Enfin, cest la réciproque de 4 fois rfc, 1/(4/(4*a*b))devient ainsi a*b.
algorithmeshark
la source
2
+1, j'étais en train de terminer ce calcul identique
Eric Tressler
1
C'est certainement la mesure zéro; c'est une union de lignes.
xnor
Je ne ferai pas de commentaire sur l'union des lignes ... @algorithmshark Pouvez-vous nous en dire plus sur la création de cette identité? Comment avez-vous abordé le problème?
Flawr
1
@flawr J'ai rappelé que les propriétés de s(x)fit correspondre aux exigences de la question, du calcul, ce qui signifiait que j'avais une fonction carrée. Après un certain temps, j'ai trouvé que je pouvais obtenir un a*bterme avec le tour de différence. Une fois que j’ai eu ça, c’était une question d’essayer quelles assignations sauvaient des opérations.
algorithmshark
Étant donné que vous utilisez -1trois fois rfc, ne pouvez-vous pas jouer au golf en l'attribuant à une variable?
isaacg
9

27 opérations

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: =++-

Il n'y a pas de théorie derrière cela. J'ai juste essayé de (const1+a*b)/const2commencer (1/(1-a)+1/(1+b))et avec (-1/a+1/b).


la source
Votre tmpest en fait de 23, ce qui rend votre score de 27. Belle trouvaille, cependant.
algorithmshark