0

I'm a computer engineering student and I have a design problem. I'd like to be able to use a numerical method to find the square root of a number with only logic gates on a physical hardware level and I'm restricted to binary numbers.

If I set $f(x) = x^2 - a$ then by Halley's method we obtain that $x_{n+1}=\frac{x_{n}^{3}+3 a x_{n}}{3x_{n}^{2}+a}$.

After some simplification using polynomial long division I've gotten this down to $x_{n+1}=\frac{x_{n}}{3}+(\frac{8}{3})(\frac{1}{\frac{1}{x_{n}}+\frac{3x_{n}}{a}})$

I would like to use Halley's method because it has quite rapid convergence, faster than the simpler form of Newton's method and use the IEEE 754 floating point standard.

Are there any other manipulations that I can do to this to reduce the complexity or size of the numbers used in each iteration?

I would like to keep $x_{n}$ as a power of one. If there is an area of mathematics that I can study these methods in more detail I would appreciate you pointing me in that direction.

jake mckenzie
  • 343
  • Did you mean to write $f(x) = x^2 - a$? – John Barber Dec 28 '17 at 06:19
  • @jakemckenzie Have you tried the Babylonian method? This method is simple to understand, yet converges quickly - for any number the second iteration has an error of $2^{-5}$, the third has $2^{-11}$, and the fourth has $2^{-23}$. – Toby Mak Dec 28 '17 at 06:21
  • What do you mean by "8 bits"? – marty cohen Dec 28 '17 at 06:24
  • @JohnBarber Yes I did. – jake mckenzie Dec 28 '17 at 07:05
  • @martycohen by 8 bits I mean the binary representation of the number. An 8 bit binary number can represent ever positive integers from 0 to 256. 0 is the binary number 00000000 and 256 is 11111111 With the IEEE 754 floating point standard it becomes a bit more complicated depending on how you want to represent your numbers. – jake mckenzie Dec 28 '17 at 07:08
  • @TobyMak I have looked into the Babylonian method, I decided this was a poor method for me as this will be represented on the hardware. I have to find an algorithmic way of picking my guesses in a smart way and decided that it was actually more complicated than these other numerical methods for that reason. There are smart algorithmic ways of picking my guess in halley's method but none that I know of for babylonian method. – jake mckenzie Dec 28 '17 at 07:16
  • You say "a poor method" ?! But it converges very quickly as well (all right you need maybe 5 iterations instead of 3), and the recurence is simpler. You should consider that Halley's method, as all other cousin methods of Newton's method, is very seldom used... – Jean Marie Dec 28 '17 at 08:07
  • @jakemckenzie One way to 'guess' the first digit is to 'sandwich' it between two squares - for example, $1600 < 1989 < 2500$, so $\sqrt{1989}$ has a leading digit of $4$. This will probably cut down one or two iterations. – Toby Mak Dec 28 '17 at 09:34
  • I was incorrect with what I said about the Babylonian method about the two guesses. Sorry I've been working all day and didn't think before I typed. – jake mckenzie Dec 28 '17 at 11:15
  • @TobyMak I didn't think of that but I'll start constructing tables of squares. I found a statistician who claims that on the average most roots lead with a 2 or 7 so they make good numbers to make your guess. I'll run some tests to see how true this is in practice. – jake mckenzie Dec 28 '17 at 11:20
  • Part of the reason I'm making this is that I've can't find anyone who has ever done it in practice. I don't even know if it's a worthwhile expenditure. Most square root functions that I've found implemented on a hardware level are based on lookup tables or a practice of "bit shifting" which does not seen optimal. If this is better I'd like to build it then write about it so that others can use the design. – jake mckenzie Dec 28 '17 at 11:24
  • If you access the bit level, then the best fast approximation of $x=2^{2k}(1+m)$ is $\sqrt x\approx 2^k(1+m/2)$ and of $x=2^{2k-1}(1+m)=2^{2k}(1-(1-m)/2)$ is $\sqrt x\approx 2^k(1-(1-m)/4)=2^{k-1}(1+(1+m)/2)$. After that you most likely will want to use a largely division-free method, as division is the most costly arithmetic operation. One often used method is the Newton method for $f(x)=ax^{-2}-1$. – Lutz Lehmann Jun 09 '18 at 16:11

0 Answers0