32 bit fixed point division

Hello All,

Can anyone please help me in writing a C code for dividing a 32 bit fixed
point number by another 32 bit number? I already have a code which works
fine for 16 bit (div_s) but it can not be converted to 32 bit. 
So please give me some source code or algorithm for implementing 32 bit
division.

Thanks and Regards,
bd.

		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

#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;
}

bsdap wrote:
> Can anyone please help me in writing a C code for dividing a 32 bit fixed
> point number by another 32 bit number? I already have a code which works
> fine for 16 bit (div_s) but it can not be converted to 32 bit.
> So please give me some source code or algorithm for implementing 32 bit
> division.

Is performance or accuracy important?  And if the former and you do
not need an exact result, does your target processor have a fast
multiply?


--
rhn

>bsdap wrote:
>> Can anyone please help me in writing a C code for dividing a 32 bit
fixed
>> point number by another 32 bit number? I already have a code which
works
>> fine for 16 bit (div_s) but it can not be converted to 32 bit.
>> So please give me some source code or algorithm for implementing 32
bit
>> division.
>
>Is performance or accuracy important?  And if the former and you do
>not need an exact result, does your target processor have a fast
>multiply?
>
>
>--
>rhn
>
>

Thanks for your reply,

I am intending to make this routine platform independent. And, yes,the
accuracy is most important for me. Can you please suggest me some idea for
this?

Thank you once again,
Regards,
bd 

		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

>#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;
>}
>
>

Hi Randy,
Thank you very much for this wonderful code. It minimised my problem to a
great extent.

Thanks again,

Regards
bd.

		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

Regarding the posted code

was it originally written for the ARM? It looks familiar. 

Plus: does anybody knows any portable for fixed-point arithmetic with
functions like sin,cos, sqrt, pow etc.

I have collected a few codes from here and there but i prefer
something moe adequate.

-kavi

>>#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;
>>}
>>
>>
>
>Hi Randy,
>Thank you very much for this wonderful code. It minimised my problem to
a
>great extent.
>
>Thanks again,
>
>Regards
>bd.
>
>		
>This message was sent using the Comp.DSP web interface on
>www.DSPRelated.com
>


Hay, can anyone please give a code for 32 bit fixed point division which
would work for a 32 bit DSP processor. It looks like this code will not
work, as it involves working with a 64 bit integer.

Thanks and Regards,
SB.



		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

sbhavikb wrote:
> >>   uint64_t remainder;
...
> >>      remainder = remainder << 1;
...
> Hay, can anyone please give a code for 32 bit fixed point division which
> would work for a 32 bit DSP processor. It looks like this code will not
> work, as it involves working with a 64 bit integer.

These operations on large unsigned integers can be broken down into
operations on sets of smaller integers.  For instance, a left
shift on a uint64 can be broken down into shifting two 32-bit integers,
plus copying the former MSB of one into the resulting LSB of the
other.  See any textbook on binary arithmetic or multi-precision
arithmetic.

So the earlier posted code will work just fine, with simple
modifications, not only for 32-bit processors, but for 16-bit and
8-bit CPU's as well.

And if you want a potentially faster multi-precision integer division
routine, look into non-restoring algorithms, which can save on some
comparison cycles.


IMHO. YMMV.
-- 
rhn A.T nicholson d.O.t C-o-M

"rhnlogic@yahoo.com" <rhnlogic@yahoo.com> writes:
> [...]
> So the earlier posted code will work just fine, with simple
> modifications, not only for 32-bit processors, but for 16-bit and
> 8-bit CPU's as well.

Why not perfectly as is? In other words, what portability issues
do you see? It seems that as long as we are talking ISO 99 C so
that the stdint library is available, we have everything we need.
-- 
%  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

Randy Yates wrote:
> "rhnlogic@yahoo.com" <rhnlogic@yahoo.com> writes:
> > [...]
> > So the earlier posted code will work just fine, with simple
> > modifications, not only for 32-bit processors, but for 16-bit and
> > 8-bit CPU's as well.
>
> Why not perfectly as is? In other words, what portability issues
> do you see? It seems that as long as we are talking ISO 99 C so
> that the stdint library is available, we have everything we need.

Guess my age is showing.  I worked too many years on systems
where one could not assume that either the system or the compiler
and its libraries would transparently support 64-bit operations.
In fact, in my junior engineer days, I remember having to develop
library support code for certain *16-bit* arithmetic operations
(maybe for Z80's and/or 6502's).

Maybe the OP is working on an antique DSP?  (More likely, they just
didn't check the C compiler manual...)


IMHO. YMMV.
-- 
rhn A.T nicholson d.O.t C-o-M