Make two conditions for even and odd power..... and use it to make solve
higher power....
That could be solved in log b time
.
On 30-Sep-2011 4:12 AM, "Dave" <dave_and_da...@juno.com> wrote:
>
> @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.
>
--
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.
