CODEWITHSUNDEEP
c#c#-4.0double
V. Panchenko
V. Panchenko

Reputation: 814

Incorrect calculation double

I have some C# application:

double n = p * q;
double S = Math.Pow(M, d) % n;

In my situation, M==7, d==27, n = 55. I calculate it in the Windows default calculator, and get 28. But my application returns 14. Why?

Upvotes: 0

Views: 124

Answers (2)

D Stanley
D Stanley

Reputation: 152556

double has a maximum of 16 digits of precision, but 7^27 is a 23-digit number, so you are losing precision in the exponentiation. Windows calculator supports 32 digits of precision for transcendental functions (like pow), so it can perform the calculation without a loss of precision.

You could use the mathematical fact that (a^b) % N is the same an ((a%n) ^ b) % n, but you're still raining a number greater then 2 to the 27th power which can't be precisely represented in a double.

Another option is to split the power into multiple exponents that can be represented in a double without a loss of precision:

     7^27 = 7^9 * 7^9 * 7^9
7^27 % 55 = ((7^9) % 55 * (7^9) % 55 * (7^9) % 55) % 55
          = (52 * 52 * 52) % 55
          = 140,608 % 55
          = 28

Upvotes: 4

ernest
ernest

Reputation: 1724

As D Stanley mentioned, double only has 16 digits of precision. You need to use BigInteger. Which is in .NET 4.5 and 4.6. You'll need to add a reference to System.Numerics

BigInteger test = BigInteger.Pow(7, 27) % 55;

Upvotes: 4

Related Questions