Originaly problem rules out the use of log.Moreover log (or any floating point operations) take lot of hardware time as they are emulated on the floating point environment on most machines.Thirdly precision problem for higher values of n may cause your solution to give wron g answers,,,
On Wed, Dec 7, 2011 at 11:54 PM, tech coder <techcoderonw...@gmail.com>wrote: > 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 <dave_and_da...@juno.com> 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 <odysseus.ulys...@gmail.com> 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 <dave_and_da...@juno.com> 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 <odysseus.ulys...@gmail.com> 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 <dave_and_da...@juno.com> 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 <odysseus.ulys...@gmail.com> >> 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 <dave_and_da...@juno.com> wrote: >> > >> > > > > > > @WgpShashank: Yours is an O(log n) solution. Mine is O(1). >> > >> > > > > > > Dave >> > >> > > > > > > On Dec 5, 6:21 am, WgpShashank <shashank7andr...@gmail.com> >> 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 >> 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. >> > >> > > -- >> > > 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. >> >> > > > -- > * > > 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 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. > -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
