# Division

Started by November 17, 2003
```Does anybody know any efficient algorithm to compute the inverse of a number
in a fixed point DSP? I have to perform the division and I have about 30
cicles to do it.
I thought that a good way is to do

a/b = a * inv(b).

Right now the inverse is computed by series approximation exploiting the log
properties, but I think there are far better ideas, like using somehow a
lookup table.

Any guess is welcome.

Luca

```
```Hello Luca,

You can use a seed (determined by you value of b) fed into a Newton-Raphson
algorithm for 1/b.

Clay

news:bpbptk\$h9q\$1@news.lsil.com...
> Does anybody know any efficient algorithm to compute the inverse of a
number
> in a fixed point DSP? I have to perform the division and I have about 30
> cicles to do it.
> I thought that a good way is to do
>
> a/b = a * inv(b).
>
> Right now the inverse is computed by series approximation exploiting the
log
> properties, but I think there are far better ideas, like using somehow a
> lookup table.
>
> Any guess is welcome.
>
> Luca
>
>

```
```most DSP manufacturers include application notes on how to do division
with their fixed-point DSPs.  i know TI does.  did you try looking there?
there is a clever way to do it, i remember.

julius

On Mon, 17 Nov 2003, Luca Baradel wrote:

> Does anybody know any efficient algorithm to compute the inverse of a number
> in a fixed point DSP? I have to perform the division and I have about 30
> cicles to do it.
> I thought that a good way is to do
>
> a/b = a * inv(b).
>
> Right now the inverse is computed by series approximation exploiting the log
> properties, but I think there are far better ideas, like using somehow a
> lookup table.
>
> Any guess is welcome.
>
> Luca
>
>
>

--
The most rigorous proofs will be shown by vigorous handwaving.
http://www.mit.edu/~kusuma

opinion of author is not necessarily of the institute
```
```
>
> Does anybody know any efficient algorithm to compute the inverse of a number
> in a fixed point DSP?

Determine the first guess by the table lookup, then use the Newton's
method for solving equation. That is faster then making a straight
division.

DSP and Mixed Signal Design Consultant

http://www.abvolt.com
```
```Luca Baradel wrote:

> Does anybody know any efficient algorithm to compute the inverse
> of a number in a fixed point DSP? I have to perform the division
> and I have about 30 cicles to do it.
> I thought that a good way is to do
>
> a/b = a * inv(b).
>
> Right now the inverse is computed by series approximation
> exploiting the log properties, but I think there are far better
> ideas, like using somehow a lookup table.
>
> Any guess is welcome.
>
> Luca

Don't forget to check these two:
1. if b is constant, do the inv(b) manually / at compile time.
2. check if your DSP has a function for the first guess.
there might be a sort of 8bit approximation for 1/x or so.

Bernhard
```
```Luca Baradel wrote:

> Does anybody know any efficient algorithm to compute the inverse of a number
> in a fixed point DSP? I have to perform the division and I have about 30
> cicles to do it.
> I thought that a good way is to do
>
> a/b = a * inv(b).
>
> Right now the inverse is computed by series approximation exploiting the log
> properties, but I think there are far better ideas, like using somehow a
> lookup table.
>
> Any guess is welcome.
>
> Luca

You do know that the direct method would only take 1 cycle per bit if
this is, e.g., a TI TMS 5xxx DSP, right? (See the SUBC instruction.)
30 cycles is a goodly amount of bits.
--
%% Fuquay-Varina, NC            %       'cause no one knows which side
%%% 919-577-9882                %                   the coin will fall."
%%%% <yates@ieee.org>           %  'Big Wheels', *Out of the Blue*, ELO
```
```Randy Yates <yates@ieee.org> wrote in message news:<IqYub.11311\$Wy4.5784@newsread2.news.atl.earthlink.net>...
>
> > Does anybody know any efficient algorithm to compute the inverse of a number
> > in a fixed point DSP? I have to perform the division and I have about 30
> > cicles to do it.
> > I thought that a good way is to do
> >
> > a/b = a * inv(b).
> >
> > Right now the inverse is computed by series approximation exploiting the log
> > properties, but I think there are far better ideas, like using somehow a
> > lookup table.
> >
> > Any guess is welcome.
> >
> > Luca
>
> You do know that the direct method would only take 1 cycle per bit if
> this is, e.g., a TI TMS 5xxx DSP, right? (See the SUBC instruction.)
> 30 cycles is a goodly amount of bits.

Whether you can achieve the desired precision for your quotient in 30
cycles depends on how many bits of precision you want. Usually you can
compute a 16 bit quotient it on most fixed point 16 bit DSPs with
single-cycle shift and add/subtract instructions, quite easily within
30 cycles.
The initial seed (the guess for the reciprocal) will determine how
fast the Newton-Raphson iterations converge. You can use a look-up
table to pick an appropriate seed value.

--Kal.
```