Lipat gandakan [tutup]

8

Tulis algoritma perkalian tercepat (terbaik-O besar) dan terkecil untuk bilangan bulat positif, tanpa menggunakan operator perkalian. Anda hanya diperbolehkan penambahan, pengurangan, fungsi logis (DAN, ATAU, XOR, BUKAN), bit shift, bit rotate, bit flip / set / clear dan bit test. Program Anda harus mampu mengalikan angka 16-bit untuk menghasilkan hasil 32-bit. Ambil input pada stdin, dipisahkan dengan koma, spasi atau baris baru (pilihan Anda), tetapi jelaskan bagaimana cara memasukkan data.

Contoh input / output:

734 929
681886
Thomas O
sumber
1
Bagaimana dengan operator divisi?
st0le
3
Apakah codegolf ini atau tantangan? : - \
st0le
4
Tercepat ATAU kecil - Anda tidak dapat memiliki keduanya, atau Anda memerlukan formulasi terjemahan untuk menghitung trade off.
pengguna tidak diketahui
3
Saya menandai untuk menutup sebagai "bukan pertanyaan nyata", karena masih belum ada solusi, bagaimana membandingkan kode tercepat dan terpendek. Yang mana prioritas? Atau dalam hubungan apa trade off? Ini dapat disembuhkan jika beberapa perbandingan algo dalam bahasa portabel diberikan - misalnya: jika std-algo mencapai 500k operasi di C, dan algo Anda mencapai 50k, Anda harus melipatgandakan panjang kode * 10. Dengan cara itu semua orang dapat memilih apakah akan mempersingkat kode atau membuatnya lebih cepat. Pemenang tidak harus menjadi pemenang di kedua kategori, tetapi kriteria yang menang akan jauh lebih objektif.
pengguna tidak diketahui
2
Pertanyaan ini gila seperti yang dinyatakan. Algoritma multiplikasi yang asymptotically paling cepat diketahui untuk bilangan bulat positif adalah algoritma Fürer ( en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm ) dan sangat rumit dan akan membutuhkan ribuan baris untuk diimplementasikan dalam bahasa apa pun. Saya berasumsi dia sebenarnya hanya berarti algoritma Anda harus O (n ^ 2) (perkalian panjang).
D Coetzee

Jawaban:

11

C, 84 83 78 Karakter

m;main(a,b){for(scanf("%d%d",&a,&b);a;b+=b)a&1?m+=b:0,a>>=1;printf("%d\n",m);}

Dalam bentuk yang lebih mudah dibaca

m;main(a,b)
{
    scanf("%d%d",&a,&b);
    while (a)
    {
        if (a&1)
           m+=b;
        a>>=1;
        b+=b;
    }
    printf("%d\n",m);
}

Algoritma ini lebih dikenal sebagai Multiplikasi Ethiopia atau Perkalian Petani Rusia. Berikut algoritmanya:

  1. Biarkan dua angka yang akan dikalikan menjadi a dan b.
  2. Jika a nol maka hancurkan dan cetak hasilnya.
  3. Jika a aneh maka tambahkan b ke hasilnya.
  4. Setengah, Ganda b. Goto Langkah 2.
fR0DDY
sumber
tidak bekerja tanpa menginisialisasi m=0(minimal bagi saya)
st0le
@ st0le Ini akan berfungsi sekarang, saya telah memindahkan 'm' untuk memulai di fungsi utama. Lihat di sini: ideone.com/XCz8C
fR0DDY
Lupa tentang yang ini, ini yang lebih pendek for(;(a&1&&m+=b)|a;a>>=1,b<<=1);Ya, saya sangat malu. :)
st0le
for(m=0;(a&1&&m+=b)|a;a/=2,b*=2);mengapa menggunakan shift, kan?
st0le
2
@ fR0DDY: Bisa dibilang b+=bbukan b*=2. Tentu saja, Anda masih harus bergeser dengan benar.
Joey Adams
7

APL (5)

Mengambil input pada input standar yang dipisahkan oleh baris baru.

+/⎕⍴⎕
marinus
sumber
5

Golfscript - 12 karakter

~0\{1$+}*\;

Harap dicatat bahwa di *sini bukan operator perkalian, ini bukan operator pengulangan, lihat penggunaan kedua di sini .

Juan
sumber
4

Golfscript - 27 karakter

Penggandaan petani. Ada * pertama di sana adalah kalikan, tetapi hanya dengan 0 atau 1

~2base-1%{1&\..+\@*}%{+}*\;

Di sini, pada 31 karakter yang tidak berlipat ganda sama sekali

~2base-1%{1&\..+\[0\]@=}%{+}*\;
gnibbler
sumber
4

Python, 64 karakter

Mungkin bukan yang paling efisien (atau yang paling sesuai, tapi saya "menambahkan", bukan?):

a=int(raw_input())
print sum(a for i in range(int(raw_input())))
Taylor Scott
sumber
7
Anda bisa menggunakan input()di tempat int(raw_input())untuk menyimpan 18 karakter. Anda mungkin menganggap kecurangan ini, tetapi print sum([input()]*input())juga berfungsi ( *digunakan untuk pengulangan, bukan multiplikasi).
James
r=input;a=r();print sum(map(lambda x:a,range(r())))jauh lebih pendek
Joel Cornett
@ JoelCornett r=input;a=r();r(sum(a for b in range(r())))bahkan lebih pendek (43 vs 51 byte)
FatalError
3

Ruby, 30

->(a){Array.new(*a).inject:+}

Berdasarkan jawaban GigaWat .

Hauleth
sumber
2

Golfscript - 43

~\:@;0 1{.3$&{\@+\}{}if@@+:@;.+.3$>!}do;\;

Implementasi multiplikasi petani . Saya pikir saya mungkin bisa bermain golf lagi nanti.

Juan
sumber
2

J, 18 17 karakter

+/({.${:)".1!:1]3

Input harus dipisahkan dengan ruang.

Gareth
sumber
2

Python, juga 64 karakter

m=lambda x,n:0 if n==0 else x+m(x,n-1);print m(input(),input())
Doug T.
sumber
1
Anda dapat mempersingkatnya dengan menetapkan i=inputdan menggunakani()
st0le
3
sebenarnya yang berhasil menjadi jumlah karakter yang persis sama
Doug T.
2
bisa ganti 0 if n==0 elsedengann and
rekursif
1

VBA, 70 karakter

Ini sebenarnya cukup lambat untuk jumlah besar, tetapi kecil. Saya berhasil meningkatkan ukuran kode sambil meningkatkan kecepatan. Waktu perhitungan bervariasi, tergantung pada posisi argumen - bukan hanya ukuran. (Yaitu 1000, 5000 menghitung dalam waktu sekitar 4 detik sementara 5000, 1000 menghitung dalam waktu sekitar 19). Karena OP mendaftar cepat dan kecil, saya pikir saya akan memilih yang ini. Input adalah dua arg numerik, dipisahkan koma.

Sub i(j,k)
For m=1 To j:n=n & String(k," "):Next
MsgBox Len(n)
End Sub

Versi yang lebih panjang ini ( 103 karakter ) akan memastikan ini berjalan dengan lebih cepat dari dua pengaturan yang mungkin:

Sub i(j,k)
If j<k Then a=j:b=k Else b=j:a=k
For m=1 To a:n=n & String(b," "):Next
MsgBox Len(n)
End Sub
Gaffi
sumber
Anda dapat kehilangan beberapa byte dengan menghapus spasi putih sebelum Todan dalam penggabungan, serta dengan keluaran ke jendela langsung VBE viaDebug.?
Taylor Scott
1

Perl: 52 karakter

Ini adalah pertanyaan lama, tetapi Perl perlu diwakili:

perl -pl '($m,$n,$_)=split;$_+=$m&1&&$n,$m>>=1,$n<<=1while$m'

(Ini adalah algoritma binary; Selain iterasi lebih kecil tetapi cara terlalu membosankan.)

Program ini mencakup fitur yang tidak disengaja: jika baris input Anda berisi angka ketiga, program akan benar-benar menghitung A * B + C.

kotak roti
sumber
Seberapa cepat?
pengguna tidak dikenal
Ini berjalan di O (log n), secara alami. Apakah Anda bertanya tentang kecepatan aktualnya? Di komputer saya, saya mengukur kira-kira 2-3 kali lebih lambat dari yang dikalikan Perl, tetapi saya tidak tahu seberapa penting itu.
kotak roti
1

Variasi dalam Scala, dioptimalkan untuk ukuran: 48 karakter

def m(a:Int,b:Int):Int=if(b==1)a else a+m(a,b-1)

dioptimalkan untuk kecepatan sedikit:

def mul (a:Int, b:Int) : Int = {
  print (".")
  if (a == 1) b
  else if (a > b) mul (b, a)
  else if (a % 2 == 0) mul (a >> 1, b << 1) 
  else b + mul (a - 1, b) 
}

Saya menukar (a, b) jika (a> b), untuk mencapai tujuan lebih cepat. Perbedaannya adalah 11 hingga 20 langkah, saat memanggil mul (1023,31), dibandingkan dengan menghilangkan baris kode itu.

golf: 95 karakter:

def m(a:Int,b:Int):Int=if(a==1)b
else if(a>b)m(b,a)
else if(a%2==0)m(a>>1,b<<1)
else b+m(a-1,b)
Pengguna tidak diketahui
sumber
1

K, 18 16

{#,/(!y),\:/:!x}

.

k){#,/(!y),\:/:!x}[4;20]
80
k){#,/(!y),\:/:!x}[13;21]
273
k){#,/(!y),\:/:!x}[3;6]
18
tmartin
sumber
1

Ruby, 35 karakter

p $*.map!(&:to_i).pop*$*.inject(:+)

Ini adalah program , yang mengambil input dan output, bukan hanya fungsi.

.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> wc -c golf.rb         
35 golf.rb
.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> ruby ./golf.rb 734 929
681886
defhlt
sumber
1

Ruby, 35 byte

def x(a)Array.new(*a).inject :+end

Pemakaian: x([123, 456]) #=> 56088

Mungkin bisa dipersingkat jika angka-angka dibaca dari ARGV, tetapi mengeluh tentang mereka menjadi format yang salah (string, bukan int). Setiap saran akan sangat bagus.

Tuan Llama
sumber
0

Mathematica 12

Berikut ini jumlah #2instance dari #1.

Kode

#1~Sum~{#2}&

Pemakaian

#1~Sum~{#2} &[734, 929]

(* out *)

681886


9 karakter?

Jika parameter Program, a, b, dapat digunakan untuk input, hasil yang sama dapat dicapai dengan 9 karakter .

a~Sum~{b}
DavidC
sumber
0

VB11, 101 Chars

   Dim m As Func(Of Integer, Integer, Integer, Integer) = Function(a, b, t) If(a = 0, t, m(a >> 1, b << 1, t + If(a Mod 2 = 1, b, 0)))
Adam Speight
sumber
1
Anda menggunakan beberapa operasi yang tidak diizinkan ...
Gaffi
Saya tidak berpikir ini menggunakan operasi yang dilarang (kecuali aliran kontrol tidak diizinkan; pertanyaannya tidak jelas tentang itu, yang merupakan bagian dari alasan itu ditahan). "mod 2" adalah operasi uji bit. Saya kira perbandingan ( ==) tidak diizinkan oleh pertanyaan, tetapi banyak jawaban yang menggunakannya.