algorithm - Digit recurrence square root -

i need implement digit recurrence square root generic floating point format such exp_size + mant_size + 1 <= 64.

i followed implementation suggested here handbook of floating point arithmetic in software implementation of floating point operator.

i've tried test implementation (not exhaustive test) , format 32 bit looks work fine, while format mantissa = 10, exponent = 5 input x = 0.25 instead give me 0.5 gives me apparently 0.707031.

so wandering if small format maybe digit recurrence approach has limits or not or... implementation bad...

i hope can me... it's pain implement stuff 0...

it extremly hard @ code should:

1. test operand combinations

   • if works single example not mean works of them

2. check bit masks

   • you wrote when use 32bit result fine
   • when use 10 not
   • that hinting overflow somewhere
   • are sure have right bit counts reserved/masked r?
   • r should 2 bits more q (+1 bit accuracy , +1 bit sign)
   • and should handle r twos complement
   • q half of d bits , unsigned

could not find algorithm (that book linked not allow me further page 265 sqrt starts may incompatibility use old opera) closest 1 found in google (non-restoring-sqrt) in pdf research , hw implementation on fpga , after clearing bugs , testing code in c++ , tested:

dword u32_sqrt(dword d) // 32bit     {     const int   _bits  =32;     const dword _r_mask=(4<<(_bits>>1))-1;     const dword _r_sign= 2<<(_bits>>1);     dword q=0; // u(_bits/2    ) result (quotient)     dword r=0; // i(_bits/2 + 2) 2os complement (remainder) r=d-q*q     (int i=_bits-2;i>=0;i-=2)         {         if (dword(r&_r_sign)){ r=(r<<2)|((d>>i)&3); r+=(q<<2)|3; }  // r< 0          else                { r=(r<<2)|((d>>i)&3); r-=(q<<2)|1; }  // r>=0         r&=_r_mask; q<<=1; if (!dword(r&_r_sign)) q|=1;             // r>=0         }     return q;     }