dokumen apa pun yang mengatakan dengan tepat berapa kisaran angka .NET BigIntegers dirancang untuk?

Saya bermain-main dengan .NET BigInteger dan pada dasarnya saya bertanya-tanya berapa nomor - jawaban yang diperkirakan akan baik-baik saja - adalah titik deviasi dari kurva (grafik (peningkatan waktu yang diperlukan untuk operasi) vs (nilai BigInteger))?

atau apakah mereka dirancang tanpa penyimpangan sedemikian rupa sehingga jika kita memplot peningkatan waktu yang diperlukan untuk operasi vs nilai BigInteger dari 1 hingga tak terbatas, kita akan memiliki kurva yang halus sepanjang jalan?

misalnya, asumsi array dirancang dengan kemampuan menangani 50 item. ini berarti bahwa jika saya memiliki 1 item, operasi adalah f (1) waktu. dan ketika saya memiliki 2 item, operasi adalah f (2) waktu. jika saya punya 50 item, operasi adalah f (50) waktu. tetapi karena dirancang untuk menangani 50 item saja, operasi yang dilakukan ketika kita memiliki 51 item akan menjadi g (51) di mana g (51)> f (51).

Jika diimplementasikan dengan benar, kompleksitas aritmatika BigInteger harus menjadi kurva yang halus. Sebagai contoh kompleksitas waktu dari perkalian harus O (NM) di mana N adalah jumlah digit dalam perkalian pertama, dan M adalah jumlah digit dalam perkalian kedua. Tentu saja ada batasan praktis di mana Anda dapat memilih N dan M begitu besar sehingga angkanya tidak muat di mesin Anda.

Apakah ada / apakah ada yang tahu tentang dokumen yang mengklaim telah diimplementasikan?

Angka apa pun yang mungkin bisa lebih besar dari ULong.MaxValue, atau lebih kecil dari Long.MinValue harus direpresentasikan menggunakan BigInteger.

Jika TIDAK (Long.MinValue <= X <= ULong.MaxValue) Maka BigInteger

BigInteger adalah untuk jumlah yang terlalu besar daripada yang bisa ditangani oleh primitif normal.

Misalnya jika integer Anda berada di luar rentang Long, Anda mungkin harus menggunakan BigInteger. Kasus-kasus ini sangat jarang, dan menggunakan kelas-kelas ini memiliki overhead yang secara signifikan lebih tinggi daripada rekan-rekan primitif mereka.

Misalnya, longlebar 64 bit dan dapat menampung kisaran: -9.223.372.036.854.775.808 hingga 9.222.372.036.854.775.88. ulong dapat menampung 0 hingga 18.446.744.073.709.551.615. Jika angka Anda lebih besar atau lebih kecil dari itu, BigInteger adalah satu-satunya pilihan Anda

Satu-satunya saat saya melihat mereka digunakan dalam aplikasi dunia nyata adalah aplikasi starchartting.

Lihat Juga: Kisaran Primitif di .NET

Dalam beberapa hal, titik BigInteger bukanlah ukuran absolut karena ketepatannya tidak terbatas. Angka floating point bisa sangat besar juga, tetapi memiliki presisi terbatas. BigInteger memungkinkan Anda melakukan aritmatika tanpa khawatir tentang kesalahan pembulatan atau melimpah. Harga yang Anda bayar adalah ratusan kali lebih lambat daripada aritmatika dengan bilangan bulat biasa atau angka floating point.

Seperti yang telah ditunjukkan orang lain, ulong dapat menampung antara 0 hingga 18.446.744.073.709.551.615, dan selama Anda tinggal di kisaran itu, Anda dapat melakukan aritmatika yang tepat. Jika Anda melampaui angka 1 di luar rentang itu, Anda akan mendapatkan luapan, jadi jawaban untuk pertanyaan Anda adalah menggunakan BigInteger jika Anda membutuhkan aritmatika yang tepat dan ada kemungkinan bahwa hasil antara akan melebihi 18.446.744.073.709.551.615.

Sebagian besar masalah dalam sains, teknik dan keuangan dapat hidup dengan perkiraan yang dipaksakan oleh angka floating point, dan tidak mampu membayar biaya waktu aritmatika BigInteger. Sebagian besar perhitungan komersial tidak dapat hidup dengan perkiraan aritmatika floating point, tetapi bekerja dalam kisaran 0 hingga 18.446.744.073.709.551.615, sehingga mereka dapat menggunakan aritmatika biasa. BigInteger diperlukan ketika menggunakan algoritma dari teori bilangan yang mencakup hal-hal seperti kriptografi (pikirkan bilangan prima 50 digit). Kadang-kadang juga digunakan dalam aplikasi komersial ketika perhitungan yang tepat diperlukan, kecepatan tidak terlalu penting, dan pengaturan sistem titik desimal tetap yang tepat terlalu banyak kesulitan.

Jika diimplementasikan dengan benar, kompleksitas aritmatika BigInteger harus menjadi kurva yang halus. Sebagai contoh kompleksitas waktu dari perkalian harus O (NM) di mana N adalah jumlah digit dalam perkalian pertama, dan M adalah jumlah digit dalam perkalian kedua. Tentu saja ada batasan praktis di mana Anda dapat memilih N dan M begitu besar sehingga angkanya tidak muat di mesin Anda.

Jika Anda Google "Kompleksitas komputasi biginteger" Anda akan mendapatkan lebih banyak referensi daripada yang bisa Anda lakukan. Salah satu yang berbicara langsung ke pertanyaan Anda adalah ini: Perbandingan dua paket aritmatika presisi sewenang-wenang .

Batas Memori

BigInteger bergantung pada array int untuk penyimpanan. Dengan asumsi ini, batas teoritis untuk angka maksimum, yang BigInteger mampu wakili, dapat diturunkan dari ukuran array maksimum yang tersedia di .net. Ada topik SO tentang array di sini: Menemukan berapa banyak memori yang dapat saya alokasikan untuk array di C # .

Dengan asumsi bahwa kita mengetahui ukuran array maksimum, kita dapat memperkirakan jumlah maksimum, yang dapat mewakili BigInteger: (2 ^ 32) ^ max_array_size, di mana:

• 2 ^ 32 - jumlah maksimum dalam sel array (int)
• max_array_size - ukuran maksimum yang diizinkan dari array int yang dibatasi oleh ukuran objek 2GB

Ini memberikan angka dengan 600 juta digit desimal.

Batas Kinerja

Adapun kinerja, BigInteger menggunakan algoritma Karatsuba untuk perkalian dan algoritma linier untuk menambahkan. Kompleksitas multiplikasi adalah , itu berarti skala akan cukup baik bahkan untuk angka besar ( Grafik kompleksitas ), namun Anda masih dapat mencapai penalti performa tergantung pada ukuran RAM dan cache prosesor.

Sejauh ini, karena ukuran angka maksimum dibatasi hingga 2GB, pada mesin keturunan Anda tidak akan melihat kesenjangan kinerja yang tidak terduga, tetapi masih beroperasi pada angka 600 juta digit akan mati lambat.

Batasnya adalah ukuran memori Anda (dan waktu yang Anda miliki). Jadi, Anda dapat memiliki jumlah yang sangat besar. Seperti yang dikatakan oleh Kevin, dalam kriptografi kita harus melipatgandakan atau mengalikan angka dengan beberapa ribu (biner) digit, dan ini dimungkinkan tanpa masalah.

Tentu saja, seringkali algoritme menjadi lebih lambat karena angkanya semakin besar, tetapi tidak terlalu lambat.

Ketika Anda menggunakan angka dalam rentang mega-digit, Anda mungkin ingin memikirkan solusi lain, karena - ketika benar-benar menghitung dengan mereka, akan menjadi lambat.

Ada beberapa kegunaan dalam komunitas ilmiah (yaitu jarak antara galaksi, jumlah atom di bidang rumput, dll.)

Seperti yang disarankan oleh kevin cline, BigNumber ditambahkan ke perpustakaan. NET terutama karena mereka diperlukan sebagai blok bangunan untuk banyak algoritma kriptografi modern (tanda tangan digital, enkripsi kunci publik / swasta, dll.). Banyak algoritma kriptografi modern melibatkan perhitungan nilai integer dengan ukuran hingga beberapa ribu bit. Karena kelas BigNumber menggambarkan kelas yang didefinisikan dengan baik dan bermanfaat, mereka memutuskan untuk menjadikannya publik (daripada menjaganya sebagai detail internal API kriptografi).