An Efficient Algorithm for Magnitude Operation
by S. Manivannan


Figure 1:
(a)
M(a,b) >= a,

(b)
M(a,b) <  a + 0.5b

(c)
 r2 = (M - a)2 = M2+ a2- 2*M*a  = 2*a2+ b2- 2*M*a;

(d)
b2= r2+ 2*a*r, ( 0 <= r < 0.5b)

(e)
(r + d) 2+ 2*a*(r+d) = (r2+ 2*a*r) + (d2+ 2*r*d + 2*a*d)

Figure 2:

Since a > b,
a  > (3/4)b
Multiply with b on both sides : ab > (3/4)b2
 ab + (1/4)b^2 > b2
Add a^2 on both sides  : a2+ ab + (1/4)b2 > a22 + b2
 (a + 0.5b)2 > M2
for 'a', 'b' integers,  M < (a + 0.5b)

Listing One
unsigned long imag(unsigned int a, unsigned int b)
{
 unsigned int  l, r, d;
 unsigned long d2, b2, R, D;
 R = 0;
 l = 0;
 b2 = 0;
 r  = b;
 do
 {
  d = 1L << l;
  if(b & d)
  {
   b2 += (b << l);
  }
  l++;    // find the number of bits in b
 }while(r >>= 1);
 l--;
 while(l --)
 {
  d   = 1L << l;   // setting the increment
  d2  = d << l;
  D   = d2 + ((a + r) << (l + 1));// D = d**2 + 2*r*d + 2*a*d;
  if((R + D) <= b2)
  {
   r += d;   // updating value of r.
   R += D;
  }
 }
 return (r + a);
}







1