CODEWITHSUNDEEP
c++math
Grim Reaper
Grim Reaper

Reputation: 600

C++ - fmod return the wrong answer

First off, I'm doing this project for school and we are not allowed to use external libraries and hence I cannot use anything like GMP. The problem is, I have a function where it requires some "tough" calculations. ie, 

m^e mod n

Here's my code 

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int e = 17, n = 3233, m = 65;
    long double p, mod;

    p = pow(m, e); // Gives 6.59974e+30 which is correct

    mod = fmodl(p, n);

    cout<<mod; // Gives 887, When the correct answer is 2790

    return 0;
}

As you can see the fmod (fmodl) function does not return the correct value is there a workaround for this ? again, without using any external libraries.

Upvotes: 0

Views: 909

Answers (2)

Joe Z
Joe Z

Reputation: 17936

Your code is doing the best it can with this straightforward approach. A long double on x86 machines is only 80 bits long, with a good number of bits dedicated to exponent and sign.

The exact value of 6517 is about 103 bits long. So, you're suffering a truncation error. To do this large multiplication and modulus, you will need to be a little more intelligent about how you do the exponentiation and modulus.

Upvotes: 1

jyotesh
jyotesh

Reputation: 340

You can write your own modulo power function.

int modpow(int a,int b,int mod)
{
    int product,pseq;
    product=1;
    pseq=a%mod;
    while(b>0)
    {
        if(b&1)
            product=(product*pseq)%mod;
        pseq=(pseq*pseq)%mod;
        b>>=1
    }
    return product;
}

Refer http://en.wikipedia.org/wiki/Modular_exponentiation for explanation

Upvotes: 2

Related Questions