# attempting to write a fixed point sqrt function

23 views (last 30 days)
Amardeep on 7 Dec 2011
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 on 8 Dec 2011
The overflow occurs on the line 'topline = ...'

Amardeep on 8 Dec 2011
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);