Square Root Help Please

[code2win]

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;
  }
My exp (exponent) function is good. When I translated this sqrt into python and replaced the exponent calls with python's ** operator for the 'to the power of', this algorithm still did not work for any problems. Then I found an algorithm that DID get everything right in python, but in Jack it got the first square root problem right but not get the second square root question which features the overflow issue. Here is the algorithm which works in python and mostly in Jack:

  function int sqrt(int x){
        var int start;
        var int mid;
        var int end;
        var int result;
        var int square;
        let start = 1;
        let end = x/2;
        while (start < (end+1)){
                let mid = (start + end) / 2;
                let square = mid * mid;
                if (square = x){return mid;}
                if (square < x){
                        let start = mid + 1;
                        let result = mid;
                }
                else{let end = mid -1;}
        }
        return result;
  }

[code2win]

I just came up with this, but I doubt its efficiency:
  function int sqrt(int x){
        var int last_i;
        var int i;
        var int end;
        let end = x/2;
        while (i<end){
                if (((i * i) > x)|(i*i < 0)){return last_i;}
                let last_i = i;
                let i = i + 1;
        }
        return last_i;
  }
what do you think?

[WBahn]

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

[code2win]

The algorithm was not defined properly. N was never defined. In the video Shimon said virtually nothing about the algorithm ("this isn't a course on algorithms").

Thank you for the response; I'll study what you have posted.

[WBahn]

code2win wrote

The algorithm was not defined properly. N was never defined.

So just what did you think it meant when it stated at the beginning of the section that, "Mathematical algorithms operate on n-bit binary numbers..."? It goes into some length of explaining why we want algorithms for our math operations that are O(n) and not to the value of an n-bit number. It then presents algorithms for several operations (multiplication, division, and square root) which consistently use the value of n in their descriptions, with the first one, multiplication, being prefaced by the statement, "we now turn to present an efficient multiplication x*y algorithm for n-bit numbers whose running time is O(n) rather an O(x) or O(y), which are exponentially larger."

So how did you implement the multiplication and division algorithms, both of which involve the parameter n, without knowing that n is the number of bits in x and y?

Even if you didn't know what n was in the square root algorithm, that doesn't mean that you can just arbitrarily replace it with x or any other parameter that comes within reach.

[code2win]

The whole lesson was vague; it really feels like the goal was to be as difficult to understand as possible.
Somehow I managed.
So i was incorrect for guessing what N was, but what i should have done, is ...correctly guessed what N was, based on what it meant in other exercises?
Blame me all you want. You didn't define the algorithm properly, and on video smugly dismissed the idea of explaining it, or just giving a simple notation as to the identity of N.

[WBahn]

code2win wrote

The whole lesson was vague; it really feels like the goal was to be as difficult to understand as possible.
Somehow I managed.
So i was incorrect for guessing what N was, but what i should have done, is ...correctly guessed what N was, based on what it meant in other exercises?
Blame me all you want. You didn't define the algorithm properly, and on video smugly dismissed the idea of explaining it, or just giving a simple notation as to the identity of N.

How much simpler does the notation need to be than, "Mathematical algorithms operate on n-bit binary numbers"?

Where did I define the algorithm at all? On what video did I do anything at all?

I'm just trying to help you understand the algorithm the authors presented in the text and help you see where you went wrong with your interpretation and how you could have lessened the likelihood of misinterpreting it by being able to better read of the material as a whole. If that is not of interest to you, then I will stop wasting both of our time. Good luck.

[code2win]

I am interested in an explanation of the square root algorithm that makes sense, which you have provided above.
This whole course, I have been able to look at what the authors have said from different angles, and come up with the answer. For this one, I have not.
No, I'm not interested in the notion that I should have known all along. Good-day to you as well; thank you for the above explanation of the square root algorithm.

[acarteas]

I had the same issue and question so you are not alone in forgetting about how you can utilize the length of bits to quickly find the square root.  Also, cudos to you for responding very professionally to what might be construed as an inflammatory response.