@Don, Ankuj. I believe that Don's algorithm uses precisely
floor{log_2(b)) + (the number of one bits in b) - 1.

Dave

On Sep 29, 1:38 pm, Don <dondod...@gmail.com> wrote:
> Because a^b = (a*a)^(b/2), so each multiplication reduces the exponent
> by half. Therefore the number of multiplications is (roughly) log2 b.
>
> int pow(int a, int b)
> {
>   int result = a;
>   while(b > 1)
>   {
>     result *= (b&1) ? a*result : result;
>     b >>= 1;
>   }
>   return result;
>
> }
>
> You can see that a^16 will require 4 multiplications, which is
> log2(16), but a^15 will require 6 multiplications (an alternative
> algorithm could do it in 4 multiplications and a division).
>
> Also note that the function above is only correct for b > 0.
>
> Don
>
> On Sep 29, 12:54 pm, Ankuj Gupta <ankuj2...@gmail.com> wrote:
>
>
>
> > How do you deduce number of multiplication  that when we perform a^b
> > function using dividing the exponent by 2 at each stage to be log b?- Hide 
> > quoted text -
>
> - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Reply via email to