Clever Geek Handbook

Professional development program

I am trying to do quick exponentiation. But the result doesn't seem to give the correct result. Any help would be greatly appreciated. EDIT: Manage to fix this, thanks for all the help.

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


source to share


3 answers


Mark this Exposure by squaring

You probably want a bit right shift and square your base every time you come across 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 to think about your exponent being split is: let's 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 squared.

+1


source


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

It basically boils down to g1

3 . I am not familiar with this algorithm, but it may not be correct.



Also, as a side note, never call Math.pow(<var>, 2)

, just write <var> * <var>

.

0


source


There are several problems with your code, starting with reading the exp line in the wrong direction, adding additional base multiplications, and not considering rank 1

when increasing powers of 2.

Below is a quick sketch of the python 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 can use a square on each iteration:

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


source






More articles:


All Articles