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