hi! i need little help. my idea is to develop module for division of whole integers (signed, up to 32 bits) on fpga (Spartan-3A 200 for example). can you help me with some good start point? Basic algorithm differnt from “paper-and-pencil”?

Depending on your application and how fast this divider you want it to be, you could design an FSM wich will execute successives suscractions.

The book from Patterson and Hennessy ("Computer Organization & Design: The Hardware/Software Interface", Morgan Kaufmann) has the best introduction to integer division circuits I know of.

Hellwig

after research: non-restoring algorithm looks to be the best for implementation on fpga. Newton-Rapshon and Goldschmidt are interesting, but may be too slow (few iteration, few mult and sub). May be someone will share experience about N-R or GS?

The whole business of doing multiplication and division is not very difficult. If you are interested, you can find my implementation of these operations (32 bit, signed and unsigned) in the attachment. I used Verilog as HDL and extracted the 150 lines directly from my 32-bit CPU.

Newton-Raphson divide does not require multiplication. Two-bit per clock non-restoring divide is a pretty tight loop, a matter of adding or subtracting 0x, 1x, or 2x the divisor from the remainder.

With only 32-bit operands, a full-length carry chain isn't a huge delay in the loop. If you're trying to be very aggressive with pipeline clock rate, the algorithm for 2-bit divide is very friendly for optimisations. If you don't need to be clock-aggressive, then a simple add/sub should work nicely.

I designed the Bipolar Integrated Technology DP FP chipset in the 1980s (before the WWW), specifically the mult/div/sqrt device. There's lots of info readily available. I used Newton-Raphson 2-bit per cycle, and achieved 1GHz inner loop clock. I believe the best paper I could find on the algorithm was written by Greg Taylor (not the Greg Taylor who worked at B.I.T. and Intel, I think he worked at Sun... not sure).

This should get you going. Good luck, and happy hunting.

- Bob Elkind

A very good book is : Computer Arithmetic Algorithms, 2nd Edition from Israel Koren. Have a look into this book to see which algorithm you prefer.
The NR algorithm for division is a very good algorithm because you get after every cycle two bit more (accuracy). An other pro for this algorithm is that you can realise a division without a division unit. You need just multipliers (and adders) to make a division. If you need more information about the NR or some good IEEE paper links (papers are not free) ask again.
By the way the NR has one problem, you need a good initial guess. But it's solved.

I am also very interested in NR division, do you have any VHDL example of it?

Hi yyrr so you asked me for some examples. I think it is better to write his stuff by your self because you have to do some adaptations to your specific needs. Let me be a bit more precise... You have to decide which bus size you need it has to do with the precision of your approximation (division) and you have to specify the write initial guess calculation or generation. At the end you will maybe write (describe) your specific addeing and multiplying circuit.
So maybe I can help you a little bit in that process. If you like you can describe your project and on witch point it is.
Did your read the stuff in the book I advised. To you have access to ieee papers?