CODEWITHSUNDEEP
algorithm
user1906537
user1906537

Reputation:

Exponentiation program

I am trying to do a fast exponentiation. But the result does not seem to produce the correct result. Any help would be appreciated. EDIT: Manage to solve it thanks for all the help.

        if (content[i] == '1')
            s1 = (int)(po1 * (Math.pow(po1, 2)));
        else
            s1 = po1 * po1;
        final_result *= temp;

Upvotes: 3

Views: 148

Answers (3)

Ajk_P
Ajk_P

Reputation: 1874

Check out this Exponation by squaring

You probably want to bit-shift right and square your base each time you encounter a 1 bit in the exponent

int pow(int base, int e)
{
    int retVal = 1;
    while (e)
    {
        if (e % 2 == 1)//i.e. last bit of exponent is 1
            retVal *= base;
        e >>= 1; //bitshift exponent to the right.
        base *= base; // square base since we shifted 1 bit in our exponent
    }

    return retVal ;
}

A good way of thinking about it is that your exponent is being broken down: say, 6^7 (exponent in bits is 1, 1, 1) = 6^1 * 6^2 * 6^4 = 6 * 36 * 36^2 = 6 * 36 * 1296. Your base is always squaring itself.

Upvotes: 1

njzk2
njzk2

Reputation: 39406

There are several problems with your code, starting with the fact that you are reading the exp string in the wrong direction, adding extra multiplications by the base, and not considering the rank of the 1 when raising the powers of 2.

Here is a python quick sketch of what you are trying to achieve:

a = int(raw_input("base"))
b = "{0:b}".format(int(raw_input("exp")))

res = 1
for index, i in enumerate(b[::-1]):
    if i == '1':
        res *= a**(2**index)

print res

Alternatively, you could square a at every iteration instead:

for index, i in enumerate(b[::-1]):
    if i == '1':
        res *= a
    a *= a

Upvotes: 0

MattPutnam
MattPutnam

Reputation: 3017

temp = (int)(g1 * (Math.pow(g1, 2)));

This basically just boils down to g13. I'm not familiar with this algorithm but this can't be right.

Also, as a side note, don't ever call Math.pow(<var>, 2), just write <var> * <var>.

Upvotes: 0

Related Questions