2
\$\begingroup\$

Does anyone know any available reference to learn how works CORDIC algorithm to implement a division?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I suppose you have already read the Wikipedia article? secure.wikimedia.org/wikipedia/en/wiki/Cordic \$\endgroup\$
    – starblue
    Jan 29, 2011 at 13:11
  • \$\begingroup\$ offcourse, but that article use trigonometric function to explain how it works. \$\endgroup\$
    – Peterstone
    Jan 29, 2011 at 13:32
  • \$\begingroup\$ This is more of a Stack Overflow kind of question \$\endgroup\$
    – Nayuki
    Jul 15, 2016 at 5:54

2 Answers 2

5
\$\begingroup\$

This is an excellent article written by someone on the Parallax forums, called CORDIC For Dummies. Well written and explains things nicely: http://forums.parallax.com/showthread.php?127241-CORDIC-for-dummies

\$\endgroup\$
1
  • \$\begingroup\$ I´ve just read and I agree with you, is an excellent and very clear article. \$\endgroup\$
    – Peterstone
    Feb 2, 2011 at 8:02
2
\$\begingroup\$

A CORDIC division is implemented using CORDIC multiplication, rearranging as follows: [source]

c = a/b
a - c*b = 0

For the multiplication z = x*y:

z is composed of shifted versions of y. The unknown value for z, may be found by driving x to zero 1 bit at a time. If the i th bit of x is nonzero, y i is right shifted by i bits and added to the current value of z. The i th bit is then removed from x by subtracting 2-i from x. If x is negative, the i th bit in the twos complement format would be removed by adding 2-i. In either case, when x has been driven to zero all bits have been examined and z contains the signed product of x and y correct to B bits.

This algorithm is similar to the standard shift and add multiplication algorithm except for two important features:

  1. Arithmetic right shifts are used instead of left shifts, allowing signed numbers to be used.
  2. Computing the product to B bits with the CORDIC algorithm is equivalent to rounding the result of the standard algorithm to the most significant B bits.

The division z = x/y is found...

... by driving x to zero using right-shifted versions of y. If the current residual is positive, the i th bit in z is set. Likewise, if the residual is negative the ith bit in z is cleared.

divide_4q(x,y){
   for (i=1; i=<B; i++){
      if (x > 0)
        if (y > 0)
           x = x - y*2^(-i);
           z = z + 2^(-i);
        else
           x = x + y*2^(-i);
           z = z - 2^(-i);
      else          
         if (y > 0)
            x = x + y*2^(-i);
            z = z - 2^(-i);
         else
            x = x - y*2^(-i);
            z = z + 2^(-i);
   }
   return(z)
}

You'll have to make a few modifications to use floating point numbers.

\$\endgroup\$
2
  • \$\begingroup\$ Since the Dr Dobb's website doesn't have all the detail, you can read the PDF at: siue.edu/~gengel/pdf/cordic.pdf \$\endgroup\$ Feb 24, 2015 at 6:53
  • 1
    \$\begingroup\$ NOTE: if the bit about driving a X to zero (in Z = X*Y) sounded confusing: you are adding a multiple of Y to Z, for each set bit in X. Keep adding to the running total, until you run out of bits in X. \$\endgroup\$ Feb 24, 2015 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.