April 2011 - mathfun@mailman.xmission.com

[math-fun] GoL fans: Music-producing cellular automaton-like system
by quad 17 Apr '11

17 Apr '11

I found this and think it is quite cool. Maybe you can do some cool math with it. Or just have fun making music. Here is an example of use that is both visually and audibly pleasing. http://www.earslap.com/projectslab/otomata?q=4h4t5j7k444c1z3l2i7o631078051q… It's intuitive. But directions are there. Have fun! -Robert

1 0

Re: [math-fun] Origin of SQRT hack?
by rcs＠xmission.com 16 Apr '11

16 Apr '11

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(a)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(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

5 4

[math-fun] Origin of SQRT hack?
by Bill Gosper 16 Apr '11

16 Apr '11

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

4 5

[math-fun] Another prime question
by David Wilson 16 Apr '11

16 Apr '11

Given prime p, do there necessarily exist primes q, r such that p+q+r | pqr ?

5 7

Re: [math-fun] Origin of SQRT hack?
by Henry Baker 16 Apr '11

16 Apr '11

[I forgot to mention the author of this memo: John White. Perhaps someone can contact him & ask him if he invented this first approximation.] FYI -- http://dspace.mit.edu/bitstream/handle/1721.1/6128/AIM-103.pdf?sequence=2 MIT Project MAC AI Project Vision Project Internal Memo No. 103. August 2, 1966 Additions to Vision Library John White MODIFIED LAP Additions have been made to LAP as described in the PDP-6 write-up. ... SQRT INPUT LISP number x. OUTPUT LISP number sqrt(x). ALARMS None. ALGORITHM Four iterations of Newton's method with first approximation as x/2^floor(log2(x)/2), i.e., the floating exponent is divided by 2. AVAILABILITY Same as ABS and ANGBTN. ... [I'm using slightly more modern notation, rather than trying to post a jpg or png image.] At 04:52 PM 4/15/2011, rcs(a)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(a)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

1 0

Re: [math-fun] Origin of SQRT hack?
by Henry Baker 16 Apr '11

16 Apr '11

FYI -- http://dspace.mit.edu/bitstream/handle/1721.1/6128/AIM-103.pdf?sequence=2 MIT Project MAC AI Project Vision Project Internal Memo No. 103. August 2, 1966 ... SQRT INPUT LISP number x. OUTPUT LISP number sqrt(x). ALARMS None. ALGORITHM Four iterations of Newton's method with first approximation as x/2^floor(log2(x)/2), i.e., the floating exponent is divided by 2. AVAILABILITY Same as ABS and ANGBTN. ... [I'm using slightly more modern notation, rather than trying to post a jpg or png image.] At 04:52 PM 4/15/2011, rcs(a)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(a)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

1 0

Re: [math-fun] Origin of SQRT hack?
by Tom Duff 15 Apr '11

15 Apr '11

Bill Gosper <billgosper(a)gmail.com> writes: >Tom Duff>It worked pretty well on old enough hardware, but it mostly can't >Tom Duff>keep up on modern machines with built-in sqrt (last I checked, >Tom Duff>which wasn't recently.) > >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 Intel has had a sqrt instruction [FSQRT] since the 8087 FPU (identical functionality has been integrated into the x86 CPU instruction set since the 486DX. 8087 was introduced in 1980, 486DX in 1989.) It's pretty much a requirement of IEEE 754, if you read between the lines. (754 has accuracy requirements that are hard to achieve by any obvious software solution, for small values of 'obvious.') -- Tom Duff. Reality does not exist but appears to exist as expressed by human beings.

1 0

Re: [math-fun] Origin of SQRT hack?
by Tom Duff 14 Apr '11

14 Apr '11

Henry Baker <hbaker1(a)pipeline.com> writes: > There's also a cool IBM trick to computing abs(z), where z=x+iy, which > converges cubically (?). It works by rotating the vector onto the > in steps, while preserving the length of the vector. There is a paper > in one of the IBM journals from the 1980's. With the multiplicity of fp > units in today's processors, it should work pretty well. That's Cleve Moler & Donald Morrison, "Replacing Square Roots by Pythagorean Sums", IBM J Res Develop v27#6 Nov 1983, pp 577-581, reproduced here: http://www.scribd.com/doc/29568822/Moler-Morrison-Pythagorean-Sums 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.) -- Tom Duff. Those idiots! They got it all wrong!

1 0

[math-fun] Origin of SQRT hack?
by Henry Baker 14 Apr '11

14 Apr '11

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).

2 4

[math-fun] Elegance & tailors
by Henry Baker 14 Apr '11

14 Apr '11

I did a Google search & it appears that Einstein is credited with the phrase "leave elegance to the tailors". However, I seem to recall that Einstein was merely quoting another German mathematician -- perhaps Hilbert. Does anyone here have any further insights?

3 3