June 2014 - mathfun@mailman.xmission.com

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

04 Jun '14

I'm sorry to be so cynical, but I expect this to show up as a patented "new" invention, thanks to the patent office amnesia to anything that happened in computer science prior to perhaps 1980. Unless Knuth tells me that this is new, I would suspect that this is another example of wheel-reinvention. At 05:49 PM 6/2/2014, Thomas Colthurst wrote: >Those interested in this topic will probably enjoy > >http://research.microsoft.com/pubs/209622/patsort-sigmod14.pdf > >"Patience is a Virtue: Revisiting Merge and Sort on Modern Processors" > >Abstract: > >The vast quantities of log-based data appearing in data centers has generated an interest in sorting almost-sorted datasets. > >We revisit the problem of sorting and merging data in main memory, and show that a long-forgotten technique called Patience Sort can, with some key modifications, be made competitive with todayâs best comparison-based sorting techniques for both random and almost sorted data. > >Patience sort consists of two phases: the creation of sorted runs, and the merging of these runs. > >Through a combination of algorithmic and architectural innovations, we dramatically improve Patience sort for both random and almost-ordered data. > >Of particular interest is a new technique called ping-pong merge for merging sorted runs in main memory.

1 0

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

03 Jun '14

In computer architectures, branch prediction "works" only to the extent that the probability of one arm is substantially smaller than the other arm. If both arms are equally likely, then many/(most?) branch prediction schemes will actually do worse, since the overheads for the branch prediction scheme aren't paid for on either arm. The best sorting algorithms arrange for the comparisons to be "most informative" -- i.e., their branch probabilities are very close to 1/2 -- so traditional "branch prediction" isn't going to be very helpful. Now to the extent that you can defer branches and deal with the consequences later may allow you to overlap some activity so that previously sequential operations are now in parallel. However, you should be aware that for most modern CPU's, things like "instruction fetch" are more-or-less free, since instruction fetch units typically fetch instructions from both branch paths. 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.

3 2

[math-fun] 497503 again
by Bill Gosper 03 Jun '14

03 Jun '14

Besides Do[If[! MemberQ[{1, 495508}, #], Print[k -> #]] &@ PowerMod[k, 497502, 497503], {k, 3333}] 499->496505 997->496506 998->998 1497->496505 1994->496506 1996->496505 2495->998 2991->496506 2994->998 497503 is the smallest pseudoprime k ⊥ 210 ∋ In[272]:= Mod[{2*265^k, 184^k + 183^k + 163^k}, k] /. k -> 497503 Out[272]= {435159, 435159} "Proof": In[273]:= Block[{d, a = B + C, b = C + A, c = A + B, A = 102, B = 82, C = 81}, d = c + C; Reap[Do[If[! PrimeQ[k] && ! MemberQ[carms, k] && CoprimeQ[k, 210] && Divisible[ 2*PowerMod[d, k, k] - PowerMod[a, k, k] - PowerMod[b, k, k] - PowerMod[c, k, k], k], Sow[{k, d, c, b, a}]], {k, 2, 497504}]]] Out[273]= {Null, {{{497503, 265, 184, 183, 163}}}} --rwg I'm converting to "anticlockwise". Counterclockwise is just the same as clockwise, but restricted to clocks sitting on counters. Or perhaps a counterclock is merely digital, so counterclockwise means showing consecutive numerals, mod 60.

1 0

[math-fun] David Wilson's 1-dimensional gun in Ponder This
by Michael Kleber 03 Jun '14

03 Jun '14

Hey Funsters, Oded Margalit's "Ponder This" puzzle this month is a bit about the "1-Dimensional Gun" model that David Wilson introduced here in June 2012. I told Oded about it when we were both speaking at the ITA workship in San Diego in February. http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/May2014.html The question Oded asked: "Every second, a gun shoots a bullet in the same direction at a random constant speed between 0 and 1. The speeds of the bullets are independent uniform random variables. Each bullet keeps the exact same speed and when two bullets collide, they are both annihilated. After shooting 20 bullets, what is the probability that eventually all the bullets will be annihilated?" Oded has a closed form for the probability of all bullets being annihilated when you shoot 2n of them, but not, I think, the probability of 2k>0 surviving. --Michael -- Forewarned is worth an octopus in the bush.

1 1

[math-fun] 497503=499*997
by Bill Gosper 02 Jun '14

02 Jun '14

In[49]:= Table[PowerMod[k, 497502, 497503], {k, 69}] Out[49]= {1, 495508, 1, 1, 495508, 495508, 495508, 495508, 1, 1, 495508, 1, 1, 1, 495508, 1, 495508, 495508, 1, 495508, 495508, 1, 1, 495508, 1, 495508, 1, 495508, 495508, 1, 1, 495508, 495508, 1, 1, 1, 495508, 495508, 1, 1, 495508, 1, 495508, 495508, 495508, 495508, 495508, 1, 1, 495508, 495508, 1, 1, 495508, 1, 1, 1, 1, 1, 495508, 495508, 495508, 495508, 1, 495508, 1, 1, 495508, 1} ? --rwg

1 2

[math-fun] Lunnon critical point theorem, counterexample
by Warren D Smith 02 Jun '14

02 Jun '14

Yesterday I proposed the intrinsic criterion for real 2-space zero-detection below. Nobody has yet shot it down --- which may well of course be because nobody has actually read it --- so I shall press on, making the optimistic assumption that it involves no grossly obvious errors. << Lunnon: Theorem: Given a continuously differentiable function f(x, y) , and a compact region R of the plane ( |R^2 ) with f nonzero on the boundary of R : f has a zero within R if and only if there is some (intrinsic critical) point (x, y) in R where *** df/dx = f = 0 ***. Proof (offered tentatively): By the implicit function theorem, the constraint f(x, y) = 0 defines a function x(y) single-valued in any interval of y where df/dx <> 0 . Such an interval meeting R is finite since R is compact, and its endpoints lie in the interior of R since f <> 0 on the boundary; therefore df/dx = 0 at those endpoints. The converse is trivial. QED. WDS: I think this is valid.

1 0

[math-fun] primes - data compression
by Warren D Smith 02 Jun '14

02 Jun '14

RWG: Well this all certainly looks handy, but at the moment I was just looking at how concisely the first "few" primes can be specified, mathematically or algorithmically. I guess I need to stipulate that it shouldn't slow down much with increasing primes. WDS; Oh. Well, there is actually a spectrum of answers to that question. I mean, at one end, you can specify all the primes via a short definition of what it means to be prime -- O(1) bits, but that is slow. On other end, you can tabulate all primes up to N, very non-concise (N bits), but very fast. If we specify a pseudoprime test and then merely tabulate pseudoprimes up to N, we can get much smaller storage needs and still the time is polynomial in logN. However, known estimates for how many pseudoprimes there are up to N, indicate that your storage needs will still exceed N^0.9999 bits eventually, so this ultimately is not a big win. The AKS primality test has no exceptions. Pomerance et al 1980 invented a pseudoprime test which later was shown to have no failures for 64-bit integers -- although using Erdosian reasoning it is likely it has an infinite number of failures eventually. Pomerance in fact outlined how to find a failure example but the computation he suggested was too large for anybody so far to run to completion. http://www.pseudoprime.com/dopo.pdf But nobody has ever found any failure in spite of a money prize and 34 years. My test which also never fails for 64-bit integers has the same conjectured behavior, but is faster than, the Pomerance et al test. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] zeros in ball-shaped regions
by Warren D Smith 02 Jun '14

02 Jun '14

incidentally, a related (?) theorem I discovered in the late 1980s is this. Let f(z) be a function analytic within in some ball-shaped compact region R of complex z plane with connected interior. THEOREM: If Re(f), Im(f), Re(f), Im(f) have zeros in that order as we walk round the boundary of R, then f() has a zero inside R. Note, am assuming Re(f) has no other zeros, and Im(f) no others, on boundary(R). You may enjoy proving that. At the time I considered it too easy to publish. On the other hand if we keep on finding such "easy" theorems (e.g. the one Andy Latto just proved is now incredibly easy, although it did not look as easy back when I proved it :) ... put them all together in a pile and it gets more interesting. What also might make it more interesting is if we had some sort of strengthened to "if and only if" version of the present post's theorem... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] prime tests
by Bill Gosper 01 Jun '14

01 Jun '14

Warren> If what you are seeking is never-fail primality tests, the following is the fastest I have that never fails for 32-bit unsigned integers: uint SmithIsPrime32(uint32 p){ //TRUE iff p is a prime and <=32 bits long. uint hash; if((p&1)==0){ return(p==2); } if( !StrongPsp232(p) ){ return(FALSE); } //base 2 strong psuprime test if(p<2047){ return(TRUE); } if( !StrongPsp32(p, 63778) ){ return(FALSE); } //base 63778 ditto hash = (p*2869299540U)>>25; assert(hash < 128); return(hash63778tab[hash]!=p); //perfect hash table of exceptions } where you need this array const uint hash63778tab[128] = { //these 50 numbers are the only nonprime odd spsp{2,63778} below 2^32: 979363153, 0, 0, 643552909, 0, 8725753, 0, 0, 0, 0, 329153653, 48191653, 0, 8036033, 0, 3116107, 0, 0, 839280691, 0, 450866021, 0, 0, 0, 0, 0, 0, 2269093, 0, 0, 0, 0, 0, 2693739751, 0, 2717428033, 1464568381, 0, 0, 0, 0, 1714322377, 1140573601, 0, 0, 63318169, 0, 0, 4157008813, 0, 0, 220729, 0, 0, 0, 0, 0, 3207297773, 0, 0, 0, 385319089, 1930534453, 0, 0, 0, 1054999441, 787085857, 0, 0, 2017509601, 0, 0, 967287751, 1272866167, 0, 3548378341, 3274264033, 0, 0, 0, 2206095589, 2766006253, 453366029, 176030977, 126132553, 0, 0, 0, 0, 3242533897, 0, 1121176981, 0, 2181961, 0, 0, 17208601, 0, 0, 0, 0, 48316969, 741751, 724969087, 0, 0, 0, 43661257, 0, 0, 0, 0, 0, 0, 1153164097, 1104194521, 0, 3323829169, 0, 765378241, 22591301, 1894909141, 3900327241, 60547831, 0, 1328256247, 0 }; and you also need to code up the strong PSP test (which I did). For 64-bit unsigned integers I also have a never-fail test which on average over all odd numbers takes only about 10% more time. It is somewhat harder to describe though, it involves both a strongPSP (base 2) test and a "Lehmer-Smith test." I can supply C code file. <WDS Well this all certainly looks handy, but at the moment I was just looking at how concisely the first "few" primes can be specified, mathematically or algorithmically. I guess I need to stipulate that it shouldn't slow down much with increasing primes. Not all of you may have seen Dean Hickerson's Life pattern (~3500 dots) that enumerates the primes by building a sieve. Nor Adam Goucher's two dot(!!), ten state riff (Golly>Patterns>Life>Miscellaneous>calcyman-primer) which NeilB points out could be one dot with a few more states. WDS> The first pseudoprimes for my 64-bit never-fail tests are not known and probably exceed 10^100 (if they exist, which they probably do). <WDS Is this one of those experimentally flawless tests that Erdös predicted will eventually fail almost always? --rwg

1 0

Re: [math-fun] algebraic geometry query
by rcs＠xmission.com 01 Jun '14

01 Jun '14

The note below is from Dan. It was trapped by the ever-mysterious mailing list filter. --Rich ----- Date: Sun, 1 Jun 2014 12:06:35 -0700 (GMT-07:00) Subject: Re: [math-fun] algebraic geometry query From: Dan Asimov <dasimov(a)earthlink.net> CORRECTION: Where I wrote "In R^n, let W be a compact connected (n-1)-dimensional submanifold with connected boundary M = bd(W)," the dimension of W should be n as below (and not n-1). Also, the affiliation is no longer current. --Dan ----- Hmm, Why wouldn't C^0 (just continuous) work. In R^n, let W be a compact connected n-dimensional submanifold with connected boundary M = bd(W). Claim: ------ If a continuous function f: W -> R^1 (= the reals) for which 0 lies in f(W) but not in f(M), then f must have an absolute extremum in int(W) = W - M. Proof à la Latto: ----------------- Since f is continuous on the compact set W, it must have both an absolute minimum and an absolute maximum on W. Since f is nonzero on the connected set M, f must take M into either (0,oo) or (-oo,0). If the former, f must have a local minimum in int(W); if the latter f must have a local maximum in int(W). [ ] Corollary: ---------- If f is also differentiable on int(W), then it has a critical point there (since any local extremum x of a function differentiable in a neighborhood of x must have a critical point at x). -----

1 0