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

**posted on**

- tinkertoy51

June 1, 2005, 1:05 pm

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

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

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

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

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

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:

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>

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.

#### Site Timeline

- » Reverse current into a lithium battery
- — Next thread in » Embedded Programming

- » MP3 files on MMC
- — Previous thread in » Embedded Programming

- » Use of soft float?
- — Newest thread in » Embedded Programming

- » Plug&Play solution to reach an embedded HTTP server under a router
- — Last Updated thread in » Embedded Programming

- » Amatorskie projekty mikroprocesorowe przed AVR-ami i 8051
- — The site's Newest Thread. Posted in » Electronics (Polish)

- » S-Video ale z dzwiekiem.
- — The site's Last Updated Thread. Posted in » Electronics (Polish)