Calculate this multiplication in less than O(n) complexity.

Question

here is the sample code of problem :
a=100000000,b=200000;
multiplication=1;
while(a--){
multiplication=multiplication*b;
}
printf "multiplication= result"
reduce the time complexity by giving a suitable example which must have less complexity than this for large numbers.

Comments

Try to solve it as b^a

---

actually I need to perform %********** after each step so need any iterative method. In pow() function I used as pow(n%modValue,pow) but it didn't work becuz it is exceeding limit.

---

Try to use the following formula and D&C with recursion should be O(log n) complexity.

(b^a) mod n = [{b^(a/2) mod n} * {b^(a/2) mod n}] mod n

Let me know if this works for you, if it works I will share the code.

---

tried recursion method and D&C with  O(log n) . thanks

---

Do I need to share the code, or you like to share it for the benefit of bigger mass.

---

okay Sir,I got the  solution and sharing code in answer section

Answer 1

I was facing the same issue and I used this method for multiplication which reduces complexity to O(log n)

 int  calculatePower(int n,int p)
    {
    int h;
    if(p==0)
    {
    return 1;
    }
    else{
    h=calculatePower(n,p/2);
        if(p%2==0)
        {
            return h*h;
        }
        else{
            return n*h*h;
        }
    }

}

Comments

I think u missed the mod part :)

---

for mod part : use %********** in return statement, like
return (h*h)%**********;
&
return (n*h*h)%**********; and change int to unsigned long int because function required to perform very large multiplication.