How to compute reciprocal without DIV

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Hello,
General question I can not seem to find anwser to using Google:
I am tinkering with a processor that has no DIV instruction, and am
wondering how to represent a reciprocal such that I can use MUL
instruction to perform div's.

The CPU is integer-only, 32bit. It has a small instruction set, but
does include the basics - add, sub, shl, shr, and so forth.

In my particular application, the divisor will always be only 16 bits.
External memory availability is not good, so I would prefer not to use
a table. By "not good", I mean A) there is only a few KB of available
memory, and B) access is slow due to architecture.
Speed is of some concern, and I am hoping that there is some "shortcut"
method that can be used. I can tolerate some degree of inaccuracy; +/-
1 at least. There is no FPU, and no support (nor need) for floating
point math.

In comp.lang.asm.x86 a kind gentleman pointed me to this page:
http://www.azillionmonkeys.com/qed/pentopt.html

There, I see this text:

"Dividing by a constant can be done by multiplying with the
reciprocal."

And this text:

"..you first calculate the reciprocal f = 2^r / d"

I don't understand the benefit of calculating a reciprocal if you need
to use a "div" instruction to get there. However, I have a poor math
foundation and am not an experienced programmer (quite the opposite!),
so perhaps I am simply missing the point there.

Any advice or suggestions appreciated.
TT


Re: How to compute reciprocal without DIV

Quoted text here. Click to load it

Do it with your calculator and insert the answer in the program. Or more
sensibly, your assembler (I assume it's not a compiler as that would
have the maths functions done for you already) can probably work it out
for you. Check the pseudo-ops. If you need to divide by a variable,
you'll have to implement a divide function using shift-and-subtract, or
successive approximation using multiply, or some such.

Paul Burke

Re: How to compute reciprocal without DIV
Hello Paul,

Thanks for your response.  Yes, I need to divide by a variable. There
is a value passed in one of the packet header words of a data packet on
the UTOPIA bus. Due to data rate, I'm hoping to find something quicker
than "longhand" method. Maybe this is not a reasonable approach, but I
thought if there was some "magic" shortcut to determining a reciprocal,
then I would not have to use a loop.

Thanks again.
TT


Re: How to compute reciprocal without DIV

Quoted text here. Click to load it

There is no magic shortcut unfortunately (*), calculating a reciprocal is
as hard as a full division. Calculating the reciprocal separately is only
beneficial if you can reuse it for several divisions (changing N divisions
into 1 reciprocal plus N multiplies) or if you can live with approximate
answers. Several division algorithms produce exact answers:

1. Division using shift&subtract - this only takes a few instructions per bit
   on most CPUs, so really quick for 32/16->16 division.

2. Newton Rhapson - complicated but quick if you have fast multiplies and
    count leading zero. Needs a lookup table.

3. Long division using a reciprocal estimate producing N bits per iteration.
    Less complicated then NR, slightly faster in some circumstances, but useful
    only if you have a fast multiplier and can afford a lookup table.

If you don't need exact answers than a reciprocal estimate lookup with linear
interpolation gives good results, especially if you don't need the full 32/16 bit
range. Performance wise this is always the fastest method. If the inaccuracy
is small (large table) then it is possible to produce exact answers by
calculating
the modulo and correct the result if it is out of range.

Wilco

(*) unless the divisor is a constant or a power of 2 of course



Re: How to compute reciprocal without DIV
Quoted text here. Click to load it

I'm sure you've already eliminated the possibility, but is it practical to
get the originator of the data to do the inversion before it's sent on
the bus?

--
Trevor Barton

Re: How to compute reciprocal without DIV

Quoted text here. Click to load it
integer-only and reciprocals are pretty orthogonal concepts...

Quoted text here. Click to load it

Dividing a 32 bit integer by a 16 bit integer, resulting in an integer
is not that big a problem, is it?

Do shifts and subtracts.

Or perhaps a binary search would be better?  Start out with a number
of a bitsize that's the difference in the bitsize of the two original
numbers and go from there.

In other words, if the dividend is 25 bits long, and the divisor 13, you
know the quotient will be 12 bits or less.


googling for "integer division" turned up this site, among others:

http://www.bearcave.com/software/divide.htm

The C code should be easily converted to assembler.

Rufus



Re: How to compute reciprocal without DIV

<snip>

Quoted text here. Click to load it

The key point here is that you are dividing by a *constant*.  You are
re-arranging your sum from:
    y = x / k
to
    y = (x * (2^n / k)) / (2^n)
where n is picked to make the ranges work out well with the sizes of
arithmetic you are working with.  Since you can use 32-bit arithmetic,
but only need 16-bit values, make n16%, and you can avoid overflows.
Thus if you want to divide by 6, you calculate (2^16 / 6) = 0x2aaa, and
then your "division" becomes a multiply by 0x2aaa, followed by a divide
by 2^16 (which is just a shift, or 32-bit store followed by a 16-bit load).

If you have a decent C compiler, it will generate such code for you.

Re: How to compute reciprocal without DIV
Quoted text here. Click to load it

you don't need to use a "div" instruction to get there

ftp://arith.stanford.edu/tr/divalgo_TOC.pdf

see section 3


Site Timeline