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
code-golf
math
restricted-source
Thomas O
sumber
sumber
Jawaban:
C,
848378 KarakterDalam bentuk yang lebih mudah dibaca
Algoritma ini lebih dikenal sebagai Multiplikasi Ethiopia atau Perkalian Petani Rusia. Berikut algoritmanya:
sumber
m=0
(minimal bagi saya)for(;(a&1&&m+=b)|a;a>>=1,b<<=1);
Ya, saya sangat malu. :)for(m=0;(a&1&&m+=b)|a;a/=2,b*=2);
mengapa menggunakan shift, kan?b+=b
bukanb*=2
. Tentu saja, Anda masih harus bergeser dengan benar.APL (5)
Mengambil input pada input standar yang dipisahkan oleh baris baru.
sumber
Golfscript - 12 karakter
Harap dicatat bahwa di
*
sini bukan operator perkalian, ini bukan operator pengulangan, lihat penggunaan kedua di sini .sumber
Golfscript - 27 karakter
Penggandaan petani. Ada * pertama di sana adalah kalikan, tetapi hanya dengan 0 atau 1
Di sini, pada 31 karakter yang tidak berlipat ganda sama sekali
sumber
Python, 64 karakter
Mungkin bukan yang paling efisien (atau yang paling sesuai, tapi saya "menambahkan", bukan?):
sumber
input()
di tempatint(raw_input())
untuk menyimpan 18 karakter. Anda mungkin menganggap kecurangan ini, tetapiprint sum([input()]*input())
juga berfungsi (*
digunakan untuk pengulangan, bukan multiplikasi).r=input;a=r();print sum(map(lambda x:a,range(r())))
jauh lebih pendekr=input;a=r();r(sum(a for b in range(r())))
bahkan lebih pendek (43 vs 51 byte)Ruby, 30
Berdasarkan jawaban GigaWat .
sumber
Golfscript - 43
Implementasi multiplikasi petani . Saya pikir saya mungkin bisa bermain golf lagi nanti.
sumber
J,
1817 karakterInput harus dipisahkan dengan ruang.
sumber
Python, juga 64 karakter
sumber
i=input
dan menggunakani()
0 if n==0 else
dengann and
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.Versi yang lebih panjang ini ( 103 karakter ) akan memastikan ini berjalan dengan lebih cepat dari dua pengaturan yang mungkin:
sumber
To
dan dalam penggabungan, serta dengan keluaran ke jendela langsung VBE viaDebug.?
Perl: 52 karakter
Ini adalah pertanyaan lama, tetapi Perl perlu diwakili:
(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.
sumber
Variasi dalam Scala, dioptimalkan untuk ukuran: 48 karakter
dioptimalkan untuk kecepatan sedikit:
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:
sumber
K,
1816.
sumber
Ruby, 35 karakter
p $*.map!(&:to_i).pop*$*.inject(:+)
Ini adalah program , yang mengambil input dan output, bukan hanya fungsi.
sumber
Ruby, 35 byte
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.
sumber
Mathematica 12
Berikut ini jumlah
#2
instance dari#1
.Kode
Pemakaian
9 karakter?
Jika parameter Program,
a
,b
, dapat digunakan untuk input, hasil yang sama dapat dicapai dengan 9 karakter .sumber
VB11, 101 Chars
sumber
==
) tidak diizinkan oleh pertanyaan, tetapi banyak jawaban yang menggunakannya.