Operator modulo (%) memberikan hasil yang berbeda untuk versi .NET berbeda di C #

Saya mengenkripsi masukan pengguna untuk menghasilkan string untuk kata sandi. Tetapi sebaris kode memberikan hasil yang berbeda dalam versi kerangka kerja yang berbeda. Kode parsial dengan nilai kunci yang ditekan oleh pengguna:

Ditekan tombol: 1. Variabel asciiadalah 49. Nilai 'e' dan 'n' setelah dilakukan perhitungan:

e = 103, 
n = 143,

Math.Pow(ascii, e) % n

Hasil kode di atas:

• Di .NET 3.5 (C #)

  Math.Pow(ascii, e) % n
  

  memberi 9.0.

• Di .NET 4 (C #)

  Math.Pow(ascii, e) % n
  

  memberi 77.0.

Math.Pow() memberikan hasil yang benar (sama) di kedua versi.

Apa penyebabnya, dan adakah solusinya?

Math.Powbekerja pada bilangan floating-point presisi ganda; dengan demikian, Anda tidak boleh mengharapkan lebih dari 15–17 digit pertama dari hasil agar akurat:

Semua bilangan floating-point juga memiliki jumlah digit signifikan yang terbatas, yang juga menentukan seberapa akurat nilai floating-point mendekati bilangan real. Sebuah Doublenilai memiliki presisi hingga 15 digit desimal, meskipun secara internal maksimal 17 digit dipertahankan.

Namun, aritmatika modulo membutuhkan semua digit untuk akurat. Dalam kasus Anda, Anda menghitung ⁴⁹¹⁰³ , yang hasilnya terdiri dari 175 digit, membuat operasi modulo menjadi tidak berarti di kedua jawaban Anda.

Untuk menghitung nilai yang benar, Anda harus menggunakan aritmatika presisi-arbitrer, seperti yang disediakan oleh BigIntegerkelas (diperkenalkan di .NET 4.0).

int val = (int)(BigInteger.Pow(49, 103) % 143);   // gives 114

Sunting : Seperti yang ditunjukkan oleh Mark Peters dalam komentar di bawah, Anda harus menggunakan BigInteger.ModPowmetode, yang ditujukan khusus untuk jenis operasi ini:

int val = (int)BigInteger.ModPow(49, 103, 143);   // gives 114

Terlepas dari fakta bahwa fungsi hashing Anda tidak terlalu bagus ^* , masalah terbesar dengan kode Anda bukanlah bahwa ia mengembalikan angka yang berbeda tergantung pada versi .NET, tetapi dalam kedua kasus itu mengembalikan angka yang sama sekali tidak berarti: jawaban yang benar untuk masalah ini adalah

49 ¹⁰³ mod 143 = adalah 114. ( link Wolfram Alpha )

Anda dapat menggunakan kode ini untuk menghitung jawaban ini:

private static int PowMod(int a, int b, int mod) {
    if (b == 0) {
        return 1;
    }
    var tmp = PowMod(a, b/2, mod);
    tmp *= tmp;
    if (b%2 != 0) {
        tmp *= a;
    }
    return tmp%mod;
}

Alasan mengapa perhitungan Anda menghasilkan hasil yang berbeda adalah karena untuk menghasilkan jawaban, Anda menggunakan nilai antara yang menurunkan sebagian besar digit signifikan dari bilangan ⁴⁹¹⁰³ : hanya 16 pertama dari 175 digitnya yang benar!

1230824813134842807283798520430636310264067713738977819859474030746648511411697029659004340261471771152928833391663821316264359104254030819694748088798262075483562075061997649

159 digit sisanya semuanya salah. Operasi mod, bagaimanapun, mencari hasil yang membutuhkan setiap digit untuk benar, termasuk yang terakhir. Oleh karena itu, bahkan peningkatan terkecil pada ketepatan Math.Powyang mungkin telah diterapkan di .NET 4, akan menghasilkan perbedaan drastis pada penghitungan Anda, yang pada dasarnya menghasilkan hasil yang berubah-ubah.

^* Karena pertanyaan ini berbicara tentang menaikkan bilangan bulat menjadi kekuatan tinggi dalam konteks hashing kata sandi, mungkin ide yang sangat baik untuk membaca _tautan jawaban ini sebelum memutuskan apakah pendekatan Anda saat ini harus diubah untuk pendekatan yang berpotensi lebih baik.

Apa yang Anda lihat adalah kesalahan pembulatan dua kali lipat. Math.Powbekerja dengan double dan perbedaannya adalah sebagai berikut:

.NET 2.0 dan 3.5 => var powerResult = Math.Pow(ascii, e);mengembalikan:

1.2308248131348429E+174

.NET 4.0 dan 4.5 => var powerResult = Math.Pow(ascii, e);mengembalikan:

1.2308248131348427E+174

Perhatikan digit terakhir sebelumnya Edan itulah yang menyebabkan perbedaan hasil. Ini bukan operator modulus (%) .

Presisi floating-point dapat bervariasi dari mesin ke mesin, dan bahkan pada mesin yang sama .

Namun, .NET membuat mesin virtual untuk aplikasi Anda ... tetapi ada perubahan dari versi ke versi.

Oleh karena itu, Anda tidak boleh mengandalkannya untuk menghasilkan hasil yang konsisten. Untuk enkripsi, gunakan kelas yang disediakan Kerangka daripada menggulirkan kelas Anda sendiri.

Ada banyak jawaban tentang cara kode itu buruk. Namun, mengapa hasilnya berbeda…

FPU Intel menggunakan format 80-bit secara internal untuk mendapatkan lebih banyak presisi untuk hasil menengah. Jadi jika sebuah nilai ada di register prosesor, ia mendapat 80 bit, tetapi ketika ditulis ke tumpukan itu disimpan di 64 bit .

Saya berharap bahwa versi .NET yang lebih baru memiliki pengoptimal yang lebih baik dalam kompilasi Just in Time (JIT), jadi ia menyimpan nilai dalam register daripada menuliskannya ke stack dan kemudian membacanya kembali dari stack.

Mungkin JIT sekarang dapat mengembalikan nilai dalam register daripada di stack. Atau berikan nilai ke fungsi MOD dalam register.

Lihat juga pertanyaan Stack Overflow Apa aplikasi / manfaat dari tipe data presisi diperpanjang 80-bit?

Prosesor lain, misalnya ARM akan memberikan hasil yang berbeda untuk kode ini.

Mungkin yang terbaik adalah menghitungnya sendiri dengan hanya menggunakan aritmatika integer. Sesuatu seperti:

int n = 143;
int e = 103;
int result = 1;
int ascii = (int) 'a';

for (i = 0; i < e; ++i) 
    result = result * ascii % n;

Anda dapat membandingkan kinerja dengan kinerja solusi BigInteger yang diposting di jawaban lain.