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 ² , à 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 code de code atomique . 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.)

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.

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

29 opérations

Ne fonctionne pas pour l'ensemble {(a, b) ∈ R ² | 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.

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).