what about this log(base 3 n) is of integral type then n is a power of 3
On Mon, Dec 5, 2011 at 11:36 PM, Dave <[email protected]> wrote: > @Carl: You can generate the constants the first time the procedure is > called. There is no need to do them every time. So the first call > would be O(wordsize) but subsequent calls are O(1). > > Dave > > On Dec 5, 10:28 am, Carl Barton <[email protected]> wrote: > > Sorry, I was being a bit vague. I meant what would the time complexity be > > then? > > As I understand your Constant time is Dependant on the constant pre > > computation you do, which is no longer the case when you generalise > > > > On 5 December 2011 16:14, Dave <[email protected]> wrote: > > > > > > > > > @Carl: Of course. For any given word size, extend the tables of powers > > > of 2 and of 3 and change the for loop limit. > > > > > Dave > > > > > On Dec 5, 9:36 am, Carl Barton <[email protected]> wrote: > > > > Ah I see, in which case could you not generalise your solution for > all > > > > integers? > > > > By taking into account the size of words on the computer for example? > > > > > > On 5 December 2011 15:09, Dave <[email protected]> wrote: > > > > > > > @Carl: Yes, as coded, my algorithm is for 32-bit integers. But the > > > > > original poster asked for a solution using bit manipulation, and > > > > > modulus and division are arithmetic operations, not bit operations. > > > > > > > Dave > > > > > > > On Dec 5, 8:56 am, Carl Barton <[email protected]> wrote: > > > > > > @Dave Yours only works for a certain subset of all possible > powers > > > or 3 > > > > > > doesn't it? So WgpShashank's would be more general? > > > > > > > > On 5 December 2011 14:30, Dave <[email protected]> wrote: > > > > > > > > > @WgpShashank: Yours is an O(log n) solution. Mine is O(1). > > > > > > > > > Dave > > > > > > > > > On Dec 5, 6:21 am, WgpShashank <[email protected]> > wrote: > > > > > > > > @SAMMM have a look > > > > > > > > > > * *solution is to keep dividing the number by 3, i.e, do n = > n/3 > > > > > > > > iteratively. In any iteration, if n%3 becomes non-zero and n > is > > > not 1 > > > > > > > then > > > > > > > > n is not a power of 3, otherwise n is a power of 3 > > > > > > > > > > check it out ?http://codepad.org/863ptoBE > > > > > > > > > > Thanks > > > > > > > > Shashank > > > > > > > > Computer Science > > > > > > > > BIT Mesrahttp:// > > > > > > >www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ > > > > > > > > > -- > > > > > > > You received this message because you are subscribed to the > Google > > > > > Groups > > > > > > > "Algorithm Geeks" group. > > > > > > > To post to this group, send email to > [email protected]. > > > > > > > To unsubscribe from this group, send email to > > > > > > > [email protected]. > > > > > > > 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 [email protected]. > > > > > To unsubscribe from this group, send email to > > > > > [email protected]. > > > > > 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 [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- * Regards* *"The Coder"* *"Life is a Game. The more u play, the more u win, the more u win , the more successfully u play"* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
