9 messages
Open this post in threaded view
|

 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;   }
Open this post in threaded view
|

## Re: Square Root Help Please

 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 x)|(i*i < 0)){return last_i;}                 let last_i = i;                 let i = i + 1;         }         return last_i;   } what do you think?
Open this post in threaded view
|

## Re: Square Root Help Please

 Administrator In reply to this post by code2win 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
Open this post in threaded view
|

## Re: Square Root Help Please

 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.
Open this post in threaded view
|

## Re: Square Root Help Please

 Administrator 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.
Open this post in threaded view
|

## Re: Square Root Help Please

 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.
Open this post in threaded view
|

## Re: Square Root Help Please

 Administrator 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.