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.
Reply by Randy Yates●November 20, 20032003-11-20
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
Reply by Bernhard Holzmayer●November 18, 20032003-11-18
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
Reply by Vladimir Vassilevsky●November 18, 20032003-11-18
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
Reply by Julius Kusuma●November 17, 20032003-11-17
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
Reply by Clay S. Turner●November 17, 20032003-11-17
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
>
>
Reply by Luca Baradel●November 17, 20032003-11-17
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