Copy Link
Add to Bookmark
Report
A fast way to calculate the root square of a number using derivatives
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);
}
