Division in Fixed Point

Dear all,

Can anyone point me to some code how to implement a division in a Fixed 
Point DSP ?
(Just to see how it works to fit it in mine)

                            Thx, Wolfgang

"Wolfgang" <Never@nowhere.com> writes:

> Dear all,
>
> Can anyone point me to some code how to implement a division in a Fixed 
> Point DSP ?
> (Just to see how it works to fit it in mine)

http://groups.google.com/group/comp.dsp/browse_frm/thread/9a21147500a7ee03/87630d175dd965db?lnk=st&q=fixed+point+division&rnum=4&hl=en#87630d175dd965db

Or, repeated here:

#include <stdint.h>

uint64_t Divide32(uint32_t y, uint32_t x)
{
   uint16_t n;
   uint64_t answer;
   uint64_t remainder;
   uint64_t divisor;

   answer = 0;
   remainder = x;
   divisor = (uint64_t)y << 32;

   for (n = 0; n < 32; n++)
   {
      divisor = divisor >> 1;
      if (remainder >= divisor)
      {
         remainder -= divisor;
         answer |= (uint64_t)1 << (63 - n);
      }
   }

   for (n = 0; n < 32; n++)
   {
      remainder = remainder << 1;
      if (remainder >= divisor)
      {
         remainder -= divisor;
         answer |= (uint64_t)1 << (31 - n);
      }
   }

   return answer;
}



-- 
%  Randy Yates                  % "And all that I can do
%% Fuquay-Varina, NC            %  is say I'm sorry, 
%%% 919-577-9882                %  that's the way it goes..."
%%%% <yates@ieee.org>           % Getting To The Point', *Balance of Power*, ELO
http://home.earthlink.net/~yatescr

Many thanks, Randy.

Yes Google is your friend I was impressed how fast I got relatively good 
infos.

                                Thanks again, Wolfgang


"Randy Yates" <yates@ieee.org> schrieb im Newsbeitrag 
news:64pqebz5.fsf@ieee.org...
> "Wolfgang" <Never@nowhere.com> writes:
>
>> Dear all,
>>
>> Can anyone point me to some code how to implement a division in a Fixed
>> Point DSP ?
>> (Just to see how it works to fit it in mine)
>
> http://groups.google.com/group/comp.dsp/browse_frm/thread/9a21147500a7ee03/87630d175dd965db?lnk=st&q=fixed+point+division&rnum=4&hl=en#87630d175dd965db
>
> Or, repeated here:
>
> #include <stdint.h>
>
> uint64_t Divide32(uint32_t y, uint32_t x)
> {
>   uint16_t n;
>   uint64_t answer;
>   uint64_t remainder;
>   uint64_t divisor;
>
>   answer = 0;
>   remainder = x;
>   divisor = (uint64_t)y << 32;
>
>   for (n = 0; n < 32; n++)
>   {
>      divisor = divisor >> 1;
>      if (remainder >= divisor)
>      {
>         remainder -= divisor;
>         answer |= (uint64_t)1 << (63 - n);
>      }
>   }
>
>   for (n = 0; n < 32; n++)
>   {
>      remainder = remainder << 1;
>      if (remainder >= divisor)
>      {
>         remainder -= divisor;
>         answer |= (uint64_t)1 << (31 - n);
>      }
>   }
>
>   return answer;
> }
>
>
>
> -- 
> %  Randy Yates                  % "And all that I can do
> %% Fuquay-Varina, NC            %  is say I'm sorry,
> %%% 919-577-9882                %  that's the way it goes..."
> %%%% <yates@ieee.org>           % Getting To The Point', *Balance of 
> Power*, ELO
> http://home.earthlink.net/~yatescr 

Wolfgang wrote:

> Dear all,
> 
> Can anyone point me to some code how to implement a division in a Fixed 
> Point DSP ?
> (Just to see how it works to fit it in mine)
> 
>                             Thx, Wolfgang
> 
> 
All of the fixed point DSP chips that I have worked with have a divide 
primitive; it basically does one bit's worth of division and leaves the 
processor in a state to perform the next step with no intervening 
instructions -- so you can just repeat the thing once for each 
significant bit in your divisor.

So if you're doing this in assembly look in the instruction set 
reference; there should be examples.  If you're doing something like 
fractional fixed-point in C then do the divide itself in assembly -- 
it'll be much faster.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Yes, you're absolutely right about this, Tim. I chose to do it this
way on my DM642 project since I don't yet know the architecture
of this machine very well and, being a parallel machine it's a lot
more difficult to pick up than, e.g., the TMS32054x. The routine
is also invoked at a very low rate, so two to three times the
cycles of an assembly implementation isn't a problem.

--Randy

Randy Yates wrote:

> Yes, you're absolutely right about this, Tim. I chose to do it this
> way on my DM642 project since I don't yet know the architecture
> of this machine very well and, being a parallel machine it's a lot
> more difficult to pick up than, e.g., the TMS32054x. The routine
> is also invoked at a very low rate, so two to three times the
> cycles of an assembly implementation isn't a problem.
> 
> --Randy
> 
At a former employer I maintained a little library of fixed-point 
routines -- I had a couple of versions that were hand-optimized for 
their target processors, and one version that was written as close to 
the ANSI C++ spec as I could get that would compile and run correctly on 
nearly anything.

The portable version used long division pretty much like yours.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Dear Randy & Tim,

Many thanks, DM642 let my "ears ring".
Many thanks for the "assembly implementation" hint, now sitting in front of 
TI's
Integer Division document.

Do you also have a starting point on how to determine the angle of an 
X/Y-pair given in fixed point.
Is there a keyword for an algorithm I can google ?

                                Many thanks, Wolfgang

> Do you also have a starting point on how to determine the angle of an
> X/Y-pair given in fixed point.
> Is there a keyword for an algorithm I can google ?

take a look at http://dspguru.com/comp.dsp/tricks/alg/fxdatan2.htm

works fine for me

there is also magnitude estimator on the same site, if you need one

Mitja

Many thanks Mitja,

Very interesting case.
Thank you for the link.

                        Wolfgang

"Korenje" <korenje@yahoo.co.uk> schrieb im Newsbeitrag 
news:1134720961.351978.102620@g44g2000cwa.googlegroups.com...
>
>> Do you also have a starting point on how to determine the angle of an
>> X/Y-pair given in fixed point.
>> Is there a keyword for an algorithm I can google ?
>
> take a look at http://dspguru.com/comp.dsp/tricks/alg/fxdatan2.htm
>
> works fine for me
>
> there is also magnitude estimator on the same site, if you need one
>
> Mitja
> 

I also have used something similar to this with good results. Thanks
Jim for the trick!

--Randy


"Korenje" <korenje@yahoo.co.uk> writes:

>> Do you also have a starting point on how to determine the angle of an
>> X/Y-pair given in fixed point.
>> Is there a keyword for an algorithm I can google ?
>
> take a look at http://dspguru.com/comp.dsp/tricks/alg/fxdatan2.htm
>
> works fine for me
>
> there is also magnitude estimator on the same site, if you need one
>
> Mitja
>

-- 
%  Randy Yates                  % "How's life on earth? 
%% Fuquay-Varina, NC            %  ... What is it worth?" 
%%% 919-577-9882                % 'Mission (A World Record)', 
%%%% <yates@ieee.org>           % *A New World Record*, ELO
http://home.earthlink.net/~yatescr