Forums

Division

Started by Luca Baradel 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





"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.