Need 1/sqrt(x) for simple machine

Need 1/sqrt(x) for simple machine

Post by Henry Ri » Tue, 16 May 1995 04:00:00



I have a simple machine (i. e. only add/subtract, but with support
for recoded multiplication and nonrestoring division).  I need to
calculate 1/sqrt(x), sometimes accurately, sometimes not.

Any suggestions?

Henry Rich

 
 
 

Need 1/sqrt(x) for simple machine

Post by Joe Landma » Wed, 17 May 1995 04:00:00



>I have a simple machine (i. e. only add/subtract, but with support
>for recoded multiplication and nonrestoring division).  I need to
>calculate 1/sqrt(x), sometimes accurately, sometimes not.

>Any suggestions?

>Henry Rich

Use Newtons Method(if you dont mind a slow algorithm code)

You are solving f(x) = x^2

which can be cleverly written as f(x) - x^2 = 0

newtons method for solving this says for guess x(i+1) use

x(i+1) = x(i) - f(x(i))/(f'(x(i)))

and iterate until x(i+1) - x(i) is smaller than some tolerance (epsilon)

where f' is just the functional derivative (which is 2 x in this case).

Check this out in Numerical Recipes under root finders.
(I may be wrong about the division, the derivative may be on top)

Joe

--
Joe Landman   Systems Engineer                        |
Silicon Graphics, 24155 Drake Rd, Farmington MI 48335 |  {}{}-------{}{}
voice: (810) 615 2169                                 |       \ O /
  fax: (810) 478 3181                                 |        | |

------------------------------------------------------+       /   \
                                                            _|     |_

 
 
 

Need 1/sqrt(x) for simple machine

Post by Herman Rub » Thu, 18 May 1995 04:00:00





>>I have a simple machine (i. e. only add/subtract, but with support
>>for recoded multiplication and nonrestoring division).  I need to
>>calculate 1/sqrt(x), sometimes accurately, sometimes not.
>>Any suggestions?
>>Henry Rich
>Use Newtons Method(if you dont mind a slow algorithm code)
>You are solving f(x) = x^2
>which can be cleverly written as f(x) - x^2 = 0
>newtons method for solving this says for guess x(i+1) use
>x(i+1) = x(i) - f(x(i))/(f'(x(i)))
>and iterate until x(i+1) - x(i) is smaller than some tolerance (epsilon)
>where f' is just the functional derivative (which is 2 x in this case).

But the question was 1/sqrt(x).  One can do much better here for speed,
and it is even possible to get some additional speedup.

The equation now is a*x^2 - 1 = 0.  The derivative is 2*a*x, which is
2/x at the true value.  This eliminates division entirely (one only needs
a first-order approximation to the derivative), and is often used for that
reason, even to get sqrt(a) = a*x.  It is also possible to modify this to
get third (or higher) order methods.
--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399

On vacation until June 2

 
 
 

Need 1/sqrt(x) for simple machine

Post by Terje Mathise » Fri, 19 May 1995 04:00:00



>I have a simple machine (i. e. only add/subtract, but with support
>for recoded multiplication and nonrestoring division).  I need to
>calculate 1/sqrt(x), sometimes accurately, sometimes not.

For the fast/approximate value, I'd use a lookup table.  Since the
reverse function is easier to calculate (x = 1 / (y * y), it might be
useful to use this as the starting point for an iteration to get a more
accurate result, but this depends a lot on what sort of accuracy you
need, and on the relative speeds of add/sub vs mul and div.

--

"almost all programming can be viewed as an exercise in caching"

 
 
 

Need 1/sqrt(x) for simple machine

Post by Nick Maclar » Sun, 21 May 1995 04:00:00




>I have a simple machine (i. e. only add/subtract, but with support
>for recoded multiplication and nonrestoring division).  I need to
>calculate 1/sqrt(x), sometimes accurately, sometimes not.

Yes, no problem.  To solve a = 1/sqrt(b), use Newton-Raphson on
(1-1/(a*x^2)).  By using that form, you need no divisions (except by 2).
This was the form used before hardware division became common, and is
still much faster on machines with very slow division.

If your multiplication is VERY slow, you can play some quite interesting
games with series expansions, but they aren't usually worth the effort.

Nick Maclaren,
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.

Tel.:  +44 1223 334761    Fax:  +44 1223 334679

 
 
 

1. Simple Simple C-source for AT90s8515 set/clear LED for STK200 needed

Hi Folks!

I have cut'n'paste from various sample/skeleton files I have found and made
the following example:

<>
#include <avr/io.h>
#include <avr/interrupt.h>
#include <avr/signal.h>

int main(void) {
  outp(0xFF,DDRB);  /* port B is output (DDRx = 1) */
  outp(0x00,DDRD);  /* port D is input  (DDRx = 0)*/

  while(1){
   if (bit_is_set(PIND,4)){
    //PORTB=1;
    sbi(PORTB,0);
   }
   else{
    //PORTB=0;
    cbi(PORTB,0);
   }
  }
<>

But compiling and flashing it, dont make my LEDs flash on the STK200 board.
The jmp-blocks for led and switch's on the stk200 are all closed (mounted)!
I have studied the assembling code (.lst-file) and it seams OK.

Hmmm the code is made using WinAVR ...
I have tried setting hole port, as well as a single bit
What am I missing ?

regards,
jk

2. Scheduled Task Log File

3. simple architecture machine instruction set

4. FS Challenge XL

5. Simple SAN Solution needed

6. Problem w/ Security and IIS

7. Need simple interface to guarantee limit max voltage swing

8. Outlook 2000 Problem

9. Newbie needs a SIMPLE RS232 send & recive function for a 2051 (C51-Core)

10. Multi media Card simple file system need

11. Need a very simple CANbus module

12. Need a simple USB interface for your micro?

13. Need simple serial protocol between 2 micros