u people absolutely correct that log operation take much time , i just
given an approach
On Sat, Dec 10, 2011 at 7:25 AM, Dave <dave_and_da...@juno.com> wrote:
> @Gaurav: Even though this is O(log n), it is bound to be slow, since
> it would use division and modulus are among the slowest operations on
> modern computers, some of which don't even have an integer division
> instruction. Here is a revision to my earlier code, for 32-bit
> integers. It should be faster since it contains no loops.
>
> bool PowerOfThree(unsigned int n)
> {
> int powsof3[32] =
> {1,3,0,9,27,0,81,243,0,729,0,2187,6561,0,19683,59049,0,
> 177147,0,531441,1594
> 323,0,4782969,14348907,0,43046721,
>
> 129140163,0,387420489,0,1162261467,3486784401};
> int i = if( n >> 16 ) ? 16 : 0;
> if( n >> (i+8) ) i += 8;
> if( n >> (i+4) ) i += 4;
> if( n >> (i+2) ) i += 2;
> if( n >= (i+1) ) i += 1;
> return powsof3[i] == n;
> }
>
> As in the previous algorithm, the first few statements use a binary
> search to find the bit number of the highest order bit set. There can
> be at most one power of three corresponding to each high-order-bit
> number, so we then check to see if the input number is the only
> possible power of three in the table of powers of 3 that is indexed by
> the high-order-bit number. The zeros in powsof3[] correspond to high-
> order-bit numbers that have no power of three.
>
> Dave
>
> On Dec 9, 2:35 am, Gaurav Kumar <gkuma...@gmail.com> wrote:
> > What if we create a base 3 number from the given number N and then check
> if there is only 1 bit with value 1 and all values should be 0. For
> example, if lets say the number is 27. Its base 3 number will be 1 0 0 0,
> now since there is only 1 single 1 present in this representation, it is a
> power of 3.
> >
> > Gaurav
> >
> > On Dec 7, 2011, at 6:03 PM, saurabh singh wrote:
> >
> >
> >
> > > 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 athttp://
> 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 athttp://
> 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 athttp://
> 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.
