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;
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.
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>
.
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