A fast way to calculate the root square of a number using derivatives

@DrWatson

Published in

atari

· 11 months ago

Fast Square Root Doc

by Noble Roman

Ok, if you studied calculus you might already know this but lets say you need that square root of 23, and you have no calculator and you really need the answer. So you make

f(x) = \sqrt x

According to some differentiation rules you take f(x) and add it to the derivative of f(x) [ which is f'(x) ] and multiply it by dx. dx is the difference between x and some normal square close to x.

\sqrt{x} + \frac{dx}{\frac{2}{\sqrt{x}}}

From this you get a very close answer to the real one.

Lets do and example.

\sqrt{34}

36 is close to 34 and I know the square root of it which is 6.

So dx = x-36 which is -2

dx = -2

\sqrt{36} + \frac{-2}{ \frac{2}{\sqrt{36}}}

then

6 - \frac{1}{6}

and \sqrt{34} is approximately \frac{36 - 1}{6} = \frac{35}{6} = 5.83333
The Square root of 34 is really 5.83092, pretty close eh.

For more help or info, contact me at thomas@unix.cde.com

p.s.
if you need some help on fixed point math, write me and I will make a doc on that also.

SQRT.C

/* Fast Square Root using derivatives 
   Coded By Noble Roman / DiGiTaLuS 
   Email for questions thomas@unix.cde.com 
   Coded in DJGCC on March 9                   */ 

/* This function returns the Square Root of 
   the number given in 16.16 fixed point 
   math.  The number supplied must also be 
   in 16.16 fixed point math.  You must call 
   the table(); before using it.  The numbers 
   returned are not precise at all but will 
   work very well.  Numbers can range from 0 
   to 300.  You can increase this if you feel 
   the need. It is not optimized, since I 
   didn't feel like it.                        */ 

#include <pc.h> 
#include <stdio.h> 
#include <stdlib.h> 

unsigned long SQRTAB[17]; 

unsigned long SQRT(unsigned long NUM); 

unsigned long SQRT(unsigned long NUM) 
{ 
     unsigned int t,d; 
     unsigned long ANS,dx,e; 
     long c; 
     e=0xfff;     /* Big number so don't pick zero as then answer */ 
     dx=0;        /* If zero really is the answer :) */ 
     for(t=0;t<17;t++) 
     { 
          c=SQRTAB[t]-NUM; /* Make c the diff between t^2 and num */ 
          if(c & 65536)   /* Get the abs */ 
               c=c^65536; 
          if(c<e) /* If c is less than e then make d=t */ 
               d=t; 
          e=c;    /* Make e=c so we can find the closest match */ 
     } 
     dx=NUM-SQRTAB[d]; 
     d=d<<16; /* Make d fixed point */ 
     ANS=d; 
     ANS+=dx/(2*d); 
     return(ANS); 
} 

void table() 
{ 
     int t; 
     for(t=0;t<17;t++) 
     { 
          SQRTAB[t]=t*t; 
          SQRTAB[t]=SQRTAB[t]<<16; /* Make it 16.16 */ 
     } 
} 

unsigned int ABS(int a) 
{ 
     if(a & 65536) 
          a=a|65536; 
     return(a); 
}