March 2016 - mathfun@mailman.xmission.com

Re: [math-fun] random generators
by Warren D Smith 19 Mar '16

19 Mar '16

> From: Eugene Salamin <gene_salamin(a)yahoo.com> > For cryptosecure, I don't see how you can do better than a physical noise or > quantum source.? Why do computer science people so disdain physical RNG's; > it is because they don't involve fun things like algorithm analysis?? This > annoys me so much that I've made it into a litmus test.? When I pick up a > book that discusses random number generation, I immediately look to see if > physical RNG's are discussed, not necessarily praised, and if not, I ignore > the entire book. > > Now, there is a place for pseudo-RNG's, and that is if the same sequence of > random numbers must be generated again since then the initial seed can > represent the entire lengthy sequence. --well, you've answered your own question. PRNGs are better than true-random in the sense you can re-run your program with exact same results, which is needed to be able to debug it. Also PRNGs are probably faster and also higher quality randomness (paradoxically) than true random RNGs in many cases, albeit by algorithms applied to true random bits they could be made excellent too. True random RNGs are essential for cryptographic purposes, i.e. generating something secret. A way I invented a long time ago to generate true random bits, is this. Let F(x) be a continuous function of x with |slope|=2, which maps some real interval to itself, for example if |x|<1 then F(x)=2+2x for -1<x<-1/2, -2x for |x|<1/2, 2-2x for 1/2<x<1. Build an analog circuit to compute F(x) on some voltage interval. (A circuit made of ideal op-amps and ideal diodes can do that.) Use it cyclically to compute x0=x, x1=F(x), x2=F(F(x)), x3=F(F(F(x))), etc forever. Each new analog value will contain 1 new bit of randomness. If we output the sequence sign(x_k) of bits, they will be random bits. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 2

[math-fun] random generators
by Warren D Smith 19 Mar '16

19 Mar '16

> From: Joerg Arndt <arndt(a)jjj.de> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: [math-fun] PCG: A Family of Simple Fast Space-Efficient > Statistically Good Algorithms for Random Number Generation. > Message-ID: <20160319171653.GA4808(a)jjj.de> > Content-Type: text/plain; charset=us-ascii > > As some of us are interested in random number generation, > I'd like to point to https://www.cs.hmc.edu/~oneill/ > I'll unlike find time to read the paper (preprint as > of now), so comments are welcome. --well, she sure devotes a lot of attention to "marketing" it, but I rather wish she'd devote more attention to concisely explaining it. Her actual very very long paper (submitted to ACMTOMS) is here http://www.pcg-random.org/pdf/toms-oneill-pcg-family-v1.02.pdf She ignores a lot of published good fast bigcrushable generators in her "comparison with everybody else" which makes her look better than she really is. For example, she ignored S.Vigna's "shootout" http://xorshift.di.unimi.it/, R.P.Brent's XorGens, and Mark A. Overton: Dr.Dobbs Journal (May+June 2011). In my opinion, here's what the world wants: period = 2^280 to 2^512 because cuberoot(period) is enough to violate certain "coupon collector" tests and squareroot(period) is enough to violate birthday tests (for any generator whatsoever) hence these need to be inaccessibly large. She already blows it by not realizing that, proposing for general use period<=2^64, which is absurdly stupid. But in her defense, most others do not realize it either. The world of randomness authors and implementors contains a lot of stupidity. state = a number of bits approx equal to log(period)/log(2) because otherwise you are being embarrassingly inefficient about your memory usage and will pay in speed due to eating too much cache. For example, the "mersenne twister" is an embarrassment to humanity for that reason. randomness: at least good enough to pass the bigcrush test suite. (Most library randgens aren't.) Preferably also a combination of several unrelated-looking generation methods. Most kinds of generators are theoretically bad, meaning I can cook up a reasonably natural test they fail. For example, every LCG is bad due to matrix rank tests and hyperplane spacings. Every generator that outputs the expansion of a very long-period-decimal (in some radix) rational is bad because of continued fraction tests. Every linear generator using matrix powers over GF2 is bad again because of matrix rank tests. You can hide those flaws well enough to escape the limited scrutiny of BigCrush, but the flaws are still inherently there. "Cryptographically secure" is a somewhat vague term meaning no statistical test that runs in a reasonably small amount of time, can reveal nonrandomness. This currently can only be proven (in the cases where it can be) with the aid of conjectures including P/=NP, e.g. hardness of discrete logs. It also can be conjectured directly, e.g. if you cannot think of any efficient way to crack it, you conjecture it is crypto-secure. My present view is that a good compromise is this. Combine several exceptionally fast, simple, unrelated, and well understood generators with relatively-prime periods, such as Vigna, a Weyl generator, and an Overton generator. That way you are assured high period and can also assure passing bigcrush. Now on top of that, add a crypto-secure generator which is called only occasionally so it will not slow things down much. It also should be noted that essentially any invertible map you do to an N-bit state space, will have period of order 2^N... usually... although you will rarely be able to prove that. For example "Feistel" tranformations. That fact makes it quite easy to design high period, fast, space-efficient generators that are crypto-secure. The problem is, you will not know when you have designed them, versus when you have designed crap. It is kind of like being in a room full of 95% gold bricks, but you cannot distinguish the gold bricks from the 5% fake bricks. O'Neill's fastest two generators are "PCG XSL RR 128/64 (MCG)" with period=2^126, "PCG RXS M XS 64 (LCG) " with period 2^64, and "PCG XSL RR RR 128 (LCG)" with period=2^128. What are they? I'm not sure. Here is actual C code for one of her simplest generators // *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t; uint32_t pcg32_random_r(pcg32_random_t* rng){ uint64_t oldstate = rng->state; // Advance internal state: rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1); // Calculate output function (XSH RR), uses old state for max ILP: uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u; uint32_t rot = oldstate >> 59u; return (xorshifted >> rot) | (xorshifted << ((-rot) & 31)); } so as you can see, it iterates "state" using an LCG with modulus 2^64, which is a pretty sucky thing to do. That presumably has period=2^64 albeit its rightmost bits will have far shorter periods, e.g. the rightmost bit will have period=2. It then outputs a disguised version of that state, disguised by performing some bit shifts and XORs, including a "random length" bit-rotation, and also outputting only 32 bits. This is fast, if you have a fast 64->128 multiplier. Otherwise, it is not so fast. She of course did not test on the latter kind of hardware since that would have made her look bad. I like the way she coded her random rotation primitive.

4 3

Re: [math-fun] random generators
by Henry Baker 19 Mar '16

19 Mar '16

I'll take a crack at answering this one; perhaps others will also chime in. "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." -- von Neumann You & von Neumann are right, in theory. However, all "true"/"hardware" random number generators ("TRNG"'s) are subject to measurable biases & other measurement errors, which produce various measurable correlations in their outputs. Even TRNG's need to be "whitened up a bit" by using various crypto functions -- e.g., crypto hash functions, AES boxes, etc. -- which clean up the statistics of their outputs. There have been a few recent talks about this very subject, and -- at least for the case of initializing the crypto packages of networked computers -- a TRNG is useful for producing the initial "seed", but from then on, a PRNG is a lot faster, and nowadays more reliable & trustworthy than a TRNG. And *trust* is the hardest thing to accept in a TRNG, because there's essentially no way to test it! Since you can store >500 GBytes in a chip the size of your pinky fingernail, and since such a chip could easily fit into the enclosure of most TRNG's, I know of no "black box" test to validate your TRNG. I purchased a $35 USB TRNG which utilizes electronic noise to produce a few bits, but can't produce bits fast enough for anything other than seeding a PRNG every once in a while. At 12:48 PM 3/19/2016, Eugene Salamin via math-fun wrote: >For cryptosecure, I don't see how you can do better than a physical noise or quantum source. > >Why do computer science people so disdain physical RNG's; it is because they don't involve fun things like algorithm analysis? > >This annoys me so much that I've made it into a litmus test. > >When I pick up a book that discusses random number generation, I immediately look to see if physical RNG's are discussed, not necessarily praised, and if not, I ignore the entire book. > >Now, there is a place for pseudo-RNG's, and that is if the same sequence of random numbers must be generated again since then the initial seed can represent the entire lengthy sequence.

1 0

Re: [math-fun] generating permutations
by Warren D Smith 19 Mar '16

19 Mar '16

The entire perm group S[n] is generated by the n-cycle (1,2,3,...,n) and the transposition (1,2), not sure if that suffices to make Baker happy.

2 1

[math-fun] 3D Snowflake
by Bill Gosper 19 Mar '16

19 Mar '16

Most of you know that it makes a cube: gosper.org/3dsno.png at least if you unite closed solids. The sequence of boundaries converges to a fractal that so distracted Mandelbrot that he neglected to mention its cubicalness. If each octant of this fractal is everted, so that all eight corners wind up in the center, we do not see eight "corner reflectors", but rather a hint of what BBM was trying to describe. gosper.org/unstella.svg except that the little octahedra should be little gobs of razor blades. The true limiting fractal here is the disjoint union of six copies of itself placed on the vertices of its bounding octahedron, and then scaled by 1/2. The intersection of this figure with its bounding octahedron is eight Sierpinski gaskets. --rwg Metallic instances of the "eight corner reflectors" figure are hung from boat masts as radar reflectors.

5 6

[math-fun] cyclic groups; permutations
by Henry Baker 18 Mar '16

18 Mar '16

A cyclic group has a generator that generates all of the elements of the group; i.e., it produces a permutation of the elements of the group. Different generators may produce different permutations. Is there any algebraic structure that elegantly generates *all* permutations? One problem with generators is that there aren't nearly enough of them: there's only N elements, but N! permutations. Are there any other mechanisms -- perhaps high-degree polynomial evaluation or matrices -- that can generate all (& only) permutations? Obviously, matrices can permute the elements of rows & columns, but I'm interested in 1-1 functions of the elements themselves.

3 5

[math-fun] An early success of Rich's "number recognizer"
by Bill Gosper 18 Mar '16

18 Mar '16

(= integer lattice reducer). I think I sent this long ago, but I just stumbled over the mail item, which I can never find when I'm looking for it.) In the late 70s, Robert Maas worked on adaptive data compression, and needed to solve these transcendental equations, In[597]:= FindRoot[{(1 - x)^(y - 2) x^(3 - 2 y) (1 - y)^(1 - y) y^y == 1, 1 == (1 - x)^(1 - x) x^x (1 - y) y^(x - 3)}, {x, 1`44/2}, {y, 1/2}, WorkingPrecision -> 44] for the coupled probabilities x and y: Out[597]= {x -> 0.64779887126104238549049829642576930694948772, y -> 0.54368901269207636157085597180174798652520330} We were curious whether they were algebraically independent, and fed their squares and crossterms into NUMREL, which Maas had implemented following an informal conversation with Rich. Here is a re-enactment with Mathematica's PSLQ. In[618]:= List @@ Expand[(1 + y + x)^2] Out[618]= {1, 2 x, x^2, 2 y, 2 x y, y^2} In[619]:= %.FindIntegerNullVector[% /. %597] Out[619]= 1 - 2 x y - y^2 Success! Is there any chance of a second relation? Try cubics: In[620]:= List @@ Expand[(1 + y + x)^3] Out[620]= {1, 3 x, 3 x^2, x^3, 3 y, 6 x y, 3 x^2 y, 3 y^2, 3 x y^2, y^3} In[621]:= %.FindIntegerNullVector[% /. %597] // Factor Out[621]= -3 y (-1 + 2 x - 2 x^2 + y) x and y are independently algebraic! Eliminating y, In[622]:= GroebnerBasis[{%/y, %%%}, {y, x}] // Factor Out[622]= {x (-1 + 2 x - 2 x^2 + 2 x^3), -1 + 2 x - 2 x^2 + y} So both satisfy cubics. In[625]:= Solve[0 == # & /@ (%622/{x, 1})][[1]] Out[625]= {x -> 1/3 (1 - (2 2^(2/3))/(13 + 3 Sqrt[33])^(1/3) + (13 + 3 Sqrt[33])^( 1/3)/2^(2/3)), y -> 1/18 (-6 + (32 2^(1/3))/(13 + 3 Sqrt[33])^(2/3) + ( 8 2^(2/3))/(13 + 3 Sqrt[33])^(1/3) - 2 (2 (13 + 3 Sqrt[33]))^(1/3) + (2 (13 + 3 Sqrt[33]))^(2/3))} In[627]:= N@% Out[627]= {x -> 0.6477988712610423, y -> 0.5436890126920761} as approximated earlier. --rwg

3 2

[math-fun] source of high-energy (10^15 eV) cosmic rays finally identified
by Warren D Smith 17 Mar '16

17 Mar '16

The supergiant black hole Sgr A* at the milky way center... or something near it... apparently emits very high energy cosmic rays! "Somewhere within the central 33 light years of the Milky Way there is an astrophysical source capable of accelerating protons to energies of about one petaelectronvolt, continuously for at least 1000 years" -- Emmanuel Moulin (CEA, Saclay). Acceleration of petaelectronvolt protons in the Galactic Centre, Nature, 2016 http://www.nature.com/nature/journal/vaop/ncurrent/full/nature17147.html see also http://arxiv.org/abs/1509.03425 http://www2.cnrs.fr/en/2727.htm I suppose what must happen is stuff falling into the hole collides with other stuff at extremely near light speed, emitting the rays as a result? If that is the explanation, then the speeds involved need to be so high that the kinetic energy of the collidors are a factor>10^6 times their rest masses. But would that even work? Wouldn't such rays be gravitationally red shifted so that we out here would not perceive them as ultrahigh energy -- and this could only produce run of the mill energies of order 1 GeV? So it is very hard to explain how such enormous cosmic ray energies could be produced, but at least they now have realized a fairly small source near the galaxy center can and does create them. Hmm. Here is a crazy idea. Dark matter particles fall into the hole & collide, emitting the rays as before. But hypothesize the DM particles each outmass protons by a factor 10^6. That would do the job. The highest energy accelerator on Earth, the LHC, just achieved 6.5 TeV beam energy, which is 6.5*10^12 eV, last year. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 1

[math-fun] Fold, punch, cut
by James Propp 17 Mar '16

17 Mar '16

Does anyone know how to make left-to-right mirror images of PDFs? My daughter and I had fun today using Joel Hamkins' fold-punch-and-cut PDF ( http://jdh.hamkins.org/math-for-nine-year-olds-fold-punch-cut/) and I thought that this activity would be even better with double-sided pages in which the markings appeared on both sides; this would make it both easier and more pleasant to fold the paper accurately. A simple approach would be to create mirror images of the pages; printing an image and its mirror-image on opposite sides of each sheet would create exactly what I want. Any suggestions? Jim Propp

3 2

[math-fun] Grabbing Cubes
by James Propp 16 Mar '16

16 Mar '16

Am I the only one who is dissatisfied with the solution to Problem 327 in the Playground feature of the February 2016 issue of "Math Horizons" (see http://digital.ipcprintservices.com/article/The_Playground/2387298/289441/a… , page 31)? To show that a certain cube-grabbing game always ends in 65 moves, the authors first show that an obvious way to play the game ends in 65 moves, and then show that "the algorithm for removing the maximum number of cubes at each steps takes 65 steps". But I don't see why it follows that EVERY way to play the game ends in 65 moves. Question #1: Am I right to be dissatisfied? Question #2 (assuming that the answer to Question #1 is "Yes"): Can someone provide a proof that will satisfy me? Jim Propp

7 20