Lipat gandakan dengan operasi terbatas

44

Ada 500 perwakilan hadiah tidak resmi untuk mengalahkan jawaban terbaik saat ini .

Tujuan

Tujuan Anda adalah melipatgandakan dua angka hanya dengan menggunakan rangkaian operasi aritmatika dan penugasan variabel yang sangat terbatas.

  1. Tambahan x,y -> x+y
  2. Timbal balik x -> 1/x( bukan pembagian x,y -> x/y)
  3. Negasi x -> -x( bukan pengurangan x,y -> x-y, meskipun Anda bisa melakukannya sebagai dua operasi x + (-y))
  4. Konstanta 1(tidak ada konstanta lain yang diizinkan, kecuali dihasilkan oleh operasi dari 1)
  5. Tugas variabel [variable] = [expression]

Penilaian: Nilai mulai dalam variabel adan b. Tujuan Anda adalah untuk menyimpan produk mereka a*bke dalam variabel cmenggunakan sesedikit mungkin operasi. Setiap operasi dan penugasan +, -, /, =biaya satu titik (setara, setiap penggunaan (1), (2), (3), atau (4)). Konstanta 1gratis. Solusi poin paling sedikit menang. Tiebreak adalah posting paling awal.

Kelonggaran: Ekspresi Anda harus benar secara aritmatika untuk real "acak" adan b. Hal ini dapat gagal pada subset ukuran nol dari R 2 , yaitu satu set yang tidak memiliki area jika diplot di a- bpesawat Cartesian. (Ini mungkin diperlukan karena kebalikan dari ekspresi yang mungkin 0seperti itu 1/a.)

Tatabahasa:

Ini adalah . Tidak ada operasi lain yang dapat digunakan. Secara khusus, ini berarti tidak ada fungsi, kondisional, loop, atau tipe data non-numerik. Berikut adalah tata bahasa untuk operasi yang diizinkan (kemungkinan dipisahkan oleh |). Suatu program adalah urutan <statement>s, di mana a <statement>diberikan sebagai berikut.

<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

Anda sebenarnya tidak harus memposting kode dalam tata bahasa yang tepat ini, asalkan jelas apa yang Anda lakukan dan jumlah operasi Anda benar. Misalnya, Anda dapat menulis a-buntuk a+(-b)dan menghitungnya sebagai dua operasi, atau mendefinisikan macro untuk singkatnya.

(Ada pertanyaan sebelumnya, Multiply tanpa Multiply , tetapi memungkinkan serangkaian operasi yang lebih longgar.)

Tidak
sumber
4
Apakah ini mungkin?
Ypnypn
1
@Ypnypn Ya, dan saya telah menulis contoh untuk memastikan.
xnor
2
Ini terasa seperti tantangan di mana solusi optimal kemungkinan akan ditemukan (setelah solusi apa pun ditemukan). Jadi apa tie breaker dalam kasus itu?
Martin Ender
1
@ MartinBüttner Tiebreak adalah posting paling awal dalam kasus itu. Saya pikir ada cukup banyak ruang untuk optimisasi, jadi saya tidak berpikir itu hanya akan menjadi perlombaan untuk menemukan yang berfungsi dan menulisnya dengan bersih. Setidaknya, itulah yang saya temukan dalam mencobanya; mungkin seseorang akan menemukan solusi yang jelas minimal.
xnor
2
Ok karena tidak semua orang mengira jawaban saya selucu yang saya lakukan, saya menghapusnya dan berkomentar di sini: Aturan tentang tolok ukur nol tidak dipilih dengan bijak karena bilangan rasional adalah tolok ukur nol untuk ukuran lebesgue, saya sarankan menggunakan persentase tertentu sebagai gantinya. (Atau jenis lain) Tapi saya benar-benar menyukai ide tantangan ini!
flawr

Jawaban:

34

22 operasi

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

Cobalah online!

Ops adalah 10 tambahan, 7 invers, 2 negasi, dan 3 tugas.

Jadi, bagaimana saya mendapatkan ini? Saya mulai dengan template yang tampak menjanjikan dari jumlah dua fraksi bertingkat, sebuah motif yang telah muncul dalam banyak upaya sebelumnya.

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

Ketika kami membatasi jumlah x+y+z+w=0, pembatalan indah terjadi, memberikan:

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

yang mengandung produk. (Seringkali lebih mudah untuk mendapatkan t*u/vdaripada t*ukarena yang pertama memiliki gelar 1.)

Ada cara yang lebih simetris untuk memikirkan ungkapan ini. Dengan pembatasan x+y+z+w=0, nilainya ditentukan oleh tiga parameter p,q,rdari jumlah berpasangannya.

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

dan kami punya c=-q*r/p. Jumlahnya pdibedakan sebagai berada dalam penyebut dengan berkorespondensi dengan pasangan (x,y)dan (z,w)variabel yang berada dalam fraksi yang sama.

Ini adalah ekspresi yang bagus untuk cin p,q,r, tetapi fraksi bertingkat ada di x,y,z,wjadi kita harus mengekspresikan yang pertama dalam hal yang terakhir:

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

Sekarang, kami ingin memilih p,q,ryang c=-q*r/psama a*b. Satu pilihan adalah:

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

Kemudian, nilai yang digandakan untuk qdan dengan rmudah dibagi menjadi dua:

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

Menyimpan 2sebagai variabel tdan memasukkannya ke dalam persamaan untuk cmemberikan solusi 24-op.

#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

Ada 12 tambahan, 6 invers, 4 negasi, dan 2 tugas.

Banyak ops dihabiskan untuk mengekspresikan x,y,z,wdalam hal 1,a,b. Untuk menyimpan ops, sebaliknya ungkapkan xdalam p,q,r(dan dengan demikian a,b,1) lalu tulis y,z,wdalam bentuk x.

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

Memilih

p = 1
q = a
r = b

dan mengekspresikan cdengan negasi seperti yang c=-q*r/pkita dapatkan

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

Sayangnya, mengurangi separuh xbiaya mahal. Itu perlu dilakukan dengan membalik, menambahkan hasilnya ke dirinya sendiri, dan membalikkan lagi. Kami juga meniadakan untuk memproduksi nxuntuk -x, karena itu ini apa y,z,wdigunakan. Ini memberi kita solusi 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

itxadalah 1 / (2 * x) dan nxadalah -x. Optimalisasi akhir dari pengekspresian 1/xsebagai itx+itxganti templated 1/(-nx)memotong karakter dan membawa solusi ke 22 ops.

Tidak
sumber
Ada optimasi mudah untuk 21 operasi. itx + itxterjadi dua kali, tetapi itxtidak terjadi dalam konteks lainnya. Tentukan sebaliknya ix = (1+1)/(1+a+b)dan Anda mengganti dua tambahan dengan satu.
Peter Taylor
Dan dengan mengekstraksi m = -1dimungkinkan untuk mendapatkan 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, kedua optimisasi itu gagal karena operasi yang didukung bersifat timbal balik daripada pembagian.
Peter Taylor
Jika adan bhanya satu yang terpisah, maka salah satu a + nx = 0atau b + nx = 0, menyebabkan solusi Anda membaginya dengan nol.
MooseOnTheRocks
1
@ MooseOnTheRocks Tidak apa-apa, lihat "uang saku" dalam tantangan bahwa kode dapat gagal pada subset ukuran-nol. Saya pikir tantangannya adalah mustahil.
xnor
26

23 operasi

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

bukti oleh ledakan:

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

Saya menyalahgunakan wolfram alpha untuk mendapatkan gambar yang indah ini (wolfram alpha mencoba membuat saya berlangganan ke pro untuk menyimpannya, tetapi kemudian ctrl-c ctrl-v ;-)):

skor (dengan ditambahkan +pada pengurangan):

z = ////++/++-+/++++-/+/
res = +
haskeller bangga
sumber
Selamat atas solusi terpendek!
xnor
@xnor, terima kasih telah memberikan jawaban pertama yang diterima dan hadiah pertama saya!
haskeller bangga
Bukan untuk menjadi rewel, tetapi seharusnya tidak ... (b + 1)) - 1 + 1 ... dan ... 1)) - (1 / a + ... menjadi ... (b + 1 )) + - 1 + 1 ... dan ... 1)) + - (masing-masing 1 / a + ...?
tfitzger
@ tfitzger Saya pikir lebih mudah seperti itu. Pertanyaannya memang mengatakan bahwa itu tidak masalah. Catatan saya menghitung skor dengan benar (Setiap minus adalah dua)
haskeller bangga
Wolfram Alpha memiliki uji coba 7 hari gratis, fyi.
ghosts_in_the_code
13

29 operasi

Tidak berfungsi untuk set {(a, b) ∈ R 2 | a + b = 0 atau a + b = -1 atau ab = 0 atau ab = -1}. Itu mungkin berukuran nol?

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

Struktur rfc(Reciprocal-Four-C) lebih jelas jika kita mendefinisikan 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)

Mari kita berhitung:

  • s(x), secara matematis, adalah 1/(1/x - 1/(x+1))setelah sedikit aljabar x*(x+1)atau x*x + x.
  • Ketika Anda memasukkan semuanya ke dalam rfc, itu benar-benar 1/((a+b)*(a+b) + a + b - (a-b)*(a-b) - a + b + (-b) + (-b))yang adil 1/((a+b)^2 - (a-b)^2).
  • Setelah perbedaan kotak, atau hanya ekspansi polos, Anda mendapatkan bahwa rfcadalah 1/(4*a*b).
  • Akhirnya, cadalah kebalikan dari 4 kali rfc, jadi 1/(4/(4*a*b))menjadi a*b.
algoritme hiu
sumber
2
+1, saya sedang menyelesaikan perhitungan yang identik ini
Eric Tressler
1
Itu pasti mengukur nol; itu adalah penyatuan garis.
xnor
Tidak akan berkomentar tentang penyatuan garis ... @algorithmshark Bisakah Anda memberi tahu kami lebih lanjut bagaimana Anda bisa menemukan identitas ini? Bagaimana Anda mengatasi masalah?
flawr
1
@ flawr Saya ingat bahwa sifat-sifat s(x)cocok dengan persyaratan pertanyaan, dari kalkulus, jadi itu berarti saya memiliki fungsi persegi. Setelah beberapa faffing tentang, saya menemukan saya bisa mendapatkan a*bistilah dengan perbedaan trik kuadrat. Setelah saya memilikinya, itu soal mencoba tugas mana yang menyelamatkan operasi.
algorithmshark
Karena Anda menggunakan -1tiga kali dalam rfc, tidak bisakah Anda bermain karakter dengan menetapkannya ke variabel?
isaacg
9

27 operasi

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

Tidak ada teori di balik ini. Aku hanya mencoba untuk mendapatkan (const1+a*b)/const2dan mulai dengan (1/(1-a)+1/(1+b))dan (-1/a+1/b).


sumber
Anda tmpsebenarnya 23, membuat skor Anda 27. Namun, senang menemukan.
algorithmshark