## Need 1/sqrt(x) for simple machine

### Need 1/sqrt(x) for simple machine

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

>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

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

>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

>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

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