June 2014 - mathfun@mailman.xmission.com

[math-fun] Bozonic boson question
by Henry Baker 24 Jun '14

24 Jun '14

"An important characteristic of bosons is that their statistics do not restrict the number that can occupy the same quantum state" https://en.wikipedia.org/wiki/Boson Ok, suppose that I want to _weigh_ one boson. I guess that most bosons are pretty light, so I'll have to weigh a bunch of identical bosons (in "the same" quantum state) & divide by their number. Q: Does this work? Is there any additional energy required to hold them together that would show up as additional mass? Or does an individual boson weigh more singly than when together in "the same" quantum state? How big is the biggest boson, anyway?

7 7

[math-fun] privacy of math-fun postings: not much
by rcs＠xmission.com 24 Jun '14

24 Jun '14

The math-fun list has 100+ subscribers. The majority are lurkers. Anyone can join. I verify the email address works, and ask new folks for "a couple of sentences about your math interests". I used to invite people to post bios, but nobody did. The archive (on xmission) is open to all subscribers. There's a pre-xmission archive (before 2002?) compressed somewhere on my disk. I generally warn new subscribers "Don't count on much privacy. Think 'coffee-house'." Strangers might overhear you, and might barge in to tell you that you misunderstand Entropy. I ask journalist members to get posters' permission before publishing material from the list. Automatic forwarding of the list to non-members isn't allowed, except to yourself and immediate family. Selected material may be sent along, and sometimes should be. We follow general customs when it comes to passing along stuff from the list: If you hear of a neat problem or puzzle, pass it on! That goes for both incoming and outgoing material. If someone asks you a question worth posting, go ahead, and tell them the good answers. If you know somebody who's working a good problem, tell them, tell us, keep connected. If you know an expert who might answer a puzzle from the list, communicate! Where appropriate, credit people. IF YOU POST HERE, THE GOOD STUFF IS GOING TO TRAVEL. IT MIGHT HAVE YOUR NAME ON IT. OR NOT. If you want/need something kept private, send a personal email. If you feel a need to debate the policy, please sit on your hands for a minutes or two before hitting Send. Keep in mind that we're constrained by reality. Rich

1 0

[math-fun] measuring the irregularity (or salamander-ness) of a planar region
by Neil Sloane 23 Jun '14

23 Jun '14

Is there a good measure of how irregular a region of the plane is? something that gives 0, say, for a circular disk, and 1 (or infinity) for a fractal gasket? the motivation is to find a measure of how irregular (or gerrymandered) a congressional district is. Neil -- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane(a)gmail.com

8 8

Re: [math-fun] gerrymandering measures
by Neil Sloane 23 Jun '14

23 Jun '14

Dear Math Fun, Thanks to everyone who responded. I have passed along the responses to the friend who asked me the question. Neil

3 5

[math-fun] counter-gerrymandering
by Henry Baker 23 Jun '14

23 Jun '14

I looked into this problem back in the 1970's, but I was never able to come up with a good intuition about how districting should work. I considered various "greedy" algorithms for growing regions starting from "seeds", but there didn't seem to be any good criteria for selecting the initial seeds. The other intuition is that of a gas under pressure living in the district where the State boundaries are rigid and the district boundaries are flexible, and the boundaries move until the pressure "equalizes". The boundary itself could have a bending energy (analogous to a physical "spline") which would tend to keep the boundaries fairly smooth. Unfortunately, this intuition/analogy only helps once the basic district is defined, and you want to allow the system to "relax" into its lowest energy state. It doesn't help choose the initial configuration. I suppose that one could come up with a "soap bubble" analogy, wherein each district started with 1/N amount of gas, where N is the number of Representatives for that State. The boundaries of these soap bubbles could move. However, I didn't see any way to guarantee that the solution would be unique and/or stable. The other problem with the "soap bubble" analogy is that the population density is extremely non-uniform, looking a lot more like fractal dust than uniform air pressure. Moving the boundary a tiny bit in a very dense region produces very large changes in the population of the district, while moving the boundary a tiny bit in a very sparse region has almost no change in the population of the district. This fractal density effect essentially _guarantees_ a fractal-like boundary, even with relatively stiff spline boundaries. Most of the suggestions I read about to make a district "compact" ignored the existing boundaries of the State in which the district would have to live. For example, if a State is long and thin, then a district in the middle will necessarily disconnect the State into districts on one side of the selected district from districts on the other side. If the State is thin enough, the problem is essentially one-dimensional, and then the boundaries can be adjusted by some sort of "pressure equalization" method. If a State has disconnected portions -- e.g., Michigan -- is a district allowed to cross the disconnect?

5 5

Re: [math-fun] Intel to incorporate FPGA in new Xeon processor
by Warren D Smith 23 Jun '14

23 Jun '14

I think this is a superb development, I've felt that should happen for a long time. It also will address a lot of issues that others (e.g. Jorg Arndt) have been complaining about for years, e.g. "why doesn't my processor have a 'reverse bit order' instruction?" This will be a hacker renaissance. It does not bother me the slightest bit that there is a big pre-wired processor accompanying the FPGA. The stuff lots of users often want, should be available hardwired for speed, not programmable for slowness. Furthermore, in the event that some FPGA use becomes commonplace idiom, that will hopefully inspire the hardware guys to make it available without the FPGA. My question would be: how should a high level language take advantage of this new hardware capability?

5 6

[math-fun] Intel to incorporate FPGA in new Xeon processor
by Warren D Smith 23 Jun '14

23 Jun '14

> So I see (at least) three types of work the FPGA could do: > > 1. Complicated work on small data---bitcoin mining and stuff > like that. FPGAs tend to do this well; no latency concerns > or memory access bottlenecks. > > 2. Streaming work. Will the FPGA have a streamable interface > to the memory hierarchy? If so, all sorts of vector work with > big computations are possible. It becomes SSE on > steroids (of course subject to memory bandwidth limitations). > > 3. Random access work. Will the FPGA have random access > to the memory hierarchy? And if so, how many memory > accesses could be in flight at one time? This would permit > another wide range of possible applications. > > I don't have high expectations for the first iteration of this --well, for example, consider the "deep blue" chess machine. Would you be able to build it in a FPGA? If so, you'd get a huge performance boost for chess programs. --for another example, suppose you are writing a SAT solver. It seems obvious (?) an FPGA could vastly speed it up. --Let's say we want to make a Lehmer-style sieve for scanning thru integers seeking one which obeys some large set of simultaneous congruences, for example you want to find N such that N is a square modulo the first J primes (but not square). I would expect these three tasks would obtain factor 100 speedups. No?

2 1

[math-fun] Intel to incorporate FPGA in new Xeon processor
by Henry Baker 23 Jun '14

23 Jun '14

FYI -- Lots of potential math applications... https://communities.intel.com/community/itpeernetwork/datastack/blog/2014/0… Disrupting the Data Center to Create the Digital Services Economy Posted by Diane Bryant in The Data Stack on Jun 18, 2014 12:56:03 PM .... But what we find even more exciting is our next innovation in processor design that can dramatically increase application performance through fully custom accelerators. **** We are integrating our industry leading Xeon processor with a coherent FPGA in a single package, socket compatible to our standard Xeon E5 processor offerings.**** Why are we excited by this announcement? The FPGA provides our customers a programmable, high performance coherent acceleration capability to turbo-charge their critical algorithms. And with down-the-wire reprogramability, the algorithms can be changed as new workloads emerge and compute demands fluctuate. Based on industry benchmarks FPGA-based accelerators can deliver >10X performance gains. By integrating the FPGA with the Xeon processor, we estimate that customers will see an additional 2X in performance thanks to the low latency, coherent interface. Our new Xeon+FPGA solution provides yet another customized option, one more tool for customers to use to improve their critical data center metric of Performance/TCO. It highlights our commitment to delivering the very best solutions across all data center workloads and our passion to lead in the transformation of the industry to cloud services. ....

7 12

Re: [math-fun] Intel to incorporate FPGA in new Xeon processor
by Henry Baker 23 Jun '14

23 Jun '14

Intel didn't say it, but I suspect that one of the applications will be changeable crypto. If you're going to incorporate AES and similar instructions, then you also have to worry that your processor might become instantly obsolete if a bug is found in one of these algorithms. Also, FPGA's allow for experimentation that will help decide what will become hard-wired instructions in the next generation of processors. At 07:33 AM 6/23/2014, Whitfield Diffie wrote: >> We are integrating our industry leading Xeon processor with a coherent >> FPGA in a single package, socket compatible to our standard Xeon E5 >> processor offerings. > > In the late sixties there was an announcement by DEC of a PDP-6 >with programmable firmware. At least, I think that is what it must >have been because what I recall is Gosper's response: if you had that, >why would you want it to be a PDP-6. My response to this is the same. > > If you have a CPU with an FPGA, why do you need anything more than >a primitive processor to manage the programming of the FPGA. Could >you not get rid of much of the legacy processor which, I assume, is >most of the Xeon. > > Whit

1 0

[math-fun] Asymptotically zero memory wasted inside dictionaries
by Warren D Smith 23 Jun '14

23 Jun '14

Consider a "dictionary" containing N items, where we support insert, delete, search-for, read-access, replace (write-access) in O(L) steps each, where L=logN. This is implementable using "balanced binary trees" such as "red black trees" or "Aa trees" which employ 2 pointers plus some small number (e.g. 1) of bits per data item. Also it can be done using "splay trees" using 2 pointers per item, and no extra bits needed, but speed guarantees now only amortized, not worst case (long pauses occasionally possible). If data items are same size as a pointer, this is a major WASTE OF MEMORY: 3X more consumed than the data itself. --------------- I now point out (which may or may not be a new observation -- I'd guess probably not new?) that there is a way to do this with far less memory wasted, and probably more efficient at the same time. (The reason for alleged "greater efficiency" is because of memory caching effects and the existence of special instructions on many processors for high speed shifts of arrays.) Let K>1 be a constant (or it could even grow slowly with N). Make each node of the tree contain not one, but rather an array of order L items consecutive in the ordering. Each node's array size is fixed, but the array may be only partly filled, knows how many items it contains. We agree that each node's array will always be within fraction 1/K of being full. To search for an item X, walk to right child if X>max array element, to left child if X<min, and binary search within the array, otherwise. To insert a new item, just do a linear insert into the array, if it is not already full; ditto for delete if contains enough items (occupancy count changed by +- 1). If it is desired to insert an item into an already-full node (or delete one from a node which has its minimum allowed occupancy; I'll focus here on insert), then we look for other nodes adjacent to this one in the ordering. We find the J closest nodes where J=1,2,...,K until finding one that is not full. Then we redistribute the array items within these J nodes to equalize their occupancy counts to within 1 and insert the new item. This all takes J times longer than a single search. If on the other hand all J=K of these nodes have full arrays, then we create a new node, redistribute items among the K+1 nodes' arrays, and insert the new item into the correct node's array, and finally, using standard balanced tree (or splay tree) methods, insert the new node into the tree. CONCLUSION: Search & access requires O(L) steps, L=logN. Insert takes O(L) steps usually, occasionally O(J*L) steps with 1<J<K, and even more rarely O(K*L) steps. Ditto delete. Here K is an arbitrary constant. If desired, we can guarantee the rareness of the longer-time kind of steps by adding "hysteresis" to the data structure, i.e. it is ok to delete until a node's array has fraction 2/K unfilled, but any multi-node redistribution is arranged to assure at most 1/K fraction unfilled. In that case, the longer-time steps can occur only a fraction K/L of the time at most, so the AMORTIZED-average time per operation is assured to be O((K/L)*K*L + L) = O(K*K+L). So we can choose K to be anywhere between 1 and sqrt(logN) while still assuring the amortized operation time is O(logN), and worst case operation time (using balanced trees) is O(logN)^2. With splay trees the worst case time could be as large as order N/L. In this case, the "waste" of memory is: 2 pointers and a few bits per K data items, which (provided K grows with N to infinity such as sqrt(logN)) asymptotically tends to ZERO waste of memory. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 4