Author Topic: Goldschmidt Division  (Read 740 times)

0 Members and 1 Guest are viewing this topic.

Offline hamster_nz

  • Super Contributor
  • ***
  • Posts: 2338
  • Country: nz
Goldschmidt Division
« 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
Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 
The following users thanked this post: jancumps

Offline ralphrmartin

  • Frequent Contributor
  • **
  • Posts: 351
  • Country: gb
    • Work website
Re: Goldschmidt Division
« Reply #1 on: January 22, 2020, 04:59:35 pm »
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.
 

Offline hamster_nz

  • Super Contributor
  • ***
  • Posts: 2338
  • Country: nz
Re: Goldschmidt Division
« Reply #2 on: January 23, 2020, 03:34:53 am »
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
« Last Edit: January 23, 2020, 03:44:41 am by hamster_nz »
Gaze not into the abyss, lest you become recognized as an abyss domain expert, and they expect you keep gazing into the damn thing.
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 5495
  • Country: fr
Re: Goldschmidt Division
« Reply #3 on: May 18, 2020, 03:11:03 pm »
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.
« Last Edit: May 18, 2020, 03:13:04 pm by SiliconWizard »
 

Offline 0db

  • Frequent Contributor
  • **
  • Posts: 315
  • Country: zm
Re: Goldschmidt Division
« Reply #4 on: May 18, 2020, 03:38:03 pm »
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.
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 5495
  • Country: fr
Re: Goldschmidt Division
« Reply #5 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?
 

Offline 0db

  • Frequent Contributor
  • **
  • Posts: 315
  • Country: zm
Re: Goldschmidt Division
« Reply #6 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.
 

Online SiliconWizard

  • Super Contributor
  • ***
  • Posts: 5495
  • Country: fr
Re: Goldschmidt Division
« Reply #7 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.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf