June 2012 - mathfun@mailman.xmission.com

Re: [math-fun] Wiki article on Circumscribed_circle
by Henry Baker 08 Jun '12

08 Jun '12

FWIW, if anyone cares, I just posted the html version of this article to my web site. http://home.pipeline.com/~hbaker1/FAQ-circumcircle.htm Hopefully, it is more readable than the ascii version. Note very carefully: due to the "head-to-tail" orientation of the vectors, the various vector products have surprising signs; e.g., a.b = -|a||b| cos C Of course, even with traditional vectors, this is still true, but it looks really weird, and can easily trip you (& me!) up.

2 2

Re: [math-fun] a simple problem ?
by Dan Asimov 08 Jun '12

08 Jun '12

On the other hand, I think Mike S. read Simon's intention correctly and I did not. --Dan ________________________________________________________________________________________ It goes without saying that .

3 2

Re: [math-fun] Carry-less squaring & multiplication
by Eugene Salamin 07 Jun '12

07 Jun '12

>________________________________ > From: Eugene Salamin <gene_salamin(a)yahoo.com> >To: Henry Baker <hbaker1(a)pipeline.com> >Sent: Thursday, June 7, 2012 11:21 AM >Subject: Re: [math-fun] Carry-less squaring & multiplication > > >Much the same is true in an arbitrary field of characteristic p: (a + b)^p = a^p + b^p. Hence, for a polynomial > > >Q(x) = sum(a[k] x^k, k=1..n), Q(x)^p = sum(a[k]^p x^pk, k=1..n). > > >And for the field GF(p), a^p = a, so that Q(x)^p = Q(x^p). > > > > -- Gene > > > >>________________________________ >> From: Henry Baker <hbaker1(a)pipeline.com> >>To: Eugene Salamin <gene_salamin(a)yahoo.com>; math-fun <math-fun(a)mailman.xmission.com> >>Sent: Thursday, June 7, 2012 10:31 AM >>Subject: Re: [math-fun] Carry-less squaring & multiplication >> >>Aha! So squaring p(x) (mod 2) "spreads" the bits, sending each bit a[k]x^k -> a[k]x^2k; p(x)^2=p(x^2). >> >>So we can represent perfect shuffle/interleave: >> >>p(x) shuffle q(x) = p(x)^2*x + q(x)^2 (mod 2) >> = p(x^2)*x + q(x^2) (mod 2) >> >>Cool! >> >>But I'd still like to know if there is a way to emulate p(x)*q(x) using cubing or fifthing, etc. >> >>At 10:13 AM 6/7/2012, Eugene Salamin wrote: >>>Over any field of characteristic 2, (a + b)^2 = a^2 + b^2. >>> >>>If p(x) = sum(a[k] x^k, k=0..n), then p(x)^2 = sum(a[k]^2 x^(2k), k=0..n). >>>Over the field GF(2), this further simplifies since a[k]^2 = a[k]. >>> >>> -- Gene >>> >>>>________________________________ >>>> From: Henry Baker <hbaker1(a)pipeline.com> >>>>To: math-fun <math-fun(a)mailman.xmission.com> >>>>Sent: Thursday, June 7, 2012 9:53 AM >>>>Subject: [math-fun] Carry-less squaring & multiplication >>>> >>>>After hearing about the new "carry-less multiplication" instructions coming soon to computers near you, it occurred to me that even without hardware help, such operations perhaps aren't so slow as I initially thought. >>>> >>>>Karatsuba squaring. >>>> >>>>p(x) is a polynomial over GF(2), where a "1" bit at bit position k represents 1*x^k. >>>> >>>>Adding is easy: p(x)+q(x) (mod 2) = p(x) xor q(x). Mod 2, subtraction is the same as addition. 2*p(x) (mod 2) = 0. >>>> >>>>If we split p(x) = q(x)*x^m+r(x) into two pieces q(x),r(x) of approximately the same size, q(x) is the "high part", and r(x) is the "low part". >>>> >>>>Then >>>> >>>>p(x)^2 = (q(x)*x^m+r(x))^2 >>>> = q(x)^2*x^2m + 2*q(x)*r(x)*x^m + r(x)^2 >>>> = q(x)^2*x^2m + r(x)^2 (2*anything = 0 mod 2, so middle part drops out.) >>>> >>>>So Karatsuba squaring is almost trivial: break the poly into 2 ~ equal-sized pieces, square each piece, and then put them together with a shift & xor. >>>> >>>>However, the ease of squaring backfires, as we can no longer use squaring to emulate multiplication: >>>> >>>>a*b = [(a+b)^2-(a-b)^2]/4 >>>> >>>>unfortunately in GF(2) becomes: >>>> >>>>a*b = [(a xor b)^2 xor (a xor b)^2]/0 >>>> = 0/0 ! >>>> >>>>So we need the traditional Karatsuba multiplication method: >>>> >>>>p(x) = q(x)*x^m+r(x) >>>>s(x) = t(x)*x^m+u(x) >>>> >>>>p(x)*s(x) = (q(x)*x^m + r(x)) * (t(x)*x^m + u(x)) >>>> = q(x)*t(x)*x^2m + ((q(x)+r(x))*(t(x)+u(x))-q(x)*t(x)-r(x)*u(x))*x^m + r(x)*u(x) >>>> = q(x)*t(x)*x^2m xor ((q(x) xor r(x))*(t(x) xor u(x)) xor q(x)*t(x) xor r(x)*u(x))*x^m xor r(x)*u(x) >>>> >>>>----- >>>>Question: >>>> >>>>Is it possible to emulate multiplication using p(x)^3 or p(x)^5 (mod 2) ? >> >> >> >> > >

1 0

[math-fun] Carry-less squaring & multiplication
by Henry Baker 07 Jun '12

07 Jun '12

After hearing about the new "carry-less multiplication" instructions coming soon to computers near you, it occurred to me that even without hardware help, such operations perhaps aren't so slow as I initially thought. Karatsuba squaring. p(x) is a polynomial over GF(2), where a "1" bit at bit position k represents 1*x^k. Adding is easy: p(x)+q(x) (mod 2) = p(x) xor q(x). Mod 2, subtraction is the same as addition. 2*p(x) (mod 2) = 0. If we split p(x) = q(x)*x^m+r(x) into two pieces q(x),r(x) of approximately the same size, q(x) is the "high part", and r(x) is the "low part". Then p(x)^2 = (q(x)*x^m+r(x))^2 = q(x)^2*x^2m + 2*q(x)*r(x)*x^m + r(x)^2 = q(x)^2*x^2m + r(x)^2 (2*anything = 0 mod 2, so middle part drops out.) So Karatsuba squaring is almost trivial: break the poly into 2 ~ equal-sized pieces, square each piece, and then put them together with a shift & xor. However, the ease of squaring backfires, as we can no longer use squaring to emulate multiplication: a*b = [(a+b)^2-(a-b)^2]/4 unfortunately in GF(2) becomes: a*b = [(a xor b)^2 xor (a xor b)^2]/0 = 0/0 ! So we need the traditional Karatsuba multiplication method: p(x) = q(x)*x^m+r(x) s(x) = t(x)*x^m+u(x) p(x)*s(x) = (q(x)*x^m + r(x)) * (t(x)*x^m + u(x)) = q(x)*t(x)*x^2m + ((q(x)+r(x))*(t(x)+u(x))-q(x)*t(x)-r(x)*u(x))*x^m + r(x)*u(x) = q(x)*t(x)*x^2m xor ((q(x) xor r(x))*(t(x) xor u(x)) xor q(x)*t(x) xor r(x)*u(x))*x^m xor r(x)*u(x) ----- Question: Is it possible to emulate multiplication using p(x)^3 or p(x)^5 (mod 2) ?

2 1

[math-fun] Recursive integer_bit_reverse function
by Henry Baker 07 Jun '12

07 Jun '12

The following Common Lisp functions should be reasonably efficient if they didn't have to recurse down to the individual bit. But even without a better function for reversing a whole word, "memoizing" int-bit-rev-helper would help a lot, by building up a table of bit-reversed smaller integers. (defun int-bit-rev (n) ;;; This definition makes a slight pretense at efficiency. ;;; Reverse the bits of a bignum n. (if (minusp n) (- (int-bit-rev (- n))) (let* ((nlobits (1- (integer-length (logand n (- n)))))) (ash (int-bit-rev-helper (ash n (- nlobits)) (- (integer-length n) nlobits)) nlobits)))) (defun int-bit-rev-helper (n k) ;;; Reverse the bits of an odd bignum n with k "significant" bits. ;;; Split the number in the middle, then bit-reverse each half. ;;; For better efficiency call an intrinsic function for k<33. ;;; Would work a lot better with memoization. (if (< k 2) n (let* ((lolen (ash k -1)) (hilen (- k lolen)) (lomask (1- (ash 1 lolen))) (lopart (logand n lomask)) (hipart (ash n (- lolen))) (revlopart (int-bit-rev-helper lopart lolen)) (revhipart (int-bit-rev-helper hipart hilen))) (logior (ash revlopart hilen) revhipart))))

2 1

[math-fun] Wilson's 1D gun problem
by Warren Smith 06 Jun '12

06 Jun '12

Wilson was slightly vague stating the problem, I assume he meant uniform random speeds in [0,1] for the bullet, one bullet shot each clock tick. Computer simulations would be a good idea. Draw trajectories (each a straight line segment) in the space-time plane. As soon as two lines hit they vanish. So no two can cross. Each line has 0<slope<1. Each line has one vertex on the time-axis at integer locations, rest lies in the right halfplane (can ignore left halfplane). There is a hierarchical structure: the planar dual of the diagram is a tree. It seems likely to me there is some sort of statistical self-similarity property, the statistics at level L above leaves of the tree should be the same everywhere (if L held fixed) and depend on L like a power, exponential, or logarithmic law. So I would predict the typical distance attained before vanish for a level-L bullet depends on L like that. If this kind of thing can be understood then the problem should be solved (including nonrigorous understanding leading to nonrigorous solution). -- Warren D. Smith http://RangeVoting.org

1 0

[math-fun] "quasicrystal"
by Bill Gosper 06 Jun '12

06 Jun '12

I'm intrigued by Jack Holloway's recursive pentagram snowflake design, Fig 31 in the Minskys & Trinskys book<http://www.blurb.com/bookstore/detail/2172660>. However, circularizing and sampling obscure the pixel structure, and how, if at all, it relates to Fig 30. As usual, Julian comes to the rescue, with a "period 5" trinsky in which orbital x+y stays constant mod 2. The "black squares" (checkerboard) subset of this bitmap strongly resembles Fig 31, except the bounding pentagons have vertex angles of π/2 and 3π/4 instead of 3π/5. So I linearly crunched it to have "rhombic pixels" and wrote http://www.tweedledum.com/rwg/rhombicp5.svg The .svg is so you can scale it up without antialiasing. Unfortunately, my Apple Firefox scales it right off the screen, and refuses to scroll it back! Safari scrolls, but won't let you zoom very far. And Preview won't load svgs at all! And, as of this AM, gosper.org delivers source text instead of graphics for it. So to mega zoom it, Neil suggested downloading inkscape<http://inkscape.org/>, which seems to work great. Can one speak of the limit of this pattern in the large? The pentagram outlines grow without bound and get "infinitely thin", yet seem to fill space. And what is a formula for their limiting shape? Julian (quoted without permission) explains the original image as follows: (d_t means the trinsky d multiplier, etc.) It's the Trinsky equivalent of p5d1, which is d=g=1, e=2*sin^2(π/5). The Minsky-Trinsky equivalence is has d_t=g_t=d_m, e_t=e_m/2, has x about twice as large to compensate. This is what causes the checkerboarded images–for a given Trinsky (x,y), the equivalent Minsky point is ((x+⸤d_t*y⸥)/2,y) (sorry about the floors I haven't found any decent floor characters to use), and the checkerboard pattern comes from whether (x+⸤d_t*y⸥)/2 is an integer or not. The "checkerboard" pattern is only when the Trinksy d=g=1, in which case x+y is constant mod 2: x'=x-y=c mod 2, y'=y+⸤e*x⸥, x''=x'-y'=c-y' mod 2. A granularity of 1/2 would not produce checkerboarded images–it would produce four normal (i.e. at coordinates (ax+b,cy+d)) images (or two, alternating in either columns or row but not both, if only one granularity=1/2). --rwg

1 4

Re: [math-fun] complex number hacks
by Henry Baker 06 Jun '12

06 Jun '12

Bill G: These theorems are in the style of Tristan Needham's "Visual Complex Analysis": http://usf.usfca.edu/vca I fiddled with incenter/inradius with complex numbers, but the formulae weren't so pretty. Since the incenter lies on the angle bisectors, we need sqrt's, which can get very messy. Perhaps you were more successful? Polygon area, polygon-point winding # are just discrete versions of the usual complex plane integrations, right? I'm still intrigued by the Bell Labs paper: Lagarias, Mallows, Wilks. "Beyond the Descartes Circle Theorem". AMM 109 (2002), 338-361. arXiv math.MG/0101066. This paper generalizes an old circle packing theorem to complex numbers. Very cool! See also Graham, et al, "Apollonian Circle Packings:I,II,III,..." arXiv ... At 06:44 PM 6/4/2012, Gosper wrote: >Henry: <minimum publishable quantum, fun facts> These are more than fun facts--they're valuable optimizations. > >We should gather up our various complex plane computational geometry slick tricks (circumcenter, circumradius, incenter, inradius, polygon area, polygon-point winding number, line-segment intersection, ...) and publish them somehow. > >Henry: (This is also true in the arts; take a look at Beethoven's manuscripts -- not everyone wrote music like Mozart, which were perfect the first time.) > >This is probably because Mozart wrote almost nothing in C#. Even less in C++.

1 0

Re: [math-fun] "quasicrystal"
by Henry Baker 06 Jun '12

06 Jun '12

Holey Moley! These are very cool. At 06:44 PM 6/4/2012, Bill Gosper wrote: >In the process, we produced some pleasantly Picassoid squiggle <http://gosper.org/snowfourier.pdf>s.

1 0

[math-fun] Name of board game
by David Wilson 06 Jun '12

06 Jun '12

There was a board game played (I think) on a 5 by 5 board. Each player had 4 blots which they alternately placed on empty squares on the board. After all pieces were placed, players alternately moved one piece as a king in chess, to an empty square. The object was to be first to form either a straight line of four adjacent blots, horizontally, vertically, or diagonally, or place the blots at the corners of a square. I seem to think it was called "teco" or something similar.

6 8