Re: A89: TI-GCC
[Prev][Next][Index][Thread]
Re: A89: TI-GCC
> I hate to be incredibly ignorant and everything, but what does the "<<"
and
> "">>" operators do to numbers? I know as a standalone they are overloaded
> for I/O stuff, but... anyone give me a hand (brain) here?
In C++ only, in C they mean bit shifts...
> Thanks from the hopelessly ignorant =)
>
> >From: Johan <johei804@student.liu.se>
> >Reply-To: assembly-89@lists.ticalc.org
> >To: assembly-89@lists.ticalc.org
> >Subject: Re: A89: TI-GCC
> >Date: Tue, 28 Mar 2000 20:59:11 +0200
> >
> >
> >On Tue, Mar 28, 2000 at 01:08:26 -0500, Scott Noveck wrote:
> > >
> > > This should be a lot faster [...] - assuming that this works - [...].
> > >
> > > int sqroot(int num)
> > > {
> > > int cntr = -1, root = 0;
> > > while((num-=(cntr+=2))>=0)
> > > root++;
> > > return root;
> > > }
> >
> >The algorithm works, but it's slower. A rough time complexity analysis
> >reveals that your algorithm is O(sqrt(n)), while the other algorithm is
> >O(log n) (or O(1) if you prefer). (Well, the other algorithm wouldn't
even
> >compile, but nevertheless, with the proper modifications it would, and it
> >would be faster.)
> >
> >In plain English this means that if your algorithm takes T time for
> >calculating the square root of a number N, it would take approximately
2*T
> >time for calculating the square root of 4*N. If the other algorithm takes
T
> >time for sqrt(N), it would take 2*T time for sqrt(N^2)...
> >
> >Below is a different but working version of "the other algorithm" that
> >takes
> >O(log n) time. Here 'log n' is fixed because it doesn't support variable-
> >length integers, and the function is in fact O(1), i.e. it actually takes
> >about the same amount of time for *all* numbers.
> >
> >Your algorithm, above, might be faster for small numbers (the O()
notation
> >doesn't tell), but as N approaches infinity, the other algorithm is
*much*
> >faster. I did a simple test with 64-bit 'long long' integers (square root
> >of
> >4,611,686,018,427,387,904 = 2,147,483,648) and the algorithm below
> >(modified
> >to the new integer size of course) returned the answer "instantly", while
> >your algorithm (also modified of course) never returned an answer at
all...
> >(It would, eventually, but I didn't want to spend the whole night waiting
> >for it... :) )
> >
> >unsigned short isqrt(unsigned long x) {
> > /* obviously doesn't work for negative integers ('unsigned long') */
> > /* returns floor(sqrt(x)) */
> > /* algorithm from SNIPPETS oct 95 */
> > /* please optimize me! :) */
> > unsigned short a=0,r=0,e=0;
> > int i;
> > for(i=0;i<16;i++) { /* 16 is bitsof(unsigned long)/2 */
> > r=(r<<2)+(x>>30); /* 30 is bitsof(unsigned long)-2 */
> > x<<=2;
> > a<<=1;
> > e=(a<<1)+1;
> > if(r>=e) {
> > r-=e;
> > a++;
> > }
> > }
> > return a;
> >}
> >
> >
> >/Johan
> >
>
> ______________________________________________________
> Get Your Private, Free Email at http://www.hotmail.com
>
>
References: