Pomnóż z ograniczonymi operacjami

44

Istnieje 500 nieoficjalnych nagród za powtórzenie najlepszej najlepszej odpowiedzi .

Cel

Twoim celem jest pomnożenie dwóch liczb przy użyciu jedynie bardzo ograniczonego zestawu operacji arytmetycznych i przypisywania zmiennych.

  1. Dodanie x,y -> x+y
  2. Wzajemne x -> 1/x( bez podziału x,y -> x/y)
  3. Negacja x -> -x( nie odejmowanie x,y -> x-y, choć można to zrobić jako dwie operacje x + (-y))
  4. Stała 1(niedozwolone są inne stałe, oprócz tych, które zostały wygenerowane przez operacje z 1)
  5. Zmienne przypisanie [variable] = [expression]

Punktacja: wartości zaczynają się od zmiennych ai b. Twoim celem jest zapisanie ich produktu a*bw zmiennej cprzy użyciu jak najmniejszej liczby operacji. Każda operacja i przypisanie +, -, /, =kosztuje punkt (równoważnie, każde użycie (1), (2), (3) lub (4)). Stałe 1są bezpłatne. Wygrywa rozwiązanie o najmniejszej liczbie punktów. Tiebreak jest najwcześniejszym postem.

Dodatek: Twoje wyrażenie musi być poprawne arytmetycznie dla liczb „losowych” ai b. To może nie na środek zera podzbiór R 2 , czyli zestawu, który nie ma obszaru, jeśli wykreślone w a- bkartezjańskiej płaszczyźnie. (Jest to prawdopodobnie potrzebne ze względu na wzajemność wyrażeń, które mogą być 0podobne 1/a).

Gramatyka:

To jest . Żadne inne operacje nie mogą być użyte. W szczególności oznacza to brak funkcji, warunków, pętli lub nienumerycznych typów danych. Oto gramatyka dozwolonych operacji (możliwości są oddzielone |). Program jest sekwencją <statement>s, gdzie a <statement>podaje się następująco.

<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

W rzeczywistości nie musisz pisać kodu w tej dokładnej gramatyce, o ile jest jasne, co robisz, a liczba operacji jest prawidłowa. Na przykład, można napisać a-bdo a+(-b)i liczyć je jako dwie operacje, lub zdefiniować makra dla zwięzłości.

(Było poprzednie pytanie Mnożenie bez mnożenia , ale pozwoliło na znacznie luźniejszy zestaw operacji).

xnor
źródło
4
Czy to w ogóle możliwe?
Ypnypn
1
@Ypnypn Tak, i napisałem przykład, aby się upewnić.
xnor
2
Jest to wyzwanie, w którym można znaleźć optymalne rozwiązanie (po znalezieniu dowolnego rozwiązania). Więc jaki jest w tym przypadku remis?
Martin Ender
1
@ MartinBüttner Tiebreak jest najwcześniejszym postem w tej sprawie. Myślę, że jest sporo miejsca na optymalizacje, więc nie sądzę, że to będzie wyścig, aby znaleźć taki, który działa i napisać go czysto. Przynajmniej tak znalazłem próbując; może ktoś znajdzie wyraźnie minimalne rozwiązanie.
xnor
2
Ok, ponieważ nie wszyscy myśleli, że moja odpowiedź była równie zabawna jak ja, usunąłem ją i skomentowałem tutaj: Reguła dotycząca zestawu miar zerowych nie jest zbyt mądrze wybierana, ponieważ liczby wymierne są zestawem miar zerowych w odniesieniu do miary Lebesgue'a, sugerowałbym używając zamiast tego określonego procentu. (Lub inny rodzaj) Ale podoba mi się pomysł tego wyzwania!
flawr

Odpowiedzi:

34

22 operacje

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

Wypróbuj online!

Operacje to 10 dodatków, 7 odwrotności, 2 negacje i 3 zadania.

Jak więc to dostałem? Zacząłem od obiecującego wzoru sumy dwóch frakcji dwupoziomowych, motywu, który pojawiał się podczas wielu poprzednich prób.

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

Gdy ograniczymy sumę do x+y+z+w=0, nastąpi piękne anulowanie, dając:

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

który zawiera produkt. (Często łatwiej jest je zdobyć t*u/vniż t*uponieważ pierwszy ma stopień 1.)

Istnieje bardziej symetryczny sposób myślenia o tym wyrażeniu. Z ograniczeniem x+y+z+w=0ich wartości są określone przez trzy parametry p,q,rich sum par.

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

a my mamy c=-q*r/p. Suma pjest rozróżniana jako mianownik poprzez odpowiadanie parom (x,y)i (z,w)zmiennym, które są w tej samej części.

To miłe wyrażenie dla cin p,q,r, ale frakcja piętrowa jest w środku, x,y,z,wwięc musimy wyrazić to pierwsze pod względem drugiego:

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

Teraz chcemy wybrać p,q,rtaki, który będzie c=-q*r/prówny a*b. Jednym wyborem jest:

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

Następnie podwojone wartości qi rsą dogodnie zmniejszone o połowę w:

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

Zapisywanie 2jako zmienną ti podłączanie ich do równania cdaje rozwiązanie 24-operacyjne.

#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

Jest 12 dodatków, 6 odwrotności, 4 negacje i 2 zadania.

Wiele OPS są spędzony wyrażając x,y,z,ww kategoriach 1,a,b. Aby zapisać operacje, zamiast tego wyrażaj xw p,q,r(a więc a,b,1), a następnie pisz y,z,ww kategoriach x.

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

Wybieranie

p = 1
q = a
r = b

i wyrażając cz zaprzeczeniem c=-q*r/p, jak otrzymujemy

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

Niestety zmniejszenie o połowę xjest kosztowne. Należy tego dokonać poprzez odwrócenie, dodanie wyniku do siebie i ponowne odwrócenie. Mamy również Negate produkować nxdla -x, ponieważ to właśnie y,z,wstosowanie. To daje nam rozwiązanie 23-operacyjne:

#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

itxwynosi 1 / (2 * x) i nxjest -x. Ostateczna optymalizacja wyrażania 1/xjako itx+itxzamiast szablonów 1/(-nx)wycina postać i sprowadza rozwiązanie do 22 operacji.

xnor
źródło
Łatwa optymalizacja do 21 operacji. itx + itxwystępuje dwa razy, ale itxnie występuje w żadnym innym kontekście. Zdefiniuj zamiast, ix = (1+1)/(1+a+b)a zastąpisz dwa dodatki jednym.
Peter Taylor
A poprzez wyodrębnienie m = -1można uzyskać 20:nx = (1+a+b)/(m+m); c = m/(m/nx + 1/(1+nx)) + m/(1/(a+nx) + 1/(b+nx))
Peter Taylor
3
Ach, obie te optymalizacje kończą się niepowodzeniem, ponieważ obsługiwana operacja jest raczej odwrotna niż podział.
Peter Taylor
Jeśli ai bsą tylko jeden od siebie, to albo, a + nx = 0albo b + nx = 0, powodując podzielenie rozwiązania przez zero.
MooseOnTheRocks
1
@MooseOnTheRocks W porządku, patrz „tolerancja” w wyzwaniu, że kod może zawieść w podzbiorze miary zero. Myślę, że inaczej wyzwanie nie jest możliwe.
xnor
26

23 operacje

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

dowód na wybuch:

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

Wykorzystałem wolfram alpha, aby uzyskać ten piękny obraz (wolfram alpha próbował mnie zmusić do subskrypcji pro, aby go zapisać, ale potem ctrl-c ctrl-v ;-)):

wynik (z dodanym +odejmowaniem):

z = ////++/++-+/++++-/+/
res = +
dumny haskeller
źródło
Gratulujemy najkrótszego rozwiązania!
xnor
@xnor dziękuję za udzielenie pierwszej zaakceptowanej odpowiedzi i mojej pierwszej nagrody!
dumny haskeller
Nie być wybrednym, ale nie powinien ... (b + 1)) - 1 + 1 ... i ... 1)) - (1 / a + ... be ... (b + 1) )) + - 1 + 1 ... i ... 1)) + - (1 / a + ... odpowiednio?
tfitzger
@tfitzger Myślę, że tak jest łatwiej. Pytanie mówi, że to nie ma znaczenia. Uwaga: Liczę poprawnie wynik (każdy minus to dwa)
dumny haskeller
Wolfram Alpha ma 7-dniowy bezpłatny okres próbny, fyi.
ghosts_in_the_code
13

29 operacji

Nie działa dla zestawu {(a, b) ∈ R 2 | a + b = 0 lub a + b = -1 lub ab = 0 lub ab = -1}. Prawdopodobnie to zero.

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

Struktura rfc(Reciprocal-Four-C) jest bardziej widoczna, jeśli zdefiniujemy makro:

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)

Zróbmy matematykę:

  • s(x), matematycznie, to, 1/(1/x - 1/(x+1))co jest po odrobinie algebry, to x*(x+1)lub x*x + x.
  • Kiedy wszystko podporządkujesz rfc, to naprawdę 1/((a+b)*(a+b) + a + b - (a-b)*(a-b) - a + b + (-b) + (-b))jest po prostu 1/((a+b)^2 - (a-b)^2).
  • Po różnicy kwadratów lub po prostu zwykłym rozwinięciu, otrzymujesz rfcto 1/(4*a*b).
  • Wreszcie cjest odwrotność 4 razy rfc, tak się 1/(4/(4*a*b))staje a*b.
algorytmshark
źródło
2
+1, byłem w trakcie dokończenia tego samego obliczenia
Eric Tressler
1
To zdecydowanie miara zera; to połączenie linii.
xnor
Nie będę komentować zjednoczenia linii ... @algorithmshark Czy możesz nam powiedzieć więcej, jak wymyśliłeś tę tożsamość? Jak podszedłeś do problemu?
flawr
1
@ flawr Przypomniałem sobie, że właściwości s(x)pasują do wymagań pytania, z rachunku różniczkowego, więc oznaczało to, że miałem funkcję kwadratową. Po krótkiej przeróbce odkryłem, że mogę znaleźć a*bpojęcie z różnicą podstępu do kwadratu. Kiedy to miałem, chodziło o sprawdzenie, które zadania zapisały operacje.
algorytmshark
Ponieważ używałeś -1trzy razy rfc, czy nie mógłbyś zagrać w golfa, przypisując ją do zmiennej?
isaacg
9

27 operacji

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

Nie kryje się za tym żadna teoria. Właśnie próbowałem zacząć (const1+a*b)/const2i zacząć od (1/(1-a)+1/(1+b))i (-1/a+1/b).


źródło
Masz tmp23 lata, co daje wynik 27. Fajne znalezisko.
algorytmshark