April 2014 - mathfun@mailman.xmission.com

[math-fun] Bit-fiddling chess bitboards ...
by Guy Haworth 18 Apr '14

18 Apr '14

I think there's some expertise at https://chessprogramming.wikispaces.com/Flipping+Mirroring+and+Rotating Best of luck Guy

1 0

[math-fun] x>0 and y>0
by Warren D Smith 18 Apr '14

18 Apr '14

If x and y both are unsigned integers, and we want to tell whether (x>0 and y>0), then how can we do it? 1. naive method: test x>0 and (if not) then also y>0. 2. x*y>0, but can fail if multiply overflows. 3. The gnu superoptimizer found 44 nonobvious methods, each involving 4 instructions, at least one of which always is subtract-with-borrow and/or add-with-carry. I think the basic idea is: if you regard (x,y) as a 2-digit number, and subtract (1,1), then you will generate at least one borrow if and only if (x=0 or y=0). 4. ((-x)&(-y))>>31 should be nonzero if x>0 and y>0, provided neither x nor y was greater than 2^31 - 1. On a 32-bit machine. -- Warren D. Smith

6 12

Re: [math-fun] x>0 and y>0
by Henry Baker 17 Apr '14

17 Apr '14

[Second Try] |4*atan2(y,x)-pi|<pi or equivalently, |4*atan2(y,x)/pi-1|<1 Don't laugh too hard; as floating point and GPU's become ubiquitous, this approach may actually be as fast as some other approaches -- particularly in very deeply pipelined units. Of course, it would work somewhat more reliably if atan2(y,x)/pi were the primitive instead of atan2(y,x) itself.

1 0

Re: [math-fun] The NRA computes pi ??
by Henry Baker 17 Apr '14

17 Apr '14

I guess a Powerpoint on a flash drive wouldn't be very much protection these days... https://en.wikipedia.org/wiki/Theodore_Roosevelt "While [Teddy] Roosevelt was campaigning in Milwaukee, Wisconsin, on October 14, 1912, a saloonkeeper named John Flammang Schrank shot him, but the bullet lodged in his chest only after penetrating his steel eyeglass case and passing through a thick (50 pages) single-folded copy of the speech he was carrying in his jacket." At 03:02 PM 4/17/2014, Eugene Salamin wrote: >According to this letter published in the Notices of the AMS, > >www.ams.org/notices/200706/tx070600693p.pdf > >an AK-47 bullet can penetrate 4-5/32 inches into a stack of Notices. > > -- Gene >>________________________________ >> From: Henry Baker <hbaker1(a)pipeline.com> >>To: math-fun(a)mailman.xmission.com >>Sent: Thursday, April 17, 2014 8:05 AM >>Subject: [math-fun] The NRA computes pi ?? >> >>FYI -- >> >>http://arxiv.org/abs/1404.1499

1 0

[math-fun] Simple formula for "Roth's constant"
by Bill Gosper 17 Apr '14

17 Apr '14

(A014578 <http://oeis.org/A014578>) Out[665]= k (-1) Sum[--------, {k, 0, ∞}] k 3 2 - 1 In[666]:= RealDigits[% /. ∞] -> 4, 8] Out[666]= {{{6, 6, 7, 6, 6, 7, 6, 6, 6, 6, 6, 7, 6, 6, 7, 6, 6, 6, 6, 6, 7, 6, 6, 7, 6, 6, 7}}, 0} --Bill (As computed by the Life pattern x = 50, y = 50, rule = B3/S23 26b3o11b3o$26bo2bo10bo2bo$26bo6b3o4bo$26bo5bo2bo4bo$27bo4bo3bo4bo$33b 4o$bo8b2o23bo$o8b4o$o3bo3b2ob2o28bo$4o5b2o29b3o$40bob2o$41b3o$41b2o$4b 2o$2b2ob2o$2bo2bo$2bo2bo$3b2o$24b3o$24bo2bo$bo22bo$o23bo$o3bo14bo5bo$ 4o14bo$18bo3bo5b4o$18b4o5bo3bo$31bo14b4o$24bo5bo14bo3bo$25bo23bo$25bo 22bo$22bo2bo$23b3o$45b2o$44bo2bo$44bo2bo$43b2ob2o$44b2o$7b2o$6b3o$6b2o bo$7b3o29b2o5b4o$8bo28b2ob2o3bo3bo$37b4o8bo$14bo23b2o8bo$13b4o$8bo4bo 3bo4bo$9bo4bo2bo5bo$9bo4b3o6bo$6bo2bo10bo2bo$7b3o11b3o! misnamed thue.) >> >> What the heck is this ⬇? I can't delete it. >> >> >> >> >> >> >

2 2

[math-fun] Divergent sum = -1/12
by Bernie Cosell 16 Apr '14

16 Apr '14

I'm wondering what the solid [??] mathematical basis is for sum(n) = -1/12. I was looking at the series (which seems to be a starting place for the "proof" of -1/12) 1 - 1 + 1 - 1 .. and it can have any of a bunch of values, depending on how you look at it. {I vaguely recall from high school that you can sum it as (1-1) + (1-1) + (1-1), and so get the sum as being zero. OR you can sum it as 1 - (1 - 1) - (1 - 1) and get a sum as being 1. OR you can do the standard summation trick: S = 1 - 1 + 1 - 1 + 1 = 1 - S, ==> S = 1/2 and you can probably get it to "sum" to other values with other manipulations. Are there some kind of [non algebraic?] extensions/definitions of 'sum' that are generally accepted for determining the "sums" of series that would appear not to have one. /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--

3 4

Re: [math-fun] Divergent sum = -1/12
by Adam P. Goucher 16 Apr '14

16 Apr '14

The reason that people attribute -1/12 to this sum is that it can be considered to be Zeta[-1], where we define Zeta[z] (z > 1 for convergence) to be: 1/1^z + 1/2^z + 1/3^z + 1/4^z + ... Then Zeta[] has a unique analytic continuation to a meromorphic function over the complex plane (with a single pole at 1), and Zeta[-1] = -1/12. That's the only reasonable evidence I've seen in favour of this. The popular `numberphile' video giving a purported `proof' using elementary methods is unconvincing hand-wavery. Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Bernie Cosell > Sent: 04/16/14 07:10 PM > To: math-fun > Subject: [math-fun] Divergent sum = -1/12 > > I'm wondering what the solid [??] mathematical basis is for sum(n) = > -1/12. I was looking at the series (which seems to be a starting place > for the "proof" of -1/12) 1 - 1 + 1 - 1 .. and it can have any of a bunch > of values, depending on how you look at it. {I vaguely recall from high > school that you can sum it as (1-1) + (1-1) + (1-1), and so get the sum > as being zero. OR you can sum it as 1 - (1 - 1) - (1 - 1) and get a sum > as being 1. OR you can do the standard summation trick: > S = 1 - 1 + 1 - 1 + 1 = 1 - S, ==> S = 1/2 > and you can probably get it to "sum" to other values with other > manipulations. > > Are there some kind of [non algebraic?] extensions/definitions of 'sum' > that are generally accepted for determining the "sums" of series that > would appear not to have one. > > /Bernie\ > > -- > Bernie Cosell Fantasy Farm Fibers > mailto:bernie@fantasyfarm.com Pearisburg, VA > --> Too many people, too few sheep <-- > > > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 2

Re: [math-fun] Aknother knight's surprise?
by Adam P. Goucher 16 Apr '14

16 Apr '14

> On 4/15/14, Adam P. Goucher <apgoucher(a)gmx.com> wrote: > > Oh, sorry, I didn't see that you needed it to be an embedding. It can't > > be embedded on the torus, since it has 36 vertices, 144 edges and an > > Euler characteristic of at most: > > > > 36 - 144 + 96 = -12 > > > > So, if you are to embed it on a surface without crossings, you'll need > > to have at least seven holes. > > Whoa! ... where does your 96 come from? WFL There are 144 edges. The maximum number of faces is achieved when every face is a triangle, in which case there are (2/3).144 = 96 triangles. Sincerely, Adam P. Goucher

2 2

[math-fun] reversing the order of bits in a word
by Bill Gosper 16 Apr '14

16 Apr '14

WDS> Let w be a 64-bit word ("unsigned long long," in C language). The following C instruction sequence w ^= w>>32; w ^= w<<32; w ^= w>>32; w ^= w>>16; w ^= w<<16; w ^= w>>16; w ^= w>>8; w ^= w<<8; w ^= w>>8; w ^= w>>4; w ^= w<<4; w ^= w>>4; w ^= w>>2; w ^= w<<2; w ^= w>>2; w ^= w>>1; w ^= w<<1; w ^= w>>1; will overwrite w with its bit-order-reversal. In general for a (2^k)-bit long word this will use 3*k shifts and 3*k XOR operations and with zero(?) or one(?) extra registers consumed for temp storage and no funny masking constants needed. -- Warren D. Smithhttp://RangeVoting.org Knuth Vol 4A, 7.1.3 has 70 pages on Bitwise Tricks and Techniques. Page 144 is Bit reversal, and may anticipate you here--I haven't read closely enough to determine. (Probably not, if Tom Karzes's "all 1s" objection resists debugging!) Certainly most of Knuth's hacks require "funny masking constants" (whose objectionability I fail to perceive). Probably the most important lesson in 7.1.3 is Knuth's strong advocacy of his MOR and MXOR (8×8 bitmatrix) instructions for inclusion in 64-bit order codes. Bit reversal takes two MORs. --rwg After Bit reversal comes Bit swapping, in which my hasty perusal fails to find the TRCE TRCE TRCE trick (HAKMEM Item 162), of which Knuth was once quite fond. It is perhaps too platform dependent? I'd think he would cite TRCE etc as ideas for future order codes, but perhaps instruction skipping is a thing of the past.

4 3

Re: [math-fun] Aknother knight's surprise?
by Adam P. Goucher 15 Apr '14

15 Apr '14

Oh, sorry, I didn't see that you needed it to be an embedding. It can't be embedded on the torus, since it has 36 vertices, 144 edges and an Euler characteristic of at most: 36 - 144 + 96 = -12 So, if you are to embed it on a surface without crossings, you'll need to have at least seven holes. Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Fred Lunnon > Sent: 04/15/14 11:31 PM > To: math-fun > Subject: Re: [math-fun] Aknother knight's surprise? > > But why is the result an embedding? WFL > > > > On 4/15/14, Adam P. Goucher <apgoucher(a)gmx.com> wrote: > >> [...] > >> > >> Whichever, is there now some way to reverse the previous identification, > >> and lift the embedding back to 36 vertices? > > > > Yes! You implied the existence of such a procedure yourself, when you said > > "vertices opposite across the torus have all neighbours in common". > > > > Specifically, for every vertex v in the 18-vertex graph, create vertices > > v_1 and v_2 in the new graph. Then connect u_i with v_j in the 36-vertex > > graph iff u is connected to v in the 18-vertex graph. > > > > The 36-vertex graph should have 2^18 times more symmetries than the > > 18-vertex graph, given by the wreath product C_2 wr G, where G is the > > automorphism group of the 18-vertex graph (as a subgroup of S_18) -- > > the one you claim (probably correctly) has order 144. > > > > > > > > Sincerely, > > > > > > Adam P. Goucher > > > > > > > >> Fred Lunnon > >> > >> > >> On 4/15/14, Fred Lunnon <fred.lunnon(a)gmail.com> wrote: > >> > On 4/15/14, Fred Lunnon <fred.lunnon(a)gmail.com> wrote: > >> >> I have posted a diagram, showing as much of the symmetry of this graph > >> >> as > >> >> planar representation allows, at > >> >> https://www.dropbox.com/s/aeea6bqlrt23tck/semi_6x6.png > >> >> Note the 4-fold diagonal coincidences --- whereby hangs another tale > >> >> entirely! > >> > > >> > Ugh --- grotesquely aliased lines --- see instead > >> > https://www.dropbox.com/s/8b0stotr8343mq2/semi_6x6.pdf > >> > > >> > The external edges obviously form a tour (closed Hamiltonian path); > >> > the remaining diagonals also form a tour, isomorphic to the first. > >> > > >> > Fred Lunnon [15/04/14] > >> > > >> >> On 4/14/14, Fred Lunnon <fred.lunnon(a)gmail.com> wrote: > >> >>> Since you dispatched 4x4 so readily, perhaps you can manage something > >> >>> about the graph genus 6x6 knight moves on a torus instead? > >> >>> > >> >>> In the 4x4 case the vertices had valency 4 instead of 8 . > >> >>> The 6x6 case degenerates as well, less predictably: vertices opposite > >> >>> across the torus have all neighbours in common; identification yields > >> >>> 18 vertices and 36 edges and valency 4 immersed on a Klein bottle. > >> >>> The symmetry group has order 144 . > >> >>> > >> >>> Fred Lunnon > >> > > >> > >> _______________________________________________ > >> math-fun mailing list > >> math-fun(a)mailman.xmission.com > >> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > > _______________________________________________ > > math-fun mailing list > > math-fun(a)mailman.xmission.com > > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 2