title: Seeding square roots on FPGA in VHDL for Fixed Point
body: <p>I'm attempting to create a fixed-point square root function for a Xilinx FPGA (hence <code>real</code> types are out, and David Bishops <code>ieee_proposed</code> <a href="http://www.eda.org/fphdl/" rel="nofollow noreferrer">library</a> is also unsupported for XST synthesis).</p>
  
  <p>I've settled on a Newton-Raphson method to calculate the reciprocal square root (as it involves fewer divisions).</p>
  
  <p>One of the remaining dilemmas I have is how to generate the initial seed. I looked at the <a href="https://en.wikipedia.org/wiki/Fast_inverse_square_root" rel="nofollow noreferrer">Fast Inverse Square Root</a>, but it only appears to work for floating point arithmetic.</p>
  
  <p>My best thoughts at the moment are, to take the length of the input value (ie. find the index of the most significant, non-zero bit), halve it crudely and use that as the power for a seed.</p>
  
  <p>I wrote a short test script to quickly check the accuracy (its in Matlab but that's just so I could plot a graph...)</p>
  
  <pre><code>x = 1:2^24;
  gen_result = zeros(1,length(x));
  seed_vals = zeros(1,length(x));
  for i = 1:length(x)
     result = 2^-ceil(log2(x(i))/2); %effectively creates seed value from top bit index
     seed_vals(i) = 1/result; %Store seed value
     for j = 1:6
         result = result*(1.5-0.5*x(i)*result^2); %reciprocal root
     end
     gen_result(i) = 1/result; %single division at the end
  end
  </code></pre>
  
  <p>And unsurprisingly, the seed becomes wildly inaccurate each time a number increases in size, and this increases as the magnitude of the input increases. As a graph this can be seen as:</p>
  
  <p><a href="https://i.stack.imgur.com/r6mDj.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/r6mDj.png" alt="enter image description here"></a></p>
  
  <p>The red line is the value of the seed, and as can be seen, is increasing increasing in powers of 2.</p>
  
  <p>My question very simple: Are there any other simple methods I could use to generate a seed value for fixed point square root values in VHDL, ideally which don't cause ever increasing amounts of inaccuracy (and hence require more iterations each time the input increases in size).</p>
  
  <p>Any other incidental advise on how to approach finding fixed points square roots in VHDL would be gratefully received!</p>