Administrator

The square root algorithm presented in Chapter 12 is fairly easy to understand and implement,
but it is a bit slow because it needs to compute 8 squares.
This post presents a more efficient algorithm that only requires addition, subtraction and shifting. Algorithm The algorithm is derived from the "long division" pencil and paper method of computing square roots. If you don't know this method, this page is the best presentation I found in a quick search.
The tricky part of this manual method can be finding the correct digit to append to the partial square root such that the partial difference isn't larger than the partial remainder. In the example above, my first guess for the 4th digit was 5, but 11205*5 =56025, which is too big. The algorithm can be converted to base2 which makes the digit choice 0 or 1, and that's an easy decision; just a single comparison. Notice that the base10 "double and append a digit" is mathematically "double, multiply by the radix, add the digit." In binary, given the partial square root bbb, the partial difference will either be zero or bbb*2*2+1 = bbb01. Implementation To generated the square root of x:
Results Running in the VM Emulator, my Jack implementation of this algorithm runs 5 times faster than the Math.sqrt in the supplied Math.vm file. Half the time in each iteration is spent on step 2.1. Jack is not good at bit manipulation! 
Can you give me stepbystep examples for each implementation step? I managed to understand the base10 long division method but have no idea how binary version works. Like, when the iteration should be stopped? What does it mean to "Shift the two most significant bits of x into the least significant end of r."? And what does it mean to "Generate subtrahend."?

Found the the stepbystep explanation from FreeBSD git! https://github.com/freebsd/freebsd/blob/master/cddl/contrib/opensolaris/lib/libdtrace/common/dt_consume.c#L291 
Administrator

In reply to this post by Ju Se Hoon
The notation r:x means to treat the r and x variables as a single 32bit value, so if r=0000..0010 and x=1101..01, then r:x = r:x << 2 results in r=00..001011 and x=01..0100. Subtrahend is the number being subtracted in a subtraction problem. In this case the xxx01 values in the column on the left side of the "division" problem. This value is q01 = q*4+1. Because step 3 just did q = q*2, step 3 is s = q*2+1. The algorithm iterates once for each bit in the output value. The argument must be nonnegative, so it can be treated as a 16bit unsigned number. The square root of a 16bit number fits in 8bits, so 8 iterations are required. Note that r:x = r:x << 2 is a bit tricky in Jack. My code does r:x = r:x << 1 twice: var int r, x; ... // Move the next 2 argument bits into the remainder (r:x = r:x << 2). let r = (r+r)(x<0); // Shift r left 1 bit and merge in new x bit. let x = x+x; // Shift x left 1 bit. let r = (r+r)(x<0); let x = x+x;I leave it for you to puzzle out how the "(x<0)" adds x's mostsignificant bit. Mark 
Free forum by Nabble  Edit this page 