Division algorithm#Goldschmidt division

Goldschmidt division is a method to realize a division in a digital circuit is fast and with low hardware complexity. In this case the division is fed back to a multiplier, which multiplier may already present can also be used.

The approach of the Goldschmidt- division is the consideration of the division as a fraction which is expanded with a factor of as long until the denominator has converged close enough to the value 1. The value of the counter thus corresponds then the result of the division.

The steps are:

Are and scaled so that, then the expansion factors can be easily calculated:

This results in:

After a sufficiently large number of iterations is the desired quotient.

In the implementation of the circuit as a multiplication of the denominator and numerator can be performed in parallel, which allows a fast processing of the algorithm. The Goldschmidt division is used in the AMD Athlon CPUs and later models.

Binomial formula

The factors of the Goldschmidt- division may be selected so that a simplification of the binomial formula is possible.

Suppose was scaled by a power of 2 that.

We set and.

Then:

Since we can round to 1 by steps. The maximum relative error is and we obtain an accuracy of digital points. This algorithm is referred to as the IBM method.

Similar procedures

Also in computer technology the SRT division is employed.