Gosper is correct, it's surely quite old--how old I can't say. "First you forget to zip up. Then you forget to zip down. Finally you forget your assembly hacks." I first encountered it in the early 1970's in the code for PDP-10 Space War, and surely it long predates that (again, as RWG suggests, a sufficiently motivated historian might look at the PDP-6 and earlier libraries--perhaps the Computer History Museum has them?). By the time I saw it it clearly bespoke evolving sophistication. Not only did it whack the approximation twice with unrolled copies of the iteration (no loop & test--twice being provably sufficient for the desired accuracy) but it had a strange twiddle before that (an OR or something, I forget), right after the initial shift, involving that alien bit from across the border between the exponent and mantissa. Famously, the only comment in that entire page of highly mysterious source code was "Watch out for the bum who wrote this!" I think I adapted it for the S-1, as unremarkable best practice du jour. Since Knuth was hanging around the Lab around then too he also might have run across it, whether or not it crept into TAOCP et seq. Indeed, it's plausible he independently invented it (heh, clever lad, that Don). At Apple (in pre-68000 days) and elsewhere I've often been annoyed hearing it (erroneously, I trust) ascribed to Kahan. "Those who cannot learn from history are doomed to reimplement it." --MLB
="Bill Gosper" <billgosper@gmail.com>
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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun