isnt his algo same like modular exponentiation in CLRS
On Wed, Sep 23, 2009 at 5:09 PM, Dufus <rahul.dev.si...@gmail.com> wrote:
>
> Vicky, Yup! you got it there.
> BTW you might like to do binary search again instead of sequential
> search when you hit the break condition.
> to indeed make it O(logn).
> Infact if M=3^n is given then this algo would be of complexity O(log
> log M)
>
> _dufus
>
>
>
> On Sep 23, 11:59 am, vicky <mehta...@gmail.com> wrote:
> > ok i can tell one with complexity of O(log(n)) , u take a no. pow =
> > 3,temp=3;
> > then
> > while(1){
> > temp=pow;
> > pow*=pow;
> > if(pow>n){
> > pow=pow/temp;
> > break;
> > }
> > }
> > now do , pow =pow *3; untill pow>=n;
> > and check from here
> > am i clear?
> > On Sep 23, 2:40 am, Dave <dave_and_da...@juno.com> wrote:
> >
> > > He didn't ask for efficient ways, only other ways.
> >
> > > On Sep 22, 2:36 pm, Ramaswamy R <ramaswam...@gmail.com> wrote:
> >
> > > > Can we evaluate the logarithm any more efficiently that repeated
> division by
> > > > 3?
> >
> > > > On Tue, Sep 22, 2009 at 12:27 PM, Dave <dave_and_da...@juno.com>
> wrote:
> >
> > > > > You could compute the logarithm of the number to the base 3 and see
> if
> > > > > the result is an integer.
> >
> > > > > Dave
> >
> > > > > On Sep 21, 12:22 pm, Anshya Aggarwal <anshya.aggar...@gmail.com>
> > > > > wrote:
> > > > > > how to find that whether the given number was of the form 3^n. (
> i.e. 3
> > > > > to
> > > > > > the power n).
> > > > > > one way is to recursively divide the number by 3 and check the
> remainder.
> > > > > > Is there any other way using bit manipulation or anything else??
> >
> > > > > > --
> > > > > > Anshya Aggarwal
> >
> > > > --
> > > > Yesterday is History.
> > > > Tomorrow is a Mystery.
> > > > Today is a Gift! That is why it is called the Present :).
> >
> > > >http://sites.google.com/site/ramaswamyr-Hidequoted 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
-~----------~----~----~----~------~----~------~--~---
