code2win wrote

I tried the algorithm in the book, but I couldn't get it to give a single correct return in python or in jack.

I looked up "square root binary search"; that algorithm worked in python but can't handle the overflow problem in jack on the second square root test. I'm been spending way too much time on this. Can someone please help me with this; this is really tedious.

What does 'j = n/2 -1...0 do' in pseudo code mean?

here was my interpretation of that: (I also tried some other variations of what it could mean)

function int sqrt(int x){

var int j;

var int y;

let j = x/2 - 1;

while (j > 0){

if (exp(y+exp(2,j),2) < (x+1)){y = y + exp(2,j);}

let j = j - 1;

}

return y;

}

The problem is that you aren't following the algorithm.

You are trying to find the square-root of x where x is a non-negative n-bit number.

You let j start at (n/2)-1, not (x/2)-1.

Work a toy version by hand until you are comfortable with it.

For instance, let's work with 8-bit values.

The largest 8-bit value is 255 and since the sqrt(256)=16, we KNOW that the sqrt(any 8-bit value) is strictly less than 16, and is thus representable by a 4-bit value.

So we start with 1000 (binary) and check if the square of it is greater than x and, if it is, then we know that sqrt(x) is less than 1000 (binary) and the biggest sqrt(x) can be is 0111, otherwise we know that sqrt(x) is at least 1000 (binary). So now we know what the most significant bit of sqrt(x) is. We then move on to the next bit and continue this process until we set the last bit.

Let's work a simple example.

x=112d (one hundred - the d on the end means decimal -- all others are in binary)

y = 0

temp = 1000

Is (y+temp)^2 > 112d? No (it's 64d), so y = y + temp = 1000

temp = 0100

Is (y+temp)^2 > 112d? Yes (it's 144d), so leave y alone

temp = 0010

Is (y+temp)^2 > 112d? No (it's 100d), so y = y + temp = 1010

temp = 0001

Is (y+temp)^2 > 112d? Yes (it's 121d), so leave y alone

temp = 0000, so we are done.

Thus sqrt(112) = 10