How to compute reciprocal without DIV

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

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

integer-only and reciprocals are pretty orthogonal concepts...

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:

The C code should be easily converted to assembler.

Rufus

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 n=16, 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.

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

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

see section 3

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

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?