CODEWITHSUNDEEP
c#mathmodulo
John Smith
John Smith

Reputation: 23

C#, Modulo operation gives different result than a calculator

So I wanted to write this method : 142^23 (mod 187), and using any calculator I get the result 65 but with this piece of code : double number = Math.Pow(142, 23) % 187 I get a result of 53. Why is this, and what am I doing wrong here?

Upvotes: 2

Views: 317

Answers (3)

maria rahel varnhagen
maria rahel varnhagen

Reputation: 1

BigInteger D = 353068955875873;
BigInteger E = 324734382257802;
BigInteger F = 752748311613664;
D ^ E % F
112448018451627

however:
BigInteger.ModPow(D, E, F)
116860072266913

Upvotes: -1

user47589
user47589

Reputation:

If we use BigInteger to compute the full result of the exponential:

var bi = BigInteger.Pow(142, 23);
Debug.WriteLine(bi);

We get this very large number:

31814999504641997296916177121902819369397243609088
or
3.1814999504642E+49

If we then convert that value to a double, to cause a loss of precision, and then back to a BigInteger:

var d = (double) bi;
bi = new BigInteger(d);
Debug.WriteLine(bi);

We get:

31814999504641997296916177121902819369397243609088  -- BigInteger
31814999504641993108158684988768059669621048868864  -- BigInteger -> double -> BigInteger
                ^ oh no mah precision

In hexadecimal, where the loss of precision is more obvious:

15C4 C9EB 18CD 25CE 858D 6C2D C3E5 D319 BC9B 8000 00
15C4 C9EB 18CD 2500 0000 0000 0000 0000 0000 0000 00   
                 ^ oh no mah precision

You'll notice that the loss of precision occurs at the 17th decimal digit, or the 14th hexadecimal digit.

Why?

A double is stored using IEEE-754 encoding:

Significand or mantissa:          0-51
Exponent:                         52-62
Sign (0 = Positive, 1 = Negative) 63

The key here is 52 bits for the mantissa. Our 14 hexadecimal digits are 56 bits, close to the 52-bit limit. How can we account for the 4-bit discrepancy?

(I think I made a mistake in the explanation that follows. If someone can point it out, I would be grateful)

The last unchanged hex digit is C, or 1100 in binary; since the last two bits are zeroes, our number was encoded in 54 bits, not 56. So, it's actually a 2-bit discrepancy.

How do we account for the last two bits? This is due to how the fractional component of IEEE-754 is determined. It's been a long time since I did this, so I'll leave it as an exercise for the reader :)

Upvotes: 2

vcsjones
vcsjones

Reputation: 141588

Math.Pow(142, 23) is too big to accurately be represented by a double. So your modulus is done on a lossy calculation.

This will give the correct answer:

BigInteger.ModPow(142, 23, 187);

BigInteger can be found in the System.Numerics namespace and assembly.

You can also implement this yourself efficiently if you want like so for integers of the size you were using in your question.

private static int ModPow(int basenum, int exponent, int modulus)
{
    if (modulus == 1)
    {
        return 0;
    }
    int result = 1;
    for (var i = 0; i < exponent; i++)
    {
        result = (result * basenum) % modulus;
    }
    return result;
}

BigInteger does something more clever with binary exponentiation which will work better with truly huge number.

Upvotes: 12

Related Questions