Operator modulo (%) daje różne wyniki dla różnych wersji platformy .NET w C #

Szyfruję dane wejściowe użytkownika w celu wygenerowania ciągu dla hasła. Ale wiersz kodu daje różne wyniki w różnych wersjach frameworka. Kod częściowy z wartością klawisza naciśniętego przez użytkownika:

Wciśnięty klawisz: 1. Zmienna asciito 49. Wartość „e” i „n” po pewnych obliczeniach:

e = 103, 
n = 143,

Math.Pow(ascii, e) % n

Wynik powyższego kodu:

• W .NET 3.5 (C #)

  Math.Pow(ascii, e) % n
  

  daje 9.0.

• W .NET 4 (C #)

  Math.Pow(ascii, e) % n
  

  daje 77.0.

Math.Pow() daje poprawny (taki sam) wynik w obu wersjach.

Jaka jest przyczyna i czy istnieje rozwiązanie?

Math.Powdziała na liczbach zmiennoprzecinkowych o podwójnej precyzji; dlatego nie należy oczekiwać, że dokładność wyniku będzie większa niż pierwsze 15–17 cyfr :

Wszystkie liczby zmiennoprzecinkowe mają również ograniczoną liczbę cyfr znaczących, które również określają, jak dokładnie wartość zmiennoprzecinkowa aproksymuje liczbę rzeczywistą. DoubleWartość ma maksymalnie 15 cyfr po przecinku precyzji, chociaż maksymalnie 17 cyfr jest utrzymywana wewnętrznie.

Jednak arytmetyka modulo wymaga, aby wszystkie cyfry były dokładne. W twoim przypadku obliczasz 49 ¹⁰³ , którego wynik składa się z 175 cyfr, przez co operacja modulo jest bez znaczenia w obu twoich odpowiedziach.

Aby obliczyć poprawną wartość, należy skorzystać z arytmetyki o dowolnej precyzji, jak zapewnia BigIntegerklasa (wprowadzona w .NET 4.0).

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

Edycja : Jak zauważył Mark Peters w komentarzach poniżej, powinieneś użyć BigInteger.ModPowmetody, która jest przeznaczona specjalnie dla tego rodzaju operacji:

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

Pomijając fakt, że twoja funkcja haszująca nie jest zbyt dobra ^* , największym problemem z twoim kodem nie jest to, że zwraca inną liczbę w zależności od wersji .NET, ale w obu przypadkach zwraca całkowicie bezsensowną liczbę: prawidłowa odpowiedź na problem brzmi

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

Możesz użyć tego kodu do obliczenia tej odpowiedzi:

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;
}

Powodem, dla którego obliczenia dają inny wynik, jest to, że w celu uzyskania odpowiedzi używasz wartości pośredniej, która usuwa większość znaczących cyfr liczby 49 ¹⁰³ : tylko pierwsze 16 z 175 cyfr jest poprawnych!

1230824813134842807283798520430636310264067713738977819859474030746648511411697029659004340261471771152928833391663821316264359104254030819694748088798262075483562075061997649

Pozostałe 159 cyfr jest błędnych. Jednak operacja mod szuka wyniku, który wymaga, aby każda cyfra była poprawna, w tym ostatnia. Dlatego nawet najmniejsza poprawa precyzji Math.Powmogłaby zostać zaimplementowana w .NET 4, spowodowałaby drastyczną różnicę w obliczeniach, co w zasadzie daje arbitralny wynik.

^* Ponieważ to pytanie dotyczy podniesienia liczb całkowitych do wysokich potęg w kontekście haszowania haseł, może być bardzo dobrym pomysłem przeczytanie tego _linku odpowiedzi przed podjęciem decyzji, czy obecne podejście powinno zostać zmienione na potencjalnie lepsze.

To, co widzisz, to podwójny błąd zaokrąglenia. Math.Powdziała z double a różnica jest jak poniżej:

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

1.2308248131348429E+174

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

1.2308248131348427E+174

Zwróć uwagę na ostatnią cyfrę przed Ei to powoduje różnicę w wyniku. To nie jest operator modułu (%) .

Precyzja zmiennoprzecinkowa może się różnić w zależności od maszyny, a nawet na tej samej maszynie .

Jednak .NET tworzy maszynę wirtualną dla twoich aplikacji ... ale są zmiany z wersji na wersję.

Dlatego nie powinieneś polegać na nim, aby uzyskać spójne wyniki. Do szyfrowania użyj klas, które zapewnia Framework, zamiast toczenia własnych.

Istnieje wiele odpowiedzi dotyczących sposobu, w jaki kod jest zły. Jednak, dlaczego wynik jest inny…

Jednostki FPU Intela używają wewnętrznie formatu 80-bitowego , aby uzyskać większą precyzję wyników pośrednich. Więc jeśli wartość znajduje się w rejestrze procesora, otrzymuje 80 bitów, ale kiedy jest zapisywana na stosie, jest przechowywana na 64 bitach .

Oczekuję, że nowsza wersja .NET ma lepszy optymalizator w kompilacji Just in Time (JIT), więc zachowuje wartość w rejestrze zamiast zapisywać ją na stosie, a następnie odczytywać ją z powrotem ze stosu.

Może się zdarzyć, że JIT może teraz zwrócić wartość w rejestrze, a nie na stosie. Lub przekaż wartość do funkcji MOD w rejestrze.

Zobacz także pytanie o przepełnienie stosu Jakie są zastosowania / zalety typu danych o rozszerzonej precyzji 80-bitowej?

Inne procesory, np. ARM, dadzą inne wyniki dla tego kodu.

Może najlepiej jest obliczyć to samodzielnie, używając tylko arytmetyki całkowitej. Coś jak:

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

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

Możesz porównać wydajność z wydajnością rozwiązania BigInteger opublikowanego w innych odpowiedziach.