Re: A89: TI-GCC

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

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: