1
$\begingroup$

I'm looking for a way to compute the reciprocal of a binary number. The numbers are fractions, but that doesn't really matter. Therefore we can think of any number involved as $N \geq 0$.

The idea is to make an approximation by doing the following. If we are taking the reciprocal of $N$, then we want $\frac{1}{N}$. However, we can approximate $\frac{1}{N}$ as $\frac{A}{2^n}$. Then are want to make this as close as possible:

$$ 1 \approx \left( \frac{N}{2^n}\right) A $$

Implementing a digital combinational circuit for the operation $\frac{N}{2^n}$ is really simple, since all that is required is an $n$ bit right shifter. Let's denote $N$ with $n$ bit shifts to the right as $\overrightarrow{N_n}$, just for the sake of abbreviation. Now all that's left to do is make the sum $S = \sum ^ A \overrightarrow{N_n}$ until $S > 1$.

To make this whole thing faster, we could just right shift until $N < 1$. Then we add $\overrightarrow{N_n}$ until the condition $\frac{A}{2^n} > 1$ is "barely met".

(Note that $1$ in this system looks like a power of $2$, $p>0$) Then, we stop. There we get an approximation with a small(?) error.

Is this method acceptable if I'm trying to implement Newton-Releigh in a digital circuit? The circuit will work with $16$ bits, and the clock runs at $50\ \text{MHz}$. If this algorithms is bad, is there another one that I could use to implement with similar implementation-complexity to this one?

Thanks!

$\endgroup$
  • $\begingroup$ I think you need "fixed point arithmetic". With google you will also find tutorials how to do this with VHDL. $\endgroup$ – user274886 Oct 31 '15 at 6:19
  • $\begingroup$ @Cryptostasis Great! If I can get VHDL to manage the reciprocals then I'm pretty much set and ready to go! Thank you. $\endgroup$ – Cehhiro Oct 31 '15 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.