This post was updated on .
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; } 
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? 
Administrator

In reply to this post by code2win
The problem is that you aren't following the algorithm. You are trying to find the squareroot of x where x is a nonnegative nbit 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 8bit values. The largest 8bit value is 255 and since the sqrt(256)=16, we KNOW that the sqrt(any 8bit value) is strictly less than 16, and is thus representable by a 4bit 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 
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. 
Administrator

So just what did you think it meant when it stated at the beginning of the section that, "Mathematical algorithms operate on nbit 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 nbit 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 nbit 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. 
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. 
Administrator

How much simpler does the notation need to be than, "Mathematical algorithms operate on nbit 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. 
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. Goodday to you as well; thank you for the above explanation of the square root algorithm. 
Free forum by Nabble  Edit this page 