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: