Re: [math-fun] Origin of SQRT hack?
I think I remember seeing this in the PDP6 library function for sqrt. I believe the shift was followed by adding (integer add) a magic constant, probably to adjust the range and repair the exponent offset. Then a few rounds of Newton, unwound. (note to folks under 50) Before IEEE floating point came along, the individual computer makers had their own formats for floating point. Both the 7090 series and PDP6/10 used 36-bit words. The PDP6 format had 8 bits of exponent, offset by 128, and 27 bits of mantissa. A normalized number included the high-order 1 bit, which is dropped in IEEE format. I don't recall if that bit had value .5 or 1.0. 0.0 was simply 0, and negatives were the (integer) two's complement of the positives. This had the virtue that the ordering of (normalized) floating numbers was the same as the ordering of integers, so the compare instructions didn't need to come in two flavors. I think I'll register a disagreement with the comment that IEEE accuracy requirements for sqrt (exactly correct rounding) effectively preclude doing it in software: After a few rounds of Newton, the answer should be within one bit, likely on the high side. You can check which of two consecutive floating values is correct by comparing V * (V-epsilon) versus X. Rich ---- Quoting 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
As a quick aside, Wikipedia says "The PDP-6 was infamous because of the 6205 board, a large (11 x 9 inches) board which contained 1 bit of AR, MB, and MQ (thus there were 36 of these). It had 88 transistors, a 2-sided PC etch, two 18-pin and two 22-pin connectors (two on each side of the module). Because of all these connectors, swapping this module was a major undertaking, and the mechanical coupling made it highly likely that fixing one fault would cause another." following with "There was also a great fear of powering off a PDP-6, since it would generally result in at least one 6205 board failing." Is this true? On Fri, Apr 15, 2011 at 6:52 PM, <rcs@xmission.com> wrote:
I think I remember seeing this in the PDP6 library function for sqrt. I believe the shift was followed by adding (integer add) a magic constant, probably to adjust the range and repair the exponent offset. Then a few rounds of Newton, unwound.
(note to folks under 50) Before IEEE floating point came along, the individual computer makers had their own formats for floating point. Both the 7090 series and PDP6/10 used 36-bit words. The PDP6 format had 8 bits of exponent, offset by 128, and 27 bits of mantissa. A normalized number included the high-order 1 bit, which is dropped in IEEE format. I don't recall if that bit had value .5 or 1.0. 0.0 was simply 0, and negatives were the (integer) two's complement of the positives. This had the virtue that the ordering of (normalized) floating numbers was the same as the ordering of integers, so the compare instructions didn't need to come in two flavors.
I think I'll register a disagreement with the comment that IEEE accuracy requirements for sqrt (exactly correct rounding) effectively preclude doing it in software: After a few rounds of Newton, the answer should be within one bit, likely on the high side. You can check which of two consecutive floating values is correct by comparing V * (V-epsilon) versus X.
Rich
---- Quoting 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The description of the 6205 module is correct. I think Wikipedia exaggerates the fear of powering off a PDP-6, but perhaps others would like to vote on that. Another aspect of the 6205 is that the clock speed was getting into the range where reliability really required design as a radio frequency (RF) device, such as having a good ground plane, but this fact hadn't fully sunk in with the designers. Consequently, the noise margins were sometimes pesky, and sometimes a given 6205 would work in one slot but not in another, as I remember. One programmer that did a lot of the PDP-6 floating point library was former MIT student and TMRC member Clark Frasier (spelling?). I think he coded many of the trig functions. He might remember about sqrt, even if he didn't code it. -- Mike ----- Original Message ----- From: "quad" <quadricode@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Cc: <rcs@xmission.com> Sent: Friday, April 15, 2011 8:21 PM Subject: Re: [math-fun] Origin of SQRT hack?
As a quick aside, Wikipedia says
"The PDP-6 was infamous because of the 6205 board, a large (11 x 9 inches) board which contained 1 bit of AR, MB, and MQ (thus there were 36 of these). It had 88 transistors, a 2-sided PC etch, two 18-pin and two 22-pin connectors (two on each side of the module). Because of all these connectors, swapping this module was a major undertaking, and the mechanical coupling made it highly likely that fixing one fault would cause another."
following with
"There was also a great fear of powering off a PDP-6, since it would generally result in at least one 6205 board failing."
Is this true?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I'm sort of coming into the middle of this discussion, but I think that shifting to get the square root of a floating point binary number must be relatively old. I vaguely recall mention of the strategy for the ORDVAC at Aberdeen Proving Ground around 1954, but a more verifiable reference might be to Konrad Zuse's machines of the 1930's. As I recall his biography mentions that a fast and reliable square root operation was one of the notable features of those machines. If shifting weren't as expensive as multiplication, you could probably get fast squares the same way. -hvm
The date of this routine claims to be 12/28/1972: http://www.saildart.org/1974/04/27/GEMSUB%5BGEM,BGB%5D SUBR(SQRT,X) ;SQUARE ROOT OF ABS(X). COMMENT ------------------------------------------------------------ A 0 B 1 C 2 MOVM B,X JUMPE B,POP1J. PUSHP 2 ;LET X=F*(2^2B) WHERE 0.25<F<1.00 THEN SQRT(X)=SQRT(F)*(2^B). ASHC B,-=27 SUBI B,201 ;GET EXPONENT IN B, FRACTION IN C. ROT B,-1 ;CUT EXP IN HALF, SAVE ODD BIT DAP B,L LSH B,-=35 ;USE THAT ODD BIT. ASH C,-10 FSC C,177(B) ;0.25 < FRACTION < 1.00 ;LINEAR APPROXIMATION TO SQRT(F). DAC C,A FMP C,[0.8125 0.578125](B) FAD C,[0.302734 0.421875](B) ;TWO ITERATIONS OF NEWTON'S METHOD. LAC B,A FDV B,C FAD C,B FSC C,-1 FDV A,C FADR A,C L: FSC A,0 LAC 1,A POPP 2 POP1J ENDR SQRT; BGB 28 DECEMBER 1972 ------------------------------------- At 04:52 PM 4/15/2011, rcs@xmission.com wrote:
I think I remember seeing this in the PDP6 library function for sqrt. I believe the shift was followed by adding (integer add) a magic constant, probably to adjust the range and repair the exponent offset. Then a few rounds of Newton, unwound.
(note to folks under 50) Before IEEE floating point came along, the individual computer makers had their own formats for floating point. Both the 7090 series and PDP6/10 used 36-bit words. The PDP6 format had 8 bits of exponent, offset by 128, and 27 bits of mantissa. A normalized number included the high-order 1 bit, which is dropped in IEEE format. I don't recall if that bit had value .5 or 1.0. 0.0 was simply 0, and negatives were the (integer) two's complement of the positives. This had the virtue that the ordering of (normalized) floating numbers was the same as the ordering of integers, so the compare instructions didn't need to come in two flavors.
I think I'll register a disagreement with the comment that IEEE accuracy requirements for sqrt (exactly correct rounding) effectively preclude doing it in software: After a few rounds of Newton, the answer should be within one bit, likely on the high side. You can check which of two consecutive floating values is correct by comparing V * (V-epsilon) versus X.
Rich
---- Quoting 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
participants (5)
-
Henry Baker -
mcintosh＠unam.mx -
Michael Beeler -
quad -
rcs＠xmission.com