attempting to write a fixed point sqrt function

Hi everybody;

I am trying to write a function to cubicly converge on a solution to a square root in fixed point. I am getting bad overflow and when I try to bitshift to eliminate it my solutions reduce to zero. My code is included below. Please help.

function [iterSqrt] = iterFixedPointSqrtCC (val)
numIter = 20;
x = zeros(numIter,1);
x(1) = 1*2^24;
botlim = 1;

if val < botlim
    x(numIter) = 0;
else
    for n = (2:1:numIter)
        x(n-1) = int32(x(n-1));
        xnMinusOneSq = bitshift(bitshift(x(n-1),-8)*bitshift(x(n-1),-8),-8);
        topLineBkts = xnMinusOneSq+3*val;
        botLine = 3*xnMinusOneSq+val;
        topLine = bitshift(x(n-1),-12)*bitshift(topLineBkts,-12);
        x(n) = int32(bitshift(bitshift(uint32(topLine),6)/bitshift(uint32(botLine),-6),12));
    end
end
iterSqrt = x(numIter);

I am using a for loop as while loops do tend to be problematic when going for an embedded target. the value to be rooted comes in scaled by 2^24. I am attempting to implement method 3 from http://chenfuture.wordpress.com/2008/01/03/simple-ways-to-compute-square-root/.

Any suggestions are most welcome.

Thanks

Amardeep

[Amardeep]

The overflow occurs on the line 'topline = ...'

Answer 1

[Amardeep]

I managed to get the quadratic convergence formula working in the interval 0 to 16 which is what I need. The mean error is in the region of 5*10^-4.

function [iterSqrt] = iterFixedPointSqrtQC (val)
numIter = uint32(30);
x = uint32(zeros(numIter,1));
x(1) = uint32(16777216);

for n = (2:1:numIter)
    if x(n-1) == 0
        x(n) = uint32(0);
    else
        divs = uint32(bitshift(uint32(bitshift(uint32(val),4) / bitshift(x(n-1),-4)),16));
        x(n) = uint32(bitshift(4096*bitshift((x(n-1)+divs),-11),-2));
    end
end

iterSqrt = x(numIter);