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(pown){
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
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
You can also do it in O(log2(log3(N))) by implementing binary search
for power of 3 !
but its slower than normal way for small N's !
On Sep 21, 8: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).
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).
yaa , that's right as then we are sure of having complexity O(n)
On Sep 23, 4:39 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).
Computing log base 2 is one multiplication simpler than computing log
base 3.
Dave
On Sep 22, 7:49 pm, Prabhu Hari Dhanapal dragonzsn...@gmail.com
wrote:
is computing log to the base 2 simpler than computing log to the base 3
?
On Tue, Sep 22, 2009 at 5:40 PM, Dave
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
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
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
