# EEVblog Electronics Community Forum

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

Title: Goldschmidt Division
Post 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.xn--vsandi-pxa.com/hdl/arithmetic/goldschmidt-division-algorithm.html
Title: Re: Goldschmidt Division
Post by: ralphrmartin on January 22, 2020, 04:59:35 pm
(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.
Title: Re: Goldschmidt Division
Post by: hamster_nz on January 23, 2020, 03:34:53 am
(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
Title: Re: Goldschmidt Division
Post by: SiliconWizard on May 18, 2020, 03:11:03 pm

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.
Title: Re: Goldschmidt Division
Post by: 0db on May 18, 2020, 03:38:03 pm
In my shared folders, I found this comment by a colleague

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.
Title: Re: Goldschmidt Division
Post by: SiliconWizard on May 18, 2020, 03:53:30 pm
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?
Title: Re: Goldschmidt Division
Post by: 0db on May 18, 2020, 04:26:19 pm
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.
Title: Re: Goldschmidt Division
Post by: SiliconWizard on May 18, 2020, 05:59:42 pm
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.