May 2014 - mathfun@mailman.xmission.com

Re: [math-fun] General way to avoid mispredicted branches (in sorting, & probably many other tasks)
by Henry Baker 21 May '14

21 May '14

Warren: You probably already know this, but deeply pipelined units -- e.g., GPU's -- sometimes use _sorting networks_ which are more-or-less oblivious compare-and-swap straight-line instructions. Since there isn't any branching, there's no branch prediction. In graphics operations, there is often a need to sort stuff, so this is important. However, such oblivious sorting networks can cost an addition factor of logN, at least in terms of hardware, but this may acceptable in today's environment. Branch prediction reached absurd levels prior to modern multicore CPU's, and the emphasis is now away from heavy branch prediction in favor of more cores. Branch prediction basically builds several hypothetical states in parallel (requiring lots of additional registers), and only when the results of the decisions are finally available does the CPU choose the correct state to "instantiate" as the actual state. In this sense, a branch prediction CPU is very much like a two-phase database transaction, where a branch opens a new transaction, and a number of uncommitted results are computed, and when the branch decision becomes evident, the choice of the actual state becomes the "commit" part of the transaction. At 04:58 PM 5/20/2014, Warren D Smith wrote: >Suppose you are doing quicksort. >Zoing, zoing, zoing, you do compares, and suddenly you decide >"aha! this last comparison tells me I need to swap item[K]!" >And then you branch off someplace else in your program to do it. >Big lose. Mispredicted branch. > >But instead: >When your comparison sees a bad item, you conditional-load that item's >ID number into a stash (no branching needed) and continue on. >Eventually your stash gets full and you have to do a real branch to >deal with that, >but with a large enough stash-size, this can be made arbitrarily rare. > When the stash fills up (or reach end), we do all the swaps of >stashed bad items (emptying the stash), then branch back to main >code. > >This stashing technique of "deferring" all the branches, then you later do >all the stuff those branches were going to do -- but almost without >any branching -- >presumably is of pretty general applicability as a high performance >programming technique. Certainly it is applicable to quicksort. I >don't know what other problems >it is applicable to, but probably many. This should yield >substantial speedups for the right problems. (Any suggestions?) > >Meanwhile, in preliminary work, I invented a different new way to >substantially speed up quicksort, which finally beat my heapsort >implementation (which in turn beat both the >currently most-ballyhooed quicksort codes, by Bentley+McIlroy, and by >Kushagra et al, in my speed tests). Some version of this stashing >idea now might increase that lead, but haven't tried it yet. Anyhow, >at least in principle, quicksort now has excellent caching behavior, >excellent branch misprediction rates, and arbitrarily near-optimal >comparison counts (with good pivot choices) all in one algorithm. >Suckily large move counts, though. > >-- >Warren D. Smith >http://RangeVoting.org <-- add your endorsement (by clicking >"endorse" as 1st step)

2 2

Re: [math-fun] the optimum percentage of females among lab rats
by Henry Baker 21 May '14

21 May '14

At 09:07 PM 5/20/2014, Warren D Smith wrote: >is this a joke? Unfortunately, no: http://www.nature.com/nmeth/journal/vaop/ncurrent/full/nmeth.2935.html Olfactory exposure to males, including men, causes stress and related analgesia in rodents Nature Methods (2014) doi:10.1038/nmeth.2935 Received 14 November 2013 Accepted 21 March 2014 Published online 28 April 2014 We found that exposure of mice and rats to male but not female experimenters produces pain inhibition. Male-related stimuli induced a robust physiological stress response that results in stress-induced analgesia. This effect could be replicated with T-shirts worn by men, bedding material from gonadally intact and unfamiliar male mammals, and presentation of compounds secreted from the human axilla. Experimenter sex can thus affect apparent baseline responses in behavioral testing.

1 0

[math-fun] the optimum percentage of females among lab rats
by Warren D Smith 20 May '14

20 May '14

So in recent news, apparently feminists discovered, that apparently lot (all?) drug testing is done only on MALE rats. This supposedly is since "female hormone cycles add extra variability, which testers would rather avoid so we can get more confidence with fewer rats." So then this created a furore ("anti-woman conspiracy to avoid detecting sex-specific drug effects") which President Obama now has addressed in some executive order than they should use co-ed lab rats for testing from now on. Presumably, tests will now cost more, but now will detect gender differences (if any). I personally had had no idea of the male rat thing at all, until just heard about it in the news. Which leads me to wonder: what the hell do they do with all the female rats? Also -- which none of the news media I saw mentioned at all -- there is the fact that only females get pregnant. So if you wanted to find teratogen effects on embryos, presumably you'd need to test on pregnant females. But they just aren't mentioning that. Anyhow. So now I'd like us math-funners to actually take a look at the advantages and disadvantages of female rats, without the baloney. I suspect that: for some kinds of tests, you'd be better off using 100% females, for some better off with 100% males, and for some better of with co-ed, but even then the optimal sex ratio would probably not be 50-50. Be good to figure this out. Apparently there is big money involved. Females have two X chromosomes, and in each cell, one of the two (randomly selected) "deactivates" so they effectively only have 1 per cell just like males. (Otherwise, they'd be in trouble, would be like XXY males, mental retardation, gonad problems, greater cancer and heart issues, sterility, and stuff. Although apparently a goodly percentage of XXY males do not experience problems, perhaps because they can deactivate one of their X's? -- overall, it is bad for you.) As a result, which is well known to biologists but not too well known among non-biologists, females are effectively "chimeras" -- mixtures of *two* individuals. As a result, women are believed to have greater smell-abilities than men, plus a woman carrying a colorblindness gene on one of her X's can effectively have FOUR-color vision, which no man has (a man with the gene is just colorblind, i.e. 2-color vision). Anyhow, as a result of this, it seems to me if you test a drug on a female rats, in some ways you are getting two tests for the price of one. For example if you wanted to know: "does this drug cause cancer (with the mechanism related to something that is present on some X chromosomes) it seems to me you'd be better of testing it on 100%, or mostly, female rats. Meanwhile, I buy the whole hormone argument. If you felt confident enough a priori that some drug had nothing to do with hormones and gender, and if it is true hormonal cycles cause extra noise, then you presumably WOULD be better off testing it on male rats only. If your confidence of that was not 100%, though, then you'd want to test it on females too, but probably the optimum strategy (yielding the greatest utility per rat, for some definition of "utility") would be some sex-ratio between 50:50 and 0:100.

2 1

Re: [math-fun] the optimum percentage of females among lab rats
by Henry Baker 20 May '14

20 May '14

As an additional confounder, researchers have recently discovered that _male_ lab technicians (the people who perform the experiments on the rats) upset the rats much more than _female_ lab technicians. These disturbances are enough to change the chemistry of the rats prior to doing chemical analyses. Apparently, the rats respond to the male/female hormones in their handlers. This recent discovery has thrown into doubt a large amount of research performed over the past several decades, so many experiments, including many drug experiments, will have to be re-done. At 05:40 PM 5/20/2014, Warren D Smith wrote: >So in recent news, apparently feminists discovered, that apparently lot (all?) >drug testing is done only on MALE rats. This supposedly is since >"female hormone cycles add extra variability, which testers would >rather avoid so we can get more confidence with fewer rats." >So then this created a furore ("anti-woman conspiracy to avoid >detecting sex-specific drug effects") which President Obama now has >addressed in some executive order than they should use co-ed lab rats >for testing from now on. Presumably, tests will now cost more, >but now will detect gender differences (if any). > >I personally had had no idea of the male rat thing at all, until just >heard about it in the news. >Which leads me to wonder: what the hell do they do with all the female rats? > >Also -- which none of the news media I saw mentioned at all -- there >is the fact that only females get pregnant. So if you wanted to find >teratogen effects on embryos, presumably you'd need to test on >pregnant females. But they just aren't mentioning that. > >Anyhow. So now I'd like us math-funners to actually take a look at >the advantages and disadvantages of female rats, without the baloney. > >I suspect that: > for some kinds of tests, you'd be better off using 100% females, >for some better off with 100% males, and for some better of with co-ed, but >even then the optimal sex ratio would probably not be 50-50. >Be good to figure this out. Apparently there is big money involved. > >Females have two X chromosomes, and in each cell, one of the two >(randomly selected) >"deactivates" so they effectively only have 1 per cell just like >males. (Otherwise, >they'd be in trouble, would be like XXY males, mental retardation, >gonad problems, greater cancer and heart issues, sterility, and stuff. > Although apparently a goodly percentage of XXY males do not >experience problems, perhaps because they can deactivate one >of their X's? -- overall, it is bad for you.) As a result, which is >well known to biologists but not too well known among non-biologists, females >are effectively "chimeras" -- mixtures of *two* individuals. As a result, women >are believed to have greater smell-abilities than men, plus a woman carrying >a colorblindness gene on one of her X's can effectively have >FOUR-color vision, which no man has (a man with the gene is just >colorblind, i.e. 2-color vision). Anyhow, as a result of this, it >seems to me if you test a drug on a female rats, in some ways you are >getting two tests for the price of one. For example if you wanted to >know: "does this drug cause cancer (with the mechanism related to >something that is present on some X chromosomes) >it seems to me you'd be better of testing it on 100%, or mostly, female rats. > >Meanwhile, I buy the whole hormone argument. If you felt confident >enough a priori that some drug had nothing to do with hormones and >gender, and if it is true hormonal cycles >cause extra noise, then you presumably >WOULD be better off testing it on male rats only. If your confidence of that >was not 100%, though, then you'd want to test it on females too, but probably >the optimum strategy (yielding the greatest utility per rat, for some >definition of "utility") >would be some sex-ratio between 50:50 and 0:100.

1 0

[math-fun] Veit Elser's Penrose conformal maps paper
by Warren D Smith 20 May '14

20 May '14

I find reading this paper painful but think it probably is good underneath. The painfulness comes from the large length compared with the small amount of "here's a satisfying result for you". Specifically, it seems to me, that you must have shown, that you can write down a certain formula, for an analytic function of two variables, in closed form (using Schwarz Christoffel) such that complex plane "sections" of this function (1 complex dimensional sections of 2 complex dimensional thing) have level sets describing quasiperiodic Penrose-tiling-like sets. [Meanwhile other sections of other such functions lead to (boring) doubly-periodic sets and correspond to elliptic functions.] Right? So then my question would be -- since that seems to be the whole point your paper is (or should be) driving at -- why didn't you actually do it? Write down a freaking formula and get a Penrosian set! If you were really ambitious you could then actually compute some pictures...

2 1

Re: [math-fun] Groups all of whose automorphisms are inner
by Warren D Smith 20 May '14

20 May '14

> Subject: [math-fun] Groups all of whose automorphisms are inner > Message-ID: > <1400633545.44072.YahooMailNeo(a)web162102.mail.bf1.yahoo.com> > Content-Type: text/plain; charset=iso-8859-1 > > Are there theorems that characterize groups all of whose automorphisms are > inner?? For example, for a finite group, the characters of a matrix > representation must be algebraic integers, and the presence of a > non-rational integer in the character table betrays the existence of an > outer automorphism. > ? --? Gene --is the group An (n!/2 even permutations of n items) a counterexample? It has an outer aut (conjugation with an odd perm), but at least for A3=C3 all characters are ordinary integers, hence no "betrayal" of the outer automorphism. C4 is another counterexample. So your test is (assuming valid) only a 1-sided test. However, it might be that there are not very many such counterexamples, and hence after some enumerated list of exceptions are excluded then your test might become a genuine test. This hopefully could be proven using the Classification Theorem, i.e. all finite simple groups and their character tables are known. All finite groups arise by "gluing together" simple groups. If we could argue that, there is an outer aut exactly when the glued simples include at least one with an outer aut, and if we further could argue about the character tables... then maybe prove something. (This is all speculative, I'm raving here.)

1 0

[math-fun] Groups all of whose automorphisms are inner
by Eugene Salamin 20 May '14

20 May '14

Are there theorems that characterize groups all of whose automorphisms are inner? For example, for a finite group, the characters of a matrix representation must be algebraic integers, and the presence of a non-rational integer in the character table betrays the existence of an outer automorphism. -- Gene

2 1

Re: [math-fun] Groups all of whose automorphisms are inner
by Warren D Smith 20 May '14

20 May '14

> Subject: [math-fun] Groups all of whose automorphisms are inner > Message-ID: > <1400633545.44072.YahooMailNeo(a)web162102.mail.bf1.yahoo.com> > Content-Type: text/plain; charset=iso-8859-1 > > Are there theorems that characterize groups all of whose automorphisms are > inner?? For example, for a finite group, the characters of a matrix > representation must be algebraic integers, and the presence of a > non-rational integer in the character table betrays the existence of an > outer automorphism. > ? --? Gene --is the group An (n!/2 even permutations of n items) a counterexample? It has an outer aut (conjugation with an odd perm), but at least for A3=C3 all characters are ordinary integers, hence no "betrayal" of the outer automorphism. C4 is another counterexample. So your test is (assuming valid) only a 1-sided test. However, it might be that there are not very many such counterexamples, and hence after some enumerated list of exceptions are excluded then your test might become a genuine test. This hopefully could be proven using the Classification Theorem, i.e. all finite simple groups and their character tables are known. All finite groups arise by "gluing together" simple groups. If we could argue that, there is an outer aut exactly when the glued simples include at least one with an outer aut, and if we further could argue about the character tables... then maybe prove something. (This is all speculative, I'm raving here.)

1 0

[math-fun] pi day, (a bit late)
by Simon Plouffe 20 May '14

20 May '14

Hello, a certain Ed Karrell used a couple of pc's equipped with 4 NVIDIA Gpu cards (GTX 690 and GTX 680) to compute the 8,000,000,000,000,000 'th position in binary of pi which is 0, using Bellard's formula and mine. That computer uses 1100 watts. some details are given here : http://www.karrels.org/pi/ best regards, simon plouffe

1 0

[math-fun] General way to avoid mispredicted branches (in sorting, & probably many other tasks)
by Warren D Smith 20 May '14

20 May '14

Suppose you are doing quicksort. Zoing, zoing, zoing, you do compares, and suddenly you decide "aha! this last comparison tells me I need to swap item[K]!" And then you branch off someplace else in your program to do it. Big lose. Mispredicted branch. But instead: When your comparison sees a bad item, you conditional-load that item's ID number into a stash (no branching needed) and continue on. Eventually your stash gets full and you have to do a real branch to deal with that, but with a large enough stash-size, this can be made arbitrarily rare. When the stash fills up (or reach end), we do all the swaps of stashed bad items (emptying the stash), then branch back to main code. This stashing technique of "deferring" all the branches, then you later do all the stuff those branches were going to do -- but almost without any branching -- presumably is of pretty general applicability as a high performance programming technique. Certainly it is applicable to quicksort. I don't know what other problems it is applicable to, but probably many. This should yield substantial speedups for the right problems. (Any suggestions?) Meanwhile, in preliminary work, I invented a different new way to substantially speed up quicksort, which finally beat my heapsort implementation (which in turn beat both the currently most-ballyhooed quicksort codes, by Bentley+McIlroy, and by Kushagra et al, in my speed tests). Some version of this stashing idea now might increase that lead, but haven't tried it yet. Anyhow, at least in principle, quicksort now has excellent caching behavior, excellent branch misprediction rates, and arbitrarily near-optimal comparison counts (with good pivot choices) all in one algorithm. Suckily large move counts, though. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0