Goldschmidt Division

[hamster_nz]

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.xn--vsandi-pxa.com/hdl/arithmetic/goldschmidt-division-algorithm.html

[ralphrmartin]

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.

[hamster_nz]

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

[SiliconWizard]

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.

[0db]

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

Code: [Select]

-- Goldschmidt, v0.0.1
-- convergence algorithm
-- sequential division
--
--        x = xn.xn-1, x0: 1 <= x < 2
--        y = yn.yn-1, 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.

[SiliconWizard]

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 non-restoring division, which basically take n steps (or n+1 for the latter I think), with n the number of bits?

[0db]

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.

Code: [Select]

-- 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.

[SiliconWizard]

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.