Design Con 2015
Breaking News
Comments
Newest First | Oldest First | Threaded View
tom-ii
User Rank
Blogger
Re: Doing division
tom-ii   2/21/2014 3:52:51 PM
NO RATINGS
@betajet:

 

I was thinking specifically of Newton-Raphson (N-R).  Wikipedia covers the gory details of the theory behind it so I won't repeat it here.

 

Yeah, I have actually read through the whole thing.  I really like that it finishes in log(N) steps (if your special cases are handled, and you have a good initial guess).  The problem with it is the generalization to "any" implementation - I don't see a good way to package up an initial guess - I suppose I could just make it half of 2^N, but then it might not be saving me anything...  Of course this is because I want to generalize it for fixed-point.  I see that it may be a bit easier for floating point.

betajet
User Rank
CEO
Re: Doing division
betajet   2/21/2014 3:43:36 PM
NO RATINGS
I was thinking specifically of Newton-Raphson (N-R).  Wikipedia covers the gory details of the theory behind it so I won't repeat it here.

Basically, to do floating-point division with N-R, you want to find the reciprocal of the denominator D.  To use N-R, you first estimate the reciprocal X[0] and then refine the estimate using the N-R iteration X[i+1] = X[i] * (2 - D * X[i]) which has only multiples and adds.  Each iteration reduces the error quadratically, so if you start with an estimate that's accurate to 13 bits, one iteration gives you 26 bits (single precision) and two gives you 52 bits (double precision).  It you have high-speed multiplication hardware, this is a great way to go.

You find the initial estimate using a look-up ROM.  The denominator D is a binary floating-point number of the form M * 2^E, where mantissa M is between 0.5 and 1.0.  To calculate your first estimate X[0], look up the 12-16 MSbs of M in a ROM to get a number between 2.0 and 1.0, divided by 2 to renormalize it to between 0.5 and 1.0.  The exponent is easy: just negate it and add 1 to compensate for the mantissa look-up.  In other words, X[0] = XM * 2^(1-E) where XM is the value read from the ROM.

You need to handle some special cases:  If M is zero or an unnormalized fraction, 1/D is +infinity.  If D is +infinity, 1/D is +0.

There is also a good N-R iteration for calculating square roots.  In this case, you actually calculate 1/sqrt(x) and then multiply by x to get sqrt(x).

Integer square root using the "long division" method is also loads of fun.  It's a simplified form of the decimal "long division" method that was taught in USA public schools before 1950 and dropped once TV started to rot the minds of USA youth :-)

tom-ii
User Rank
Blogger
Re: Doing division
tom-ii   2/20/2014 7:26:34 AM
NO RATINGS
Actually, the next post doesn't talk about such things, and I am interested in your thoughts.  I know of the SVT algorithm, but haven't yet quite wrapped my mind around it.  I also took a look at Newton-Rhapson, but the need for a scaling factor throws me in that I haven't figured out how to make it generic - that is, if I instantiate a QN = 8,12. but want to then instantiate a QN=3,15, the scaling factors will need to be different (I think).

 

I'm interested in thoughts...

betajet
User Rank
CEO
Re: Doing division
betajet   2/19/2014 2:00:40 PM
NO RATINGS
If you have floating-point numbers, it's actually easier to do division.  The mantissas are already normalized, so you don't need the pre-shifting business, and floating-point uses sign/magnitude representation so you only need an XOR to take care of signs.

If you have fast multiplication hardware -- which you usually do nowadays -- you can use an extremely clever technique to calculate the reciprocal.  I think the author is working up to this, so I won't say more.

KarlS01
User Rank
Manager
Computer binary division
KarlS01   2/19/2014 1:36:43 PM
NO RATINGS
I am trying to remmember IBM 360/75 divide.

Dividend occupied even odd register pair to form 64 bit width  Divisor in third 32 bit register.

make both positive by complement if negative, remember if signs were different and make quotient negative at end

do a trial subtraction of divisor from high half of dividend, if positive write result into dividend and shift one into dividend low bit.  If negative result shift dividend left and zero into low bit.  (Aligns left bits and generates zero high quotient bits)

repeat 32 times(word width) so the 32 bit quotient is shifted into the low register of the dividend pair.  The shift and subtract reduces the dividend to a 32 bit remainder in the register that held the high order dividend 32 bits.

Note that shifting zero into the emptied bit of the dividend until the divisor can be successfully subtracted accomplishes the alignment of the operands while reducing the magnitude of the quotient. (As I already wrote...)

Multiples of the divisor (2x,4x, 5x?) were generated and decoding of dividend and divisor bits to generate multiple quotient bits to reduce cycles.  That is too complicated to remember.

The ALU and working registers were 64 bits for floating point so no big cost for divide and multiply 64 bit product.

tom-ii
User Rank
Blogger
Doing division
tom-ii   2/19/2014 12:07:34 PM
NO RATINGS
Nice and determistic, but not necessarily the fastest way?  Anybody out there got anything better? I'd like to hear it.

 



Most Recent Comments
Top Comments of the Week
Flash Poll
Like Us on Facebook

Datasheets.com Parts Search

185 million searchable parts
(please enter a part number or hit search to begin)
EE Life
Frankenstein's Fix, Teardowns, Sideshows, Design Contests, Reader Content & More
Max Maxfield

Tired Old iPad 2 vs. Shiny New iPad Air 2
Max Maxfield
6 comments
I remember when the first iPad came out deep in the mists of time we used to call 2010. Actually, that's only four years ago, but it seems like a lifetime away -- I mean; can you remember ...

<b><a href=Betajet">

The Circle – The Future's Imperfect in the Present Tense
Betajet
5 comments
The Circle, a satirical, dystopian novel published in 2013 by San Francisco-based writer Dave Eggers, is about a large, very powerful technology company that combines aspects of Google, ...

Martin Rowe

Make This Engineering Museum a Reality
Martin Rowe
Post a comment
Vincent Valentine is a man on a mission. He wants to make the first house to ever have a telephone into a telephone museum. Without help, it may not happen.

Rich Quinnell

Making the Grade in Industrial Design
Rich Quinnell
16 comments
As every developer knows, there are the paper specifications for a product design, and then there are the real requirements. The paper specs are dry, bland, and rigidly numeric, making ...

Special Video Section
The LT8640 is a 42V, 5A synchronous step-down regulator ...
The LTC2000 high-speed DAC has low noise and excellent ...
How do you protect the load and ensure output continues to ...
General-purpose DACs have applications in instrumentation, ...
Linear Technology demonstrates its latest measurement ...
10:29
Demos from Maxim Integrated at Electronica 2014 show ...
Bosch CEO Stefan Finkbeiner shows off latest combo and ...
STMicroelectronics demoed this simple gesture control ...
Keysight shows you what signals lurk in real-time at 510MHz ...
TE Connectivity's clear-plastic, full-size model car shows ...
Why culture makes Linear Tech a winner.
Recently formed Architects of Modern Power consortium ...
Specially modified Corvette C7 Stingray responds to ex Indy ...
Avago’s ACPL-K30T is the first solid-state driver qualified ...
NXP launches its line of multi-gate, multifunction, ...
Doug Bailey, VP of marketing at Power Integrations, gives a ...
See how to ease software bring-up with DesignWare IP ...
DesignWare IP Prototyping Kits enable fast software ...
This video explores the LT3086, a new member of our LDO+ ...
In today’s modern electronic systems, the need for power ...