CODEWITHSUNDEEP
javac++calgorithmmath
nishantbhardwaj2002
nishantbhardwaj2002

Reputation: 767

Is there anything wrong with my implementation of exponential by squaring?

I implemented the exponential by squaring in java. And copied from net, a C code for the same. But the problem is, these codes are giving different outputs.

The input i am giving is: 2 as base and 999999999 and 1000000000 as powers.

here is my java code:

long power(int b,int i){
    long num;
    if(i==1)
        return b;
    else if(i%2==0){
        num=(long)Math.pow(power(b,i/2),2);
        if(num>=1000000007)
            num%=1000000007;
        return num;
    }
    else{
        num=b*(long)Math.pow(power(b,(i-1)/2),2);
        if(num>=1000000007)
            num%=1000000007;
        return num;
    }
}

output: 646458262 178281319

here is the C code i got from net:

long long int fast_exp(int base, int exp)
{
    if(exp==1)
    return base;
    else
    {
        if(exp%2 == 0)
        {
            long long int base1 = pow(fast_exp(base, exp/2),2);
            if(base1 >= 1000000007)
            return base1%1000000007;
            else
            return base1;
        }
        else
        {
            long long int ans = (base*  pow(fast_exp(base,(exp-1)/2),2));
            if(ans >= 1000000007)
            return ans%1000000007;
            else
            return ans;
        }
    }
}

output: 646458006 477022294

Upvotes: 0

Views: 470

Answers (3)

T.C.
T.C.

Reputation: 137395

Don't use floating point numbers and functions that use them (including pow/std::pow in C/C++ or Math.pow in Java) for integer math. It doesn't do what you want.

A double usually have about 15 decimal digits of precision. (In C++, check with std::numeric_limits<double>::digits10; in C, it's the DBL_DIG macro.) The result of 1000000006 * 1000000006 (1000000006 being the largest value your fast_exp can return, since it returns the result modulo 1000000007) has 19 decimal digits, which means that it can't be accurately represented in a double. As a result, the return value of your pow calls is likely inaccurate at least in some cases.

Just use plain old integer multiplication:

long long int fast_exp(int base, int exp)
{
    if(exp==1)
    return base;
    else
    {
        if(exp%2 == 0)
        {
            long long int ret = fast_exp(base, exp/2);
            long long int base1 = ret * ret;
            return base1 % 1000000007;
        }
        else
        {
            long long int ret = fast_exp(base, (exp-1)/2);
            long long int ans = base * ret;
            ans %= 1000000007; 
            ans *= ret;
            return ans % 1000000007;
        }
    }
}

int main() {
    std::cout << fast_exp(2, 999999999) << std::endl;
    std::cout << fast_exp(2, 1000000000) << std::endl;
    return 0;
}

This produces:

570312504
140625001

Sanity check: 570312504 * 2 - 140625001 == 1000000007.

The equivalent Java version produces the same output, as expected.

A simple demo of the inaccuracies of floating point:

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main()
{
    cout << setprecision(20) << pow(1000000006, 2) << endl
         << 1000000006LL * 1000000006LL << endl;
}

prints:

1000000012000000000
1000000012000000036

So does the equivalent Java version.

Upvotes: 4

laune
laune

Reputation: 31300

Welcome to the wonders of floating point arithmetic.

The implementation of Math.pow may vary. If you change the Java code to 

 static long power(int b,int i){
    long num;
    if(i==1)
        return b;
    else if(i%2==0){
        long p = power(b,i/2);
        double dp = (double)p;
        num=(long)(dp*dp);
        if(num>=1000000007)
            num%=1000000007;
        return num;
    }
    else {
        long p = power(b,i/2);
        double dp = (double)p;
        num=(long)(b*dp*dp);
        num=(long)(b*Math.pow(power(b,(i-1)/2),2));
        if(num>=1000000007)
        num%=1000000007;
        return num;
    }
}

the results are

646458262 477022294

which shows that C++ appears to handle integer powers differently, in comparison to Math.pow( double base, double exp );

It's impossible to discuss such issues without reading the source code of Math.pow and the pow function in the C++ library.

Upvotes: 1

Eypros
Eypros

Reputation: 5723

Why you are converting double to long here:

num=b*(long)Math.pow(power(b,(i-1)/2),2);

Original code does not do that:

long long int ans = (base*  pow(fast_exp(base,(exp-1)/2),2));

I guess that has something to do with the result.

Upvotes: 0

Related Questions