Richard Fateman contributes: sure you may quote me; i would not be surprised if it is described in one of his files at www.cs.berkeley.edu/~wkahan<http://www.cs.berkeley.edu/%7Ewkahan> but I can't spot it. W. Kahan. Implementation of algorithms (lecture notes by W. S. Haugeland and D. Hough). Technical Report 20, Department of Computer Science, University of California, Berkeley, CA, 1973. might contain it, but I can't spot it online.but see this, Bentley column.. http://delivery.acm.org/10.1145/320000/315707/p1155-bentley.pdf?key1=315707&... On Thu, Apr 14, 2011 at 8:32 AM, R Fateman <fateman@eecs.berkeley.edu>wrote:
w kahan taught this trick; I don't know if he invented it. He "proved" his 7090 code was optimal by essentially enumerating all 1-argument subroutines of fewer (plausible) instructions. Something like 12 instructions.
RJF
------------- Tom Duff>It worked pretty well on old enough hardware, but it mostly can't keep up
on modern machines with built-in sqrt (last I checked, which wasn't recently.) rwg>Eh? The last hardware sqrt I recall was on the Packard Bell 250 (1963?). (Integer sqrt, with remainder.) I have been griping for years at its absence from modern order codes, since it is far simpler than divide. So they've finally come around to reviving it? --rwg mrob> The next ("ultimate") editions of Knuth's books, if he manages to finish them will use MMIX[1] which uses IEEE floating-point, but I think it's unlikely Knuth would have held on to anecdotes about this right-shift hack just to include them 40 years later... rwg>Did you check Vol 4a? It *is* (in part) about bit bumming. On Wed, Apr 13, 2011 at 11:35 PM, Bill Gosper <billgosper@gmail.com> wrote:
hgb>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). ------ rwg>It's really old, and can probably be found in the 704 and pdp-6 library sqrts. I think Knuth told me he found it as an undergrad, but that basketball youtube
shows him using a biquinary machine (650?). --rwg