EEVblog Electronics Community Forum
Electronics => FPGA => Topic started by: hamster_nz on January 22, 2020, 04:26:24 am

I just stumbled onto Goldschmidt Division while reading about old IBM Model 360 systems. Maybe othera here might find it interesting in it too.
https://lauri.xnvsandipxa.com/hdl/arithmetic/goldschmidtdivisionalgorithm.html

Couple of quick comments:
(1) its a variant of the Newton Raphson algorithm, useful for solving many algebraic problems iteratively
(2) As its iterative, its very suited to pipelining.

Couple of quick comments:
(1) its a variant of the Newton Raphson algorithm, useful for solving many algebraic problems iteratively
(2) As its iterative, its very suited to pipelining.
(As always) Wikipedia has a section on it, that describes it quite well... sort of like the "CORDIC" of division algorithms, works by forcing the denominator to one.
https://en.wikipedia.org/wiki/Division_algorithm#Goldschmidt_division

Reviving this thread...
I'm considering implementing this in VHDL.
Has any of you already done this? Any tips? I've read about it, and the base algorithm seems simple enough, but properly implementing it in an HDL with pure integers, without losing precision, is not as trivial as it looks  my goal is to use it not to implement FP division, but integer division, so obviously the integer quotient needs to be exact.
A cool idea, if anyone's interested, is that we could share a working solution once we get to one. If I get there, I'll share it.

In my shared folders, I found this comment by a colleague
#tail @work\hdl\reasearch\alu\div\divider_goldschmidt_v0.0.1\tb\readme.txt
 Goldschmidt, v0.0.1
 convergence algorithm
 sequential division

 x = xn.xn1, x0: 1 <= x < 2
 y = yn.yn1, y0: 1 <= y < 2
 q = x/y
 m steps
 internally: p bits, p > n

 TestBench 2015/11/5:
 Generates Random cases, 2115 evaluated cases != 2500 expected cases
 test report: NOT WORKING!
It was explicit.

I don't know exactly what didn't work in the above.
The Goldschmidt division itself is a working way of implementing division, and used in a number of processors.
Question: is it actually unpractical for pure integer division, and to be restricted to FP division only?
If so, is there any other algorithm for pure integer division that takes fewer steps than the common restoring or nonrestoring division, which basically take n steps (or n+1 for the latter I think), with n the number of bits?

Question: is it actually unpractical for pure integer division, and to be restricted to FP division only?
Yes, probably it's abandoned not because it's impossible, but rather because he must have thought it was not worth it for just an integer division.
 divider_gm22
 unsigned divisor
 dividend
  = { quotient, remainder }
 divisor
I mean, the next folder I see is the classic "old school" integer division.
2200 test cases: 100% passed.

Yeah. A typical way of doing integer division in fewer cycles is to use a radix higher than 2. I guess this is what probably makes the most sense.
Still wondering whether we could use the Goldschmidt division  properly  for even fewer cycles, but come to think of it, I now doubt it.