I don't have my Knuth volumes handy. Perhaps this trick is in one of the exercises? Current additional guesses: IBM 704/709/7040/7090 Fortran libraries PDP-6/10 Fortran libraries CDC 6600 Fortran libraries Cray-1 Fortran libraries _not_ the IBM 360 (not a binary exponent) Kahan's original SANE IEEE floating point SW for the Motorola 68000 used in the original Apple Macintosh. Various DSP (Digital Signal Processors): Analog Devices, Texas Instruments, ATT (Bell Labs), etc., from the 1980's. At 11:35 PM 4/13/2011, Robert Munafo wrote:
I've just traced it back to 1997 ("Floating-point tricks" by Blinn, see below) where one finds the following:
float ASqrt(float x) { int i = (AsInteger(x)>>1) + (AsInteger(1.0f)>>1); return(AsFloat(i); }
Here are the breadcrumbs I followed:
1. Google "square root estimate right shift"
2. http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#cite_note-8
3. http://www.beyond3d.com/content/articles/8/
4. http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf ("Fast Inverse Square Root" by Chris Lamont, Feb 2003)
5. http://replay.waybackmachine.org/20041206135041/http://www.magic-software.co...
("Fast Inverse Square Root" by David Eberly, Jan 2002)
5b. www.geometrictools.com/Documentation/FastInverseSqrt.pdf (current version of the same article, which does not know about the 1997 source)
6. http://en.wikipedia.org/wiki/Fast_inverse_square_root
7. ieeexplore.ieee.org/iel1/38/13035/00595279.pdf (abstract only, actual content blocked by spoofing)
7b. http://rufus.hackish.org/~rufus/FPtricks.pdf ("Floating-point tricks" by Jim Blinn, relevant section is on top of page 83)
- Robert Munafo
On Thu, Apr 14, 2011 at 00:19, Henry Baker <hbaker1@pipeline.com> wrote:
When making an initial guess of sqrt(x) for a Newton iteration, where x is a positive floating point number, a good initial guess is the bits of the entire number (both exponent & mantissa) shifted right by 1.
This is the sort of thing that would have been done on the 7090 or the PDP-10. Does anyone here recall seeing this trick in the 1950's or 1960's ?
I checked, and it isn't in HAKMEM.
I've used this trick myself (at least on machines where moving numbers between the integer & floating point units isn't prohibitive).
-- Robert Munafo -- mrob.com Follow me at: fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com- youtube.com/user/mrob143 - rilybot.blogspot.com