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?
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
Follow-Ups: