Could not understand how it is fast

#1

Could not understand how it is fast. Because at the step of the loop we are updating the a with the following equation:
a=a*a
And in the normal exponential also we do it for the p(power) times

#2

hello @ayusdas2000
no they are not same.

a^n = a * a^(n-1) (this is what we are doing our trivial method)

a^n= a^(n/2) * a^(n/2) (this is what we are doing in fast emponetiation).

if u try to find time complexity it will be O(n) for first.
but O(log(n)) for second , because in second one power is changing with a factor of 2.
wheres in first one it is linear.

for more clarity refer gaurav sen video on utube.

#3

i think you gave the reply for fast exponention through recursion but i am asking fast exponention through bit masking.

#4

idea is exaclty same.
we are not perfomring n iteration .
iterations are always log(n) .
how ?
check
n=n>>1;
line of ur code. what it is doing ?
it is reducing ur n by factor of 2.
so after log(n) iteration n will be less than or equal to 1 for sure.

#5

thank you. I understood