Non-restoring binary square root and convergence

From: Clint Olsen (clint_at_0lsen.net)
Date: 02/22/05 

Date: Tue, 22 Feb 2005 15:45:07 -0600

Hi:

I was interested in this algorithm because it generates the solution, one
bit at a time, and I could potentially use this for generating
pseudo-random bit patterns for some software I'm writing.

For giggles I was playing around with the binary square-rooting algorithm.
I read a paper or two which talked about it, and implemented my best guess
at it. Unfortunately the documentation on some of these algorithms leaves
a bit to be desired. Some handle the determination of the next root bit by
signed arithmetic, and others rely on some flimsy notion of 'overflow'.

For correctness, I tried a few examples where there is an exact square
root. Heck, if it can't find that, what's the point? :)

I noticed that while my implementation of the algorithm does generate the
correct bits, I don't get a clear sense of convergence when an exact
solution is found. In other words, I don't get a clear-cut case when the
remainder goes to zero on the correct iteration.

For example, when I'm trying to find the square root of 36, I get an
iteration where the derived root is 3, and the remainder is zero. On the
next iteration, I get a derived root of 6 (which is correct), but I'm left
with a remainder of -13. The algorithm will continue to correctly
calculate zeroes for any bits thereafter and the remainder continutes to
increase (negatively) in magnitude. Interestingly, on odd inputs the
correct result and the remainder is 0 in the same iteration.

I was curious if this method is designed to operate for a fixed number of
iterations and then terminate or is there an iteration when you *know*
you've converged on a result? The algorithms I've read all either conform
to the former or the exit strategy is undocumented.

Thanks,

-Clint

Relevant Pages

  • Non-restoring binary square root and convergence
    ... For giggles I was playing around with the binary square-rooting algorithm. ... Some handle the determination of the next root bit by ... iteration where the derived root is 3, and the remainder is zero. ...
    (comp.programming)
  • Re: Non-restoring binary square root and convergence
    ... > For giggles I was playing around with the binary square-rooting algorithm. ... Some handle the determination of the next root bit by ... > iteration where the derived root is 3, and the remainder is zero. ...
    (sci.math)
  • Re: Non-restoring binary square root and convergence
    ... > For giggles I was playing around with the binary square-rooting algorithm. ... Some handle the determination of the next root bit by ... > iteration where the derived root is 3, and the remainder is zero. ...
    (comp.programming)
  • Short koan-like code snippets (was: coerce for arbitrary types)
    ... (defun bfs6 (test children pending) ... The algorithm seems to be a tail-recursive expression of what ... I don't like using tail recursion to emulate iteration, ...
    (comp.lang.lisp)
  • Iterative subspace decomposition
    ... Subspace Tracking," IEEE Transactions on Signal Processing, vol. 43, ... the PASTd algorithm does not produce orthogonal ... it is not producing the eigendecomposition I ...
    (sci.math.num-analysis)