Di tengah banyaknya tantangan saya pikir ini mungkin menarik.
Dalam tantangan ini, kita akan menggunakan Residue Number System (RNS) untuk melakukan penambahan, pengurangan, dan penggandaan pada bilangan bulat besar.
Apa itu RNS?
RNS adalah salah satu dari banyak cara yang telah dikembangkan orang untuk mengidentifikasi bilangan bulat. Dalam sistem ini, angka diwakili oleh urutan residu (yang merupakan hasil setelah operasi modulus (yaitu sisa setelah pembagian bilangan bulat)). Dalam sistem ini, setiap integer memiliki banyak representasi. Untuk menjaga hal-hal sederhana, kita akan membatasi hal-hal sehingga setiap bilangan bulat diwakili secara unik. Saya pikir lebih mudah menggambarkan apa yang terjadi dengan contoh nyata.
Mari kita lihat tiga bilangan prima pertama: 2, 3, 5. Dalam sistem RNS, kita dapat menggunakan ketiga bilangan ini untuk secara unik mewakili bilangan apa pun yang kurang dari 2 * 3 * 5 = 30 menggunakan residu. Ambil 21:
21 kurang dari 30, jadi kita dapat mewakilinya menggunakan hasil setelah modding dengan 2, 3, dan 5. (yaitu sisanya setelah integer membaginya dengan 2, 3, dan 5)
Kami akan mengidentifikasi 21 dengan urutan bilangan bulat berikut:
21 ~ {21 mod 2, 21 mod 3, 21 mod 5} = {1, 0, 1}
Jadi dalam sistem RNS kami, alih-alih "21", kami akan menggunakan {1,0,1}.
Secara umum diberi bilangan bulat n , kami mewakili n sebagai { n mod 2, ..., n mod p_k } di mana p_k adalah bilangan terkecil sehingga n lebih kecil dari produk semua bilangan prima kurang dari atau sama dengan p_k .
Contoh lain, katakanlah kita memiliki 3412. Kita perlu menggunakan 2,3,5,7,11,13 di sini karena 2*3*5*7*11*13=30030
sedangkan, 2*3*5*7*11=2310
yang terlalu kecil.
3412 ~ {3412 mod 2, 3412 mod 3, 3412, mod 5, ..., 3412 mod 13} = {0, 1, 2, 3, 2, 6}
Anda perhatikan bahwa dengan menggunakan sistem ini kami dapat mewakili jumlah yang sangat besar secara relatif tanpa rasa sakit. Dengan menggunakan residu {1, 2, 3, 4, 5, 6, 7, 8,}, kita dapat merepresentasikan angka hingga {2, 6, 30, 210, 2310, 30030, 510510, 9699690 ...} masing-masing. ( Ini adalah seri )
Tugas kita
Kami akan menggunakan residu ini untuk melakukan +, -, dan * dalam jumlah besar. Saya akan menjelaskan proses-proses di bawah ini. Untuk saat ini di sini adalah spesifikasi input dan output.
Memasukkan
Anda akan diberikan dua angka (berpotensi sangat besar) melalui argumen stdin atau fungsi. Mereka akan diberikan sebagai string basis 10 digit.
Untuk keperluan menguraikan masalah lebih lanjut, kami memanggil input pertama n
dan kedua m
. Asumsikan n> m> = 0 .
Anda juga akan diberikan +
atau -
atau *
untuk menunjukkan operasi untuk melakukan.
Keluaran
Biarkan x menjadi bilangan bulat. Kami akan menggunakan [ x ] untuk merujuk ke representasi RNS yang dijelaskan di atas x .
Anda akan menghasilkan [n] <operator> [m] = [result]
Cara melakukan operasi di RNS
Operasi ini relatif sederhana. Diberi dua angka dalam notasi RNS, untuk menambah, mengurangi, atau mengalikannya, cukup lakukan operasi komponen yang diberikan dengan bijaksana dan kemudian ambil modulus.
yaitu
{1, 2, 3} + {1, 1, 4} = {(1 + 1) mod 2, (2 + 1) mod 3, (3 + 4) mod 5} = {0, 0, 2}
Perhatikan bahwa jika jumlah residu yang digunakan untuk mewakili dua angka berbeda tidak sama, saat melakukan operasi, Anda perlu memperpanjang angka "lebih pendek" sehingga memiliki jumlah residu yang sama. Ini mengikuti proses yang sama. Lihat contoh uji untuk contoh.
Hal yang sama berlaku jika hasilnya membutuhkan lebih banyak residu daripada input. Maka kedua input harus "diperluas".
Detail Penting
Kita akan berhadapan dengan angka-angka besar di sini, tetapi tidak dengan sembarangan besar. Kami akan bertanggung jawab untuk nomor hingga produk dari 100 bilangan prima pertama (lihat di bawah). Untuk tujuan ini, Anda diberikan 100 bilangan prima pertama secara gratis (tanpa biaya byte) . Anda dapat menempelkannya dalam array yang disebut
p
atau sesuatu yang idiomatis untuk bahasa Anda dan kemudian kurangi jumlah byte yang digunakan untuk memulai array ini dari total akhir Anda. Ini tentu saja berarti bahwa mereka mungkin hard-coded atau Anda dapat menggunakan built-in untuk membuatnya.Jika karena alasan tertentu ini adalah representasi integer default yang digunakan dalam bahasa Anda. Ini baik saja.
Anda tidak boleh menggunakan tipe Integer Presisi Sewenang-wenang kecuali itu adalah bahasa default Anda. Jika itu adalah default, Anda mungkin tidak menggunakannya untuk menyimpan bilangan bulat yang biasanya tidak muat dalam 64 bit.
Agar jelas, setiap bilangan bulat akan selalu diwakili dengan residu sesedikit mungkin. Ini berlaku untuk input dan output.
Saya pikir spesifikasi lain harus mencegah hal ini, tetapi menjadi berlebihan: Anda mungkin tidak melakukan operasi yang diberikan pada input dan kemudian mengubah segalanya menjadi RNS dan kemudian output. Anda harus mengubah input ke RNS dan kemudian melakukan operasi untuk menghasilkan output.
Uji Kasus
Memasukkan:
n = 10
m = 4
+
Keluaran:
{ 0, 1, 0 } + { 0, 1 } = { 0, 2, 4 }
Penjelasan:
Pertama, ubah setiap angka menjadi representasi RNS seperti dijelaskan di atas:
10 ~ {0,1,0}
dan 4 ~ {0,1}
. Perhatikan bahwa ketika kita ingin melakukan penambahan komponen, itu 10
memiliki lebih banyak komponen daripada 4
. Karena itu kita harus "memperpanjang" angka yang lebih pendek. Jadi kita akan menulis secara singkat 4 ~ {0,1} --> {0,1, 4 mod 5} = {0,1,4}
. Sekarang kita lanjutkan dengan penambahan dan kemudian mengambil modulus.
- Memasukkan
n=28
m=18
+
Keluaran:
[ 0, 1, 3 ] + [0, 0, 3 ] = [ 0, 1, 1, 4 ]
- Input (saya menumbuk wajah saya di keyboard)
n=1231725471982371298419823012819231982571923
m=1288488183
*
Keluaran (dipisah menjadi baris terpisah untuk dibaca):
[1, 2, 3, 6, 2, 10, 2, 1, 12, 16, 7, 15, 34, 29, 31, 5, 55, 32, 66, 61, 3, 76, 52, 14, 65, 44, 99, 57 ]
*
[1, 0, 3, 3, 4, 8, 9, 10, 8, 0 ]
=
[1, 0, 4, 4, 8, 2, 1, 10, 4, 0, 17, 7, 27, 21, 44, 51, 56, 9, 6, 9, 12, 0, 52, 36, 43, 68, 99, 24, 96, 39, 96, 66, 125]
n
membutuhkan 28 bilangan prima. m
membutuhkan 10. n*m
membutuhkan 33.
- Memasukkan
n=8709668761379269784034173446876636639594408083936553641753483991897255703964943107588335040121154680170867105541177741204814011615930342030904704147856733048115934632145172739949220591246493529224396454328521288726490
m=1699412683745170450115957274739962577420086093042490863793456500767137147999161679589295549397604032154933975242548831536518655879433595016
-
Keluaran:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 509]
-
[0, 2, 1, 6, 1, 12, 11, 18, 14, 28, 21, 36, 37, 42, 16, 52, 41, 60, 16, 70, 49, 78, 80, 88, 49, 100, 13, 106, 4, 112, 68, 130, 36, 138, 37, 150, 0, 162, 8, 172, 163, 180, 18, 192, 129, 198, 135, 222, 78, 228, 90, 238, 57, 250, 36, 262, 87, 270, 206, 280, 193, 292, 253, 310, 224, 316, 57, 336, 48, 348]
=
[0, 1, 4, 1, 10, 1, 6, 1, 9, 1, 10, 1, 4, 1, 31, 1, 18, 1, 51, 1, 24, 1, 3, 1, 48, 1, 90, 1, 105, 1, 59, 1, 101, 1, 112, 1, 0, 1, 159, 1, 16, 1, 173, 1, 68, 1, 76, 1, 149, 1, 143, 1, 184, 1, 221, 1, 182, 1, 71, 1, 90, 1, 54, 1, 89, 1, 274, 1, 299, 1, 266, 1, 228, 1, 340, 1, 170, 1, 107, 1, 340, 1, 88, 1, 157, 1, 143, 1, 22, 1, 22, 1, 58, 1, 296, 1, 371, 1, 140]
n
menggunakan 100 bilangan prima. m
menggunakan 70 bilangan prima. n-m
menggunakan 99 bilangan prima.
Saya memeriksa ini menggunakan ChineseRem
implementasi built-in teorema Remainder Cina pada GAP (yang pada dasarnya mengambil angka RNS dan mengubahnya ke basis 10 integer). Saya percaya mereka benar. Jika ada sesuatu yang mencurigakan, tolong beri tahu saya.
Bagi mereka yang peduli, produk dari 100 bilangan prima pertama adalah:
471193079990618495316248783476026042202057477340967552018863483961641533584503
422120528925670554468197243910409777715799180438028421831503871944494399049257
9030720635990538452312528339864352999310398481791730017201031090
Angka ini 1 lebih besar dari angka maksimal yang dapat kami wakili menggunakan sistem yang diberikan (dan 100 batasan utama).
(a,b,o)=>a.map((v,i)=>eval(v+o+b[i]))
di ES6 misalnya. Saya pikir bagian tersulit mungkin menemukan jumlah bilangan prima yang diperlukan untuk mewakili hasil tanpa menggunakan aritmatika presisi sewenang-wenang, meskipun konversi berikutnya ke RNS tidak sepenuhnya sepele.1234,1234,+
)?Jawaban:
CELAH
Beberapa Latar Belakang: Saya akan mengakui bahwa ketika saya membuat pertanyaan ini, berbulan-bulan yang lalu, saya tidak memiliki metode untuk menyelesaikan bagian sulit dari pertanyaan ini: menentukan jumlah bilangan prima yang tepat untuk digunakan. Kami memiliki banyak orang yang sangat cerdas di situs ini, dan saya benar-benar berharap seseorang akan menemukan cara untuk melakukannya dengan cukup cepat. Namun, karena ini tidak terjadi, saya bahkan tidak yakin bahwa itu benar-benar mungkin untuk menyelesaikan masalah ini. Jadi, saya harus meluangkan waktu untuk menyusun metode. Saya percaya bahwa apa yang telah saya lakukan tidak melanggar aturan dalam tantangan ini, tentu saja saya ingin ini diperiksa kebenarannya.
Saya juga sedikit menyesali pilihan kode-golf karena solusinya sedikit lebih dalam daripada yang biasanya cocok dengan format tag. Setelah mengatakan ini, untuk mengikuti aturan situs, ada versi "golf" dari solusi saya di bagian bawah posting ini.
Kode
Penjelasan:
Untuk memulai, kami menghitung semua 100 residu untuk kedua input. Kami melakukan ini dengan
modulus
fungsi dalam kode. Saya mencoba berhati-hati agar kami menggunakanmod
fungsi bawaan setelah setiap langkah. Ini memastikan bahwa kita tidak pernah memiliki angka yang lebih besar dari540^2
, yaitu 1 kurang dari kuadrat ke-100.Setelah kita memiliki semua residu, kita dapat melakukan operasi yang diberikan dan
mod
setiap entri lagi. Sekarang kita memiliki designator yang unik untuk hasilnya, tetapi kita perlu menentukan jumlah minimal entri yang harus kita gunakan untuk mewakili hasil dan masing-masing input.Mencari tahu berapa banyak residu yang sebenarnya kita butuhkan adalah bagian tersulit dari masalah ini. Untuk menentukan ini, kami melakukan sebagian besar langkah Teorema Sisa Cina (CRT). Namun, kami jelas harus melakukan modifikasi agar tidak berakhir dengan angka yang terlalu besar.
Biarkan
prod(i)
menjadi jumlahi-1
bilangan prima pertama . Sebagai contoh,Membiarkan
X
menjadi bilangan bulat. Membiarkan{r_i}
menjadi residuX
, yaituDi mana
p_i
adalahi
perdana th. Ini untuk1<i<=100
kasus kami.Sekarang kita akan menggunakan CRT untuk menemukan urutan
{u_i}
sehingga jumlahi
dariprod(i) * u_i
sama denganX
. Perhatikan bahwa masing-masingu_i
secara teknis juga merupakan residu, sepertiu_i < p_i
. Selanjutnya, jikaX < prod(i)
demikianu_i = 0
. Ini sangat penting. Ini berarti bahwa dengan memeriksa nol jejak, kita dapat menentukan berapa banyak residu yangr_i
sebenarnya perlu kita wakiliX
dalam RNS.Jika Anda ingin memeriksa beberapa urutan
u_i
,partial_chinese
fungsi mengembalikanu_i
urutan.Dengan bermain-main dengan CRT, saya dapat menemukan formula rekursif untuk
u_i
nilai - nilai, memecahkan masalah menentukan berapa banyak residu yang kita butuhkan.Rumusnya adalah:
Di mana
SUM
jumlahj in [1,i)
dariu_j * prod(i)
.Tentu saja,
prod(i)
dalam beberapa kasus tidak dapat benar-benar dihitung karena terlalu besar. Untuk tujuan ini, saya menggunakanphi_i
fungsinya. Fungsi ini kembaliprod(j) (mod p_i)
. Itu adamod
di setiap langkah, jadi kami tidak pernah benar-benar menghitung apa pun yang terlalu besar.Jika Anda penasaran dari mana rumus ini berasal, saya akan merekomendasikan bekerja beberapa contoh CRT, yang dapat ditemukan di halaman wikipedia .
Akhirnya, untuk setiap input serta output kami, kami menghitung
u_i
urutan dan kemudian menentukan nol yang tertinggal. Kemudian kami membuang banyakr_i
dari ujung urutan residu."Golfed" Code, 2621 bytes
sumber
Mathematica, bukan golf
Fungsi
rns[d_,l_]
mengubah bilangan bulat basis-10d
menjadi bilangan bulat RNSl
.Fungsi
plus
/times
/subtract
tambahkan / gandakan / kurangi satu bilangan bulat RNS ke / dari yang lain, yang keduanya memiliki panjang yang sama.Fungsi
mag[f_]
mengestimasi besarnya perkiraan angka floating pointf
dalam hal batas bawah dari panjang representasi RNS-nya.Fungsi
ext[m_,n_,i_]
menemukan sisa dari pembagian produk olehm
dan .Prime[Range@n]
Prime[i]
Function
multi[e_,p_,t_]
memberikan multiplier terkecil yangm
memuaskan ituDivisible[m*e+t,p]
Fungsi
appx[d_]
mengambil6
digit pertama dari bilangan bulat desimal dan memberikan nilai titik apung perkiraannya.Dengan bantuan fungsi-fungsi di atas, sekarang kami dapat memecahkan masalah yang rumit - untuk menentukan panjang hasilnya .
Pertama, saya harus mengklarifikasi bahwa itu bukan tugas yang mudah untuk menentukan panjang RNS integer. Untuk bilangan bulat kecil, kita dapat membandingkannya langsung dengan produk bilangan prima. Tetapi untuk bilangan bulat yang sangat besar, karena dilarang untuk menghitung produk bilangan prima yang sangat akurat, perbandingan seperti itu tidak lagi berfungsi.
Sebagai contoh, mengingat bahwa produk perdana
1
untuk30
adalah3.16*10^46
, panjang RNS bilangan bulat sekitar3.16*10^46
mungkin menjadi29
atau30
. Fungsimag
akan memberikan29
sebagai referensi untuk bilangan bulat ini, menunjukkan bahwa keduanya29
dan30
mungkin.Setelah mengetahui besarnya, kami hanya mewakili bilangan bulat sesuai dengan besarnya itu secara langsung, berharap untuk menghitung panjang sebenarnya. Kuncinya di sini adalah menambahkan beberapa nomor baru ke nomor asli dan memodifikasi representasi RNS-nya, sampai representasi itu nol.
Misalnya,
mag[211.]
adalah4
, dan panjang4
representasi adalah{1, 1, 1, 1}
.Dengan menambahkan beberapa angka, kami menambah
211
ke angka terkecil yang dapat dibagi oleh210
(2*3*5*7
). Dan sekarang kita menyimpulkan bahwa angka aslinya lebih besar dari210
, karena420
sama dengan "kira-kira" dua kali lipat210
. Tidak sulit membayangkan bahwa jika kita mulai dari209
, angka terakhir adalah "kira-kira"210
.Fungsi
length[f_,n_]
mengambil nilai titik apungf
untuk memperkirakan besarnya, dan memperbaikinya berdasarkan representasi RNS-nyan
.Fungsi
rnsOperation[a_,b_,op_,rnsop_]
memberirnsop[a,b]
danop
sesuai dengan operasi normal yang digunakan untuk mendapatkan hasil perkiraan berdasarkan nilai floating point.Contoh
sumber
Python 3 , 435 byte
Tantangan ini telah ada dalam daftar ember saya untuk sementara waktu, tetapi baru-baru ini bahwa: a) Saya meluangkan waktu dan perhatian untuk mencoba jawaban; dan b) benar-benar menguji ide saya untuk menghitung ukuran angka (dan juga jumlah bilangan prima dengan membandingkannya dengan ukuran primorial) menggunakan beberapa kombinasi logaritma dan Teorem Sisa Tiongkok yang tidak suci. Sayangnya, bekerja dengan logaritma saat mencoba menentukan jumlah bilangan prima yang, misalnya,
large_primorial + 3
mengharuskan, berarti saya harus menemukan cara untuk mengatasi masalah floating-point.Jadi, ini adalah port jawaban Liam .
Cobalah online!
Penjelasan
Ketika mencoba menjawab jawaban Liam, saya pribadi menemukan beberapa penjelasan yang diberikan membingungkan, jadi ini adalah upaya saya untuk menjelaskan algoritmanya.
Pertama, kita mendapatkan residu
n
danm
.Ini melibatkan mengubah semua digit dari string input dan mengubahnya menjadi angka-angka modulo masing-masing bilangan prima kita, misalnya untuk 28, kita akan memiliki
[(20 + 8) mod 2, (20 + 8) mod 3, (20 + 8) mod 5, etc]
Kemudian kita tambahkan, gandakan, atau kurangi residu menggunakan pairwise
eval()
Kemudian kita mendapatkan ukuran residu kita, yaitu jumlah minimum bilangan prima yang kita butuhkan.
Mendapatkan ukuran adalah bagian tersulit dan paling intensif kode. Kami menggunakan
partial_chinese
fungsi, yang memberi kami urutanu_i
untuk menentukan ukuran. Lebihu_i
dalam sebentar.Urutan
u_i
dihitung dengan mengambil setiap residur_i
, mengurangi jumlahu_j * primorial(j) for j in [1, i)
, dan kemudiandividing
denganprimorial(i)
, semua moduloprimes[i]
. Yaituu_i = (r_i - SUM) / primorial(i)
,. Lebih lanjut tentang fungsi primorial dan divisi kami sebentar lagi.phi_i(j, i)
menghitungprimorial(j) mod primes[i]
. Divisi modulo setiap primep
mudah diimplementasikan dengan memeriksa invers perkalian secara manual, seperti yang kita dapat yakin bahwa apapun mungkinu_i
adalah0 <= u_i < p
dijamin akan coprime untuk p dan dijamin invers perkalian.Dengan semua yang dilakukan, kami mencetak string kami dan kami selesai.
Apa berikutnya
Ini menyenangkan untuk diterapkan. Saya masih ingin melihat apakah saya bisa menggunakan logaritma dalam beberapa cara di jawaban lain. Dan saya ingin menerapkan kode ini atau sesuatu seperti dalam bahasa golf fungsional, seperti APL atau Jelly. Semua dan semua saran dan koreksi golf dipersilahkan!
sumber