From: Lynn Killingbeck Subject: Re: Approximations Date: Thu, 31 Aug 2000 15:50:06 -0500 Newsgroups: sci.math.num-analysis,sci.math Summary: Approximating square roots with primitive circuitry (AOI gates) [Many levels of nested quotes reformatted --djr] In article <39a25a23@news2lo.highwayone.net>, "ajd" wrote: > > Does anyone know of any approximations to the square root function that are > more computationaly efficient. (I need to it for implementation in hardware). "Christian Bau" wrote in message news:christian.bau-2308001015440001@christian-mac.isltd.insignia.com... > For a fast floating point square root: Find an approximation for 1 / sqrt > (a) with lets say 12 bit precision, using some table lookup from the > mantissa and calculating the exponent from the exponent of a. > > Then take the function f (x) = 1/x^2 - a = 0 which has the solution 1 / > sqrt (a). To improve an existing approximation x, you calculate > > x - f (x) / f' (x) = x - (x^-2 - a) / (-2 x^-3) > > = x + 1/2 (x - a x^3) > > One iteration step gives about 23 bits of precision. Multiply that > approximation of 1 / sqrt (a) by a. Of course you need a fast multiplier, > but that should be no problem. > > You do realise that dedicated hardware for square root calculation is > going out of fashion because software is much more efficient? Examples: > PowerPC, Athlon, Altivec, Itanium processors. ajd wrote: > > Thanks for the adivce, I need the square root in hardware as it part of a > larger design running on an embedded system with no processor. "Lynn Killingbeck" wrote in message news:39A57B9B.2E79@pointecom.net... > > No processor?! Of any kind? :-) > > If the chip you are using is at all common, this problem has likely been > solved before for that specific hardware. I don't know how to run down > that kind of data, though. Perhaps through the manufacturer? ajd wrote: > > I'm running it on an embedded system with no processor - of any kind! The > main hardware is an FPGA (a reconfigurable chip which can eliminate the need > for a processor) which I am writing the application for, hence i needed the > advice to write the hardware - no option of going to the manufacturer! > Specific hardware designs often speed up algorithms wqhen compared to > software.(After all - what does your software run on?) > > thanks again > ajd Just to see if I could still work at this level, here is an approach to getting sqrt(I), using nothing but AOI (And, Or, Invert) logic gates, where the input is a 4-bit unsigned integer and the output is a 4-bit unsigned number with two integer bits to the left and two fraction bits to the right of the implicit binary point. If you have to extend it much beyond 4 bits, I hope you have some computer-assisted tools to help with the logic expression and gate minimization, a rather tedious and error-prone exercise when done manually for many input and output bits. Rounded to the nearest bit, something else which may or may not be your requirement. I sqrt(I) 0000. 00.00 0001. 01.00 0010. 01.10 0011. 01.11 0100. 10.00 0101. 10.01 0110. 10.10 0111. 10.11 1000. 10.11 1001. 11.00 1010. 11.01 1011. 11.01 1100. 11.10 1101. 11.10 1110. 11.11 1111. 11.11 Label the input bits (I0,I1,I2,I3) from the left. Label the output bits (R0,R1,R2,R3) from the left. Use ' to denote the complement. By inspection, R0=(I0 OR I1) (R0 is 1 when (inclusive-or) I0 or I1 is 1.) R1=(I0 AND NOT (I0 AND I1' AND I2' AND I3')) OR (R0' AND NOT (I0' AND I1' AND I2' AND I3')) (R1 is 1 when I0 is 1, except when I=1000; R1 also is 1 when R0 is 0, except when I=0000.) (Note: R1 can be improved by regrouping. Left as an exercise!) I'll leave the logic-gate (And, Or, Invert) expressions for R2 and R3 as a routine exercise. At the time I did such exercises in college, I would have been drawing Karnaugh maps to manually find the minimal expressions. In practice, even then there were computer programs for minimizing the number of gates (if that is your constraint), for minimizing ripple effects (if that is your constraint), and for working with the popular exclusive-or family of gates (if those are available to you). Lynn Killingbeck