Division

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





"Luca Baradel" <lbaradel@lsil.com> wrote in message
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

Luca Baradel wrote:
> 
> 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.

Vladimir Vassilevsky

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.
-- 
%  Randy Yates                  % "...the answer lies within your soul
%% 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
http://home.earthlink.net/~yatescr

Randy Yates <yates@ieee.org> wrote in message news:<IqYub.11311$Wy4.5784@newsread2.news.atl.earthlink.net>...
> 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.

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.