Ok, here's the _extremely short_ version, which I'll expand upon later: On a "hidden bit" floating point system, the positive number 2^e(1+m) (0<m<1) is represented by the pair [e,m]. If we have a number z=2^(2e)*(1+2x) (0<x<.5), represented by [2e,2x], then a good initial approximation to sqrt(z) is [e,x]. Why? Consider squaring s0=[e,x]=2^e*(1+x): [e,x]^2 = (2^e*(1+x))^2 = 2^(2e)*(1+2*x+x^2) ~~ 2^(2e)*(1+2*x) = [2e,2x]. So you get the idea. So, the initial guess isn't a lot of precision, but every little "bit" helps... (I don't have time to expand upon this right this second, but the oddp(e) case looks more like 2^(e-1)*(1-m), so the low bit shifted out of the exponent becomes the "sign" bit for the mantissa.) At 02:30 PM 4/17/2011, Robert Munafo wrote:
On Sun, Apr 17, 2011 at 11:59, Henry Baker <<mailto:hbaker1@pipeline.com>hbaker1@pipeline.com> wrote:
I think we've established that shifting the exponent right by 1 for the initial approximation goes way far back. I suspect that it may go back much further -- perhaps to Von Neumann's original binary floating point proposal.
The only question now is what are the contents of the mantissa. I may need to do some experiments with Maxima to determine how important various guesses at the mantissa are.
[...]
No, you asked "[...] the bits of the entire number (both exponent & mantissa) shifted right by 1."
I still want the answer to that question, not any of the others.
I wrote assembly code for the PDP-11, and apparently it used a floating point format in which an integer test "A>B" was suitable for comparing two positive floating point numbers, so the monolithic shift would have worked there. Maybe other PDP's were similar. But we're looking for actual evidence of it.
- Robert
-- Robert Munafo -- <http://mrob.com>mrob.com Follow me at: <http://fb.com/mrob27>fb.com/mrob27 - <http://twitter.com/mrob_27>twitter.com/mrob_27 - <http://mrob27.wordpress.com>mrob27.wordpress.com - <http://youtube.com/user/mrob143>youtube.com/user/mrob143 - <http://rilybot.blogspot.com>rilybot.blogspot.com