Re: A89: TI-GCC


[Prev][Next][Index][Thread]

Re: A89: TI-GCC




I love Algorithms in C!  Its a great book!  Unless you got your algorithm
analysis techniques elsewhere.  But, its still a good book :)
--kaus


----- Original Message -----
From: "Johan" <johei804@student.liu.se>
To: <assembly-89@lists.ticalc.org>
Sent: Tuesday, March 28, 2000 12:59 PM
Subject: Re: A89: TI-GCC


>
> 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
>




Follow-Ups: References: