Square root algorithms / Computer Science / Forums

Forums

4hv.org :: Forums :: Computer Science

« Previous topic | Next topic »

Square root algorithms

1 2 next

Move Thread

LAN_403

Bjørn

Sat Apr 22 2006, 11:50AM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

Does anyone know any efficient square root algorithms? I made this one in an attempt to make it very short and failsafe but it is the fastest one I have tried out so far.

I was surprised not to find anything faster so if anyone has any ideas or pointers towards something efficient it would be interesting to hear. I saw an algorithm years ago that was very efficient but I can't recall the name.

;r0 = sqrt(r1)
		mov     r0, #0
		mov     r3, #32768
loop1   orr     r0, r0, r3
		mul     r2, r0, r0
		cmp     r2, r1
		bichi   r0, r0, r3
		movnes  r3, r3, lsr #1
		bne     loop1

ShawnLG

Sat Apr 22 2006, 03:48PM

Registered Member #286 Joined: Mon Mar 06 2006, 04:52AM
Location:
Posts: 399

This one says it is under 20 clock cycles on some cpus.

JimG

Sat Apr 22 2006, 04:38PM

Registered Member #52 Joined: Thu Feb 09 2006, 04:22AM
Location: Austin TX
Posts: 57

The code you've shown is equivalent to the following C code:

int const isqrt( int const square )
{
   int guess = 0;
   int bit = 1 << 15;  // do the first 15 LSBs
   while ( bit > 0 ) 
   {
      guess |= bit;   // build up a value
      if ( guess * guess > square ) // is the square of the guess bigger than the orginal?
         guess &= ~bit; // remove the bit 
      bit >>= 1;
   }
   return guess;
}

It doesn't scale very well beyond 32 bit inputs and will always take 96 instructions to execute, but the algorithm you choose is dependant on your situation. If you're ever going to be taking the square root of 8 bit numbers you would use a different algorithm from if you were getting the square root of an 80 bit floating point number.

Normally table lookup with a Newton iteration like Newton-Raphson yeilds fast and accurate results for larger numbers. A purely iterative approach works really well for small numbers. It's always a trade off of overhead

I have used the BSR trick on Intel that is pointed out in the link ShawnLG provided to get an approximation before doing an iterative approach, as well.

Update: Fixed or to an and.

Electroholic

Sat Apr 22 2006, 09:20PM

Registered Member #191 Joined: Fri Feb 17 2006, 02:01AM
Location: Esbjerg Denmark
Posts: 720

Copied from circuit cellar issue 187

Sum of odds

uint16_t Exh_sumodd-opt
(uint16_t A)
{
uint16_t x_odd = 1;

while (x_odd <= A)
{
A -= x_odd;
x_odd += 2;
}

return (x_odd>>1);
}

Alfons

Sat Apr 22 2006, 11:43PM

Registered Member #134 Joined: Fri Feb 10 2006, 10:44PM
Location: Belgium
Posts: 86

In BASIC, this will work:

10 INPUT "Calculate square root of";A
20 GOSUB 50
30 PRINT "Square root of "A" is: ";B
40 END
50 O=1:B=0
60 AA=A*100
70 AA=AA-O
80 B=B+1
90 O=O+2
100 IF AA<=0 THEN B=B/10:RETURN
110 GOTO 70

(The code was given to me by Fedor Steeman, a Tandy Color Computer enthousiast)

Bjørn

Sun Apr 23 2006, 12:05AM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

My code does exactly the same as the following C code except that it exits early if it finds an exact result.

Table lookup in Flash memory is quite slow and the accuracy is not what I was aiming for but I have made a note of the <20 cycle algorithm for other uses.

I tried the sum of odds and i was faster on 8 bit numbers than my first attempt but if I configure my code for 8 bit then it becomes a lot faster than the sum of odds.

Simon

Sun Apr 23 2006, 12:15AM

Registered Member #32 Joined: Sat Feb 04 2006, 08:58AM
Location: Australia
Posts: 549

The Newton method should work well. To keep the options coming, what about a Taylor expansion? Ie. approximating the square-root function with a polynomial. Each term in your approximation should only involve two extra multiplications at most.

This isn't the best applicaton for Taylor approximations, however. Exponents and trig are better examples.

I guess this is meant to be a general algorithm, otherwise that would change things a lot.

Bjørn

Mon Apr 24 2006, 04:02PM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

It is supposed to be a general purpose algorithm for a microcomputer and have these properties that does not mix well:

Predictable
Accurate
Fast
Small

My first attempt unrolls well and I can use an unrolled version for 16 bit numbers and use that for small numbers and to approximate the square root of large numbers and use the looped version for 32 bit numbers.

Carbon_Rod

Tue Apr 25 2006, 04:43AM

Registered Member #65 Joined: Thu Feb 09 2006, 06:43AM
Location:
Posts: 1155

For low speed 8-bit real time fixed-root core design a look-up style hash table is nice as it uses no ram. =) Its cost is O (1) so itâ€™s fast, simple, and predictable. There is a space-time trade off.. However, it also offers controlled number rounding if a weighted result is needed.

Did you mean an n-th root function or specifically square root? Estimated results using successive approximation techniques are common.

Bjørn

Tue Apr 25 2006, 12:54PM

Registered Member #27 Joined: Fri Feb 03 2006, 02:20AM
Location: Hyperborea
Posts: 2058

I was specifically thinking about square roots since that is what I needed at the time. I would be interested in efficient implementations of all kinds of useful functions, including IEEE 754 floating point functions. There is only room for 8192 instructions and there is a lot of other things to be included.

1 2 next

Moderator(s): Chris Russell, Noelle, Alex, Tesladownunder, Dave Marshall, Dave Billington, Bjørn, Steve Conner, Wolfram, Kizmo, Mads Barnkob