LUT versus Newton-Raphson Division For IEEE-754 32-bit Floating Point

Question

I was wondering what are the tradeoffs when implementing 32-bit IEEE-754 floating point division: using LUTs versus through the Newton-Raphson method?

When I say tradeoffs I mean in terms of memory size, instruction count, etc.

I have a small memory (130 words (each 16-bits)). I am storing upper 12-bits of mantissa (including hidden bit) in one memory location and lower 12-bits of mantissa in another location.

Currently I am using newton-raphson division, but am considering what are the tradeoffs if I changed my method. Here is a link to my algorithm: Newton's Method for finding the reciprocal of a floating point number for division

Thank you and please explain your reasoning.

It depends on the platform, and the level of accuracy required. — Oliver Charlesworth, Apr 02 '12 at 17:57
Why is this tagged [tag:c] and [tag:c++]? You hardly have to think about such fundamental things unless programming in assembly, do you? — leftaroundabout, Apr 02 '12 at 17:59
@leftroundabout: some processors simply don't have floating point, but still have a C compiler — peterchen, Apr 02 '12 at 18:02
@starbox usually you can just compile with an /fp:strict type command and get "perfect" IEEE-754 floating point compliance. I can't think of a C compiler that can't emulate floating point for you. — std''OrgnlDave, Apr 02 '12 at 18:02
@starbox it depends, how fast is multiplication? How fast is a lookup from a big table? Which LUT-using division algorithm are you planning to use anyway? — harold, Apr 02 '12 at 18:08
@starbox: This question is impossible to answer unless you can tell us something about the platform you're coding this for. — Oliver Charlesworth, Apr 02 '12 at 18:09
@starbox Well, that's small alright. Isn't the usual bit-by-bit restoring division algorithm good enough? — harold, Apr 02 '12 at 18:14
@starbox http://en.wikipedia.org/wiki/Division_%28digital%29#Restoring_division — harold, Apr 02 '12 at 18:17
@harold, it says it operates on fixed-point numbers. Also, D — Veridian, Apr 02 '12 at 18:19

score 4 · Answer 1 · edited May 23 '17 at 11:45

The trade-off is fairly simple. A LUT uses extra memory in the hope of reducing the instruction count enough to save some time. Whether it's effective will depend a lot on the details of the processor -- caching in particular.

For Newton-Raphson, you change X/Y to X* (1/Y) and use your iteration to find 1/Y. At least in my experience, if you need full precision, it's rarely useful -- it's primary strength is in allowing you to find something to (say) 16-bit precision more quickly.

The usual method for division is a bit-by-bit method. Although that particular answer deals with integers, for floating point you do essentially the same except that along with it you subtract the exponents. A floating point number is basically A*2^N, where A is the significand and N is the exponent part of the number. So, you take two numbers A*2^N / B * 2^M, and carry out the division as A/B * 2^N-M, with A and B being treated as (essentially) integers in this case. The only real difference is that with floating point you normally want to round rather than truncate the result. That basically just means carrying out the division (at least) one extra bit of precision, then rounding up if that extra bit is a one.

The most common method using lookup tables is SRT division. This is most often done in hardware, so I'd probably Google for something like "Verilog SRT" or "VHDL SRT". Rendering it in C++ shouldn't be terribly difficult though. Where the method I outlined in the linked answer produces on bit per iteration, this can be written to do 2, 4, etc. If memory serves, the size of table grows quadratically with the number of bits produced per iteration though, so you rarely see much more than 4 in practice.

@starbox: That can easily be satisfied by normalising N and D. — Oliver Charlesworth, Apr 02 '12 at 18:27
@OliCharlesworth, loss of precision would occur I believe. Can you normalize and guarantee results that 100% match the ieee-754 standard for 32-bit numbers? — Veridian, Apr 02 '12 at 18:53
@starbox: Given that the hardware implementation of IEEE 754 on most modern processors does use SRT, I'm pretty sure it *can* be done, though it's not necessarily trivial. — Jerry Coffin, Apr 02 '12 at 19:00

score 3 · Accepted Answer · edited Feb 16 '16 at 17:17

3

Each Newton-Raphson step roughly doubles the number of digits of precision, so if you can work out the number of bits of precision you expect from a LUT of a particular size, you should be able to work out how many NR steps you need to attain your desired precision. The Cray-1 used NR as the final stage of its reciprocal calculation. Looking for this I found a fairly detailed article on this sort of thing: An Accurate, High Speed Implementation of Division by Reciprocal Approximation from the 9th IEEE Symposium on Computer Arithmetic (September 6-8, 1989).

edited Feb 16 '16 at 17:17

Evil Dog Pie

2,300
2
23
46

answered Apr 02 '12 at 19:49

mcdowella

19,301
2
19
25

2

Yes, LUT vs. Newton-Raphson is not an either/or, it's a both/and. – comingstorm Apr 02 '12 at 22:07
1

I concur with comingstorm that a combination of a small LUT for the initial approximation followed by a converging iteration (does not have to be Newton's) usually works best. As I pointed out in response to your previous question about FP division, Newton iteration (which has quadratic convergence) may not be the best choice. I therefore recommended looking into a combination of a 256 byte lookup table plus cubically convergent iteration for single-precision divison: http://stackoverflow.com/questions/9011161/how-to-implement-floating-point-division-in-binary-with-no-division-hardware-and – njuffa Apr 03 '12 at 18:25
@mcdowella I tried the link but the web page is not available . Can you please give the name of the document so that I can read about it ? – chitranna May 20 '14 at 22:58
The page I referred to was a freely available copy of "An accurate, high speed implementation of division by reciprocal approximation" by Fowler, D.L. - for which the IEEE wants to charge me $31. There is also historical information on the CRAY-1 implementation at http://code.google.com/p/cray-1x/source/browse/trunk/Verilog/float_recip.v?spec=svn8&r=8, which suggests that they did indeed use an 8-bit lookup followed by reciprocal iteration. – mcdowella May 21 '14 at 05:13

LUT versus Newton-Raphson Division For IEEE-754 32-bit Floating Point

2 Answers2