April 2017 - mathfun@mailman.xmission.com

[math-fun] Simplified division?
by David Wilson 22 Apr '17

22 Apr '17

Given 64-bit unsigned integer n and 0 <= k <= 63, can floor(n/(1 + 2^-k)) be computed more quickly than by general integer division?

3 2

[math-fun] Trig question
by David Wilson 22 Apr '17

22 Apr '17

Is there anything mathematically interesting about the function f(a, b) = arctan(tan(a) + tan(b))?

1 0

[math-fun] Discrete Log Webpage
by rcs＠xmission.com 21 Apr '17

21 Apr '17

For those of us interested in the discrete log problem for finite fields, a new page summarizing progress. --rcs --- From: Laurent Grémy <laurent.gremy(a)inria.fr> To: NMBRTHRY(a)LISTSERV.NODAK.EDU Subject: Database of computations of discrete logarithms Dear Number Theorists, We are pleased to present the discretelogdb project. The aim of this project is to list all the computations of discrete logarithms in finite fields of any characteristic, with references. We have chosen to list the complete computations (with an individual logarithm computation of a given target in the considered finite field). We have obviously used the announcements send on this list, and also the research articles that report such computations. To consult the data we have collected, you can take a look at the website https://members.loria.fr/LGremy/dldb/index.html If you find wrong data or want to supplement the data we have, you are welcome to go to https://gitlab.inria.fr/dldb/discretelogdb and follow the CONTRIBUTING readme to improve the database. Thanks in advance for your contributions. Best regards. Laurent Grémy and Aurore Guillevic

1 0

[math-fun] Sudoku Theorem
by rcs＠xmission.com 21 Apr '17

21 Apr '17

I've come across a Sudoku theorem. A bit of web searching didn't turn up anything quite like it. It isn't particularly helpful in solving them, but it seems worth reporting. Maybe someone can take it further. Within a 9x9 Sudoku, look at a horizontal block of three subsquares, forming a rectangle with three rows and nine columns. Within each 3x3 subsquare, consider the sets of three horizontal cells, *** ignoring the cells' order *** within each 1x3 rectangle. Then there are only two possible patterns of the 3x9 rectangle: abc ghi def def abc ghi Rare ghi def abc abc efg hid hig abd efc Common efd hic abg In the rare case, the horizontal triples abc, def, ghi rotate (either up or down) in the successive 3x3 subsquares. In the common case, each horizontal triple in the first subsquare has a pair of values that stay together in the second and third subsquares. In the example above, the pairs are ab, ef, and hi. The pairs rotate (either up or down) in successive boxes. The other three values (in the example, c, d, and g) rotate in the opposite direction. The proof (below) is easy, using the usual exclusion rules. This may explain why the theorem isn't much help in solving: The solver automatically applies the exclusion rules in each particular puzzle, deducing anything that the theorem provides. It does seem to work best in midgame, but usually there are a few different possible ways to assign the blank cells in a partially filled-in situation. I haven't explored trying to use both horizontal and vertical restrictions together. Proof: Name the three cells in the top left 1x3 rectangle ABC. In the middle subsquare, it's possible that ABC are still together in either the middle row or the bottom row. If so, the rare case follows immediately. Otherwise, if ABC are split up between the middle and bottom rows of the middle subsquare, two of them must be together, say AB, and assume they are in the middle row: ABC ... ... ... AB. ... ... ..C ... Filling in the right subsquare: ABC ... ... ... AB. ..C ... ..C AB. Naming some remaining cells D and EF: ABC ... ... ... ABD EFC ... ..C AB. Then DEF must occupy the lower left triple: ABC ... ... ... ABD EFC EFD ..C AB. Naming the remaining cells in the bottom row HI and G: ABC ... ... ... ABD EFC EFD HIC ABG The rest follows: ABC EFG HID HIG ABD EFC EFD HIC ABG [QED] I've arranged the pairs on the left of each 3x3 subsquare, and the singletons C,G,D on the right, to make the rotations obvious. In a real Sudoku, the arrangement within each 1x3 triple can be anything. The theorem is a description at a different level than the usual situation, where the possibilities for individual cells are listed, but listing combinations is infrequent. In an average midgame, I can examine the six 3x9 rectangles and make various deductions. If I see two values together in two of the three subsquares, they must be together in the third subsquare, and the direction of pair rotation is also determined. Usually the rare case is immediately obvious or refuted. Moreover, in the common case, I know that three of the nine values must rotate in one direction, and six in the other. Whenever a value occurs in two subsquares, the rotation direction is determined. Often, the pairs can be worked out from this, or the singletons. This usually doesn't determine values in a cell, but may allow some possibilities to be excluded. Rich

1 0

[math-fun] Ambitious data management endeavor by Wolfram
by Bill Gosper 21 Apr '17

21 Apr '17

http://blog.stephenwolfram.com/2017/04/launching-the- wolfram-data-repository-data-publishing-that-really-works/#more-12901 (Stub) https://datarepository.wolframcloud.com/category/Mathematics/ --rwg

1 0

[math-fun] http://mathworld.wolfram.com/SphericalSpiral.html still disputes my old rhumb (= loxodrome) math-fun
by Bill Gosper 17 Apr '17

17 Apr '17

Despite the constant-heading definition, the graph (http://mathworld.wolfram.com/images/eps-gif/SphericalSpiral_700.gif) clearly shows a course approximating due west near the poles, but about 30º north of west near the equator. Here is the old(!) mail minus a long list of ~b (BCC), some deceased. math-fun(a)optima.cs.arizona.edu rhumb lines ~c [Eric Weisstein](a)wolfram.com Date: (unfortunately missing) Under "Spherical Spiral", Eric's Stupendium (at least the versions I can access) gives "The path taken by a ship which travels from the south pole to the north pole of a Sphere while keeping a fixed (but not Right) Angle with respect to the meridians. The curve has an infinite number of loops since the separation of consecutive revolutions gets smaller and smaller near the poles. It is given by the parametric equations [...]" which are equivalent to [x,y,z]= cos(t) sin(t) a t [---------------, ---------------, - ---------------]. 2 2 2 2 2 2 sqrt(a t + 1) sqrt(a t + 1) sqrt(a t + 1) He also gives [the above-mentioned] 3D plot for some unspecified value of a, which presumably depends on the ship's heading. Leaving aside the problems of navigability at the south pole, and of having any initial heading other than due north, this still can't be right. The coils of a rhumb line do not, in fact, appear to bunch up at the poles because the curve approaches a logarithmic spiral, and has finite total arc length. It indeed has infinite winding number, but due to their exponential shrinkage, only a few coils are visually discernable. E.g., for a northwest heading, each orbit of the pole gets you a factor of e^(2 pi) ~ 535.5 closer, so you don't even see a full turn. As a further check, I get as the unit due north (tangent to the unit sphere) vector from the above curve: a t cos(t) a t sin(t) 1 [---------------, ---------------, ---------------], 2 2 2 2 2 2 sqrt(a t + 1) sqrt(a t + 1) sqrt(a t + 1) which dotted with the unit tangent to the curve gave me a - --------------------, 2 2 2 sqrt(a t + a + 1) which should not depend on t. For a heading of a radians west of north, I propose instead the formula t t [sin(t) cos(tan(a) log(tan(-))), sin(t) sin(tan(a) log(tan(-))), - cos(t)], 2 2 which runs from south pole to north as 0 < t < pi. This paramaterization has the virtue that arc length s is merely t sec a. [Now that there's Mathematica, Out[398]= {Cos[Log[Tan[t/2]] Tan[a]] Sin[t], Sin[t] Sin[Log[Tan[t/2]] Tan[a]], -Cos[t]} In[399]:= ArcLength[%, {t, 0, t}] Out[399]= t Sqrt[Sec[a]^2] ] Thus sailing northwest [a = -π/4, gosper.org/NW rhumb.png] will get you to the pole only sqrt 2 times slower than sailing due north. Unfortunately, you are killed by centrifugal whiplash [assuming you personally have a positive radius] before being able to contemplate the miracle of having sailed northwest to a point not northwest of anywhere. [ --rwg]

1 1

Re: [math-fun] Unstoppable Brilliance: Irish Geniuses and Asperger's Syndrome
by Fred Lunnon 16 Apr '17

16 Apr '17

Having spent my professional life around comp. science and maths departments, I noticed decades ago that any "neurotypical" individual happening to stray into such realms stood out like a proverbial sore thumb. The introduction of this book reads like a personality test checklist for their academic denizens --- I found myself nodding in recognition sufficiently often to qualify under "repetitive behaviour" --- in addition, that is, to a substantial proportion of the remainder! WFL On 4/16/17, Douglas Rogers <dgrbgsu(a)gmail.com> wrote: > William Rowan Hamilton and more ... > > > * Michael Fitzgerald, Antoinette Walker > Unstoppable Brilliance: Irish Geniuses and Asperger's Syndrome > (liberties Press <http://www.libertiespress.com/>, Dublin, 2006) > <https://books.google.com/books?id=EU0xBwAAQBAJ> > > Michael Fitzgerald is Henry Marsh Professor of Child and Adolescent > Psychiatry > at Trinity College Dublin and is the leading expert on Asperger's syndrome > and > autism in Ireland. He has written extensively about these subjects and > addressed > national and international symposia on them. >

1 0

[math-fun] Things my mother never told me
by Fred Lunnon 14 Apr '17

14 Apr '17

As a companion piece to the well-known(-ish!) 1 + 2 + 3 + ... = -1/12 https://terrytao.wordpress.com/2010/04/10/the-euler-maclaurin-formula-berno… the guru has recently given us to understand that (loosely speaking) "the number of finite sets is e " https://terrytao.wordpress.com/2017/04/13/counting-objects-up-to-isomorphis… --- should small children be permitted to overhear such seditious material, one wonders? WFL

2 1

[math-fun] Draft of my April 2017 blog post
by James Propp 11 Apr '17

11 Apr '17

I started writing a new draft titled "More about .999..." and would appreciate feedback. I plan on publishing it on April 17. Suggestions for references, and comments of all kinds, are welcome. Keep in mind that all math-fun feedback goes into one mail-feed, so I won't know whose feedback is whose unless you sign your comment. Also, all substantive suggestions that I use will be acknowledged (unless you specifically ask me not to do this). Please leave your feedback here: https://mathenchant.wordpress.com?p=1591&shareadraft=58ebef1e6b78a Title: More about .999… Beginning: I thought my last essay on .999... was pretty good until I asked some of my students what they got out of it; then I got a humbling jolt of pedagogical reality. The students agreed that .999... is the limit of the sequence .9, .99, .999, etc., and they also agreed that the limit of that sequence i... Read more: https://mathenchant.wordpress.com?p=1591&shareadraft= 58ebef1e6b78a Thanks, jamespropp

3 2

[math-fun] Calculating asinh(x)
by Bill Gosper 10 Apr '17

10 Apr '17

Of perhaps only historical interest are the digit-at-a-time CORDIC methods based on tables and trigonometric addition formulæ: https://en.wikipedia.org/wiki/CORDIC , (which claims bombers as recent as the B58 used analog navigation computers). Here's my take on Sinh and ArcSinh. For illustration, simulate a fixed table of floating point "rotation" matrices Cosh[2^n] -I Sinh[2^n] I Sinh[2^n] Cosh[2^n] via the function cish[n_] := cish[n] = {{Cosh@#, -I Sinh@#}, {I Sinh@#, Cosh@#}} &[2^n] here left unfloated, again for illustration. In practice, we'd only store the two real floats Cosh[2.^n],Sinh[2.^n], or possibly Tanh[2.^(n-1)],Sinh[2.^n]. Then to compute Sinh[r] In[53]:= CISh[r_Real] := Block[{L, s}, {L, s} = RealDigits[r, 2]; MapIndexed[MatrixPower[cish[s - #2[[1]]], #1] &, L /. {a__, 0 ..} :> {a}]] I.e., use the bits of r's mantissa as exponents of successive "rotation" matrices (which incidentally commute). s is the exponent. The /. {a__, 0 ..} :> {a}] just drops trailing 0s from the mantissa bits. MapIndexed automatically assign {1}, {2}, ... to #2 while assigning consecutive mantissa bits to #1. E.g., to compute Sinh[69./128] In[56]:= CISh[69./128] Out[56]= {{{Cosh[1/2], -I Sinh[1/2]}, {I Sinh[1/2], Cosh[1/2]}}, {{1, 0}, {0, 1}}, {{1, 0}, {0, 1}}, {{1, 0}, {0, 1}}, {{Cosh[1/32], -I Sinh[1/32]}, {I Sinh[1/32], Cosh[1/32]}}, {{1, 0}, {0, 1}}, {{Cosh[1/128], -I Sinh[1/128]}, {I Sinh[1/128], Cosh[1/128]}}} (Recall that 69 = octal(105) = binary(1000101).) Again, in practice, these matrices would be simply pairs of "reals". Multiplying them, In[58]:= Dot @@ %% // FullSimplify Out[58]= (Cosh[69/128] -I Sinh[69/128] I Sinh[69/128] Cosh[69/128] gets our Sinh, with the Cosh to boot. Using Tanh[t/2] instead of Cosh[t] is attractive because, as with real rotations, we can replace each matrix multiplication with three lossless skews: (1 -I Tanh[t/2] 0 1) . (1 0 I Sinh[t] 1) . (1 -I Tanh[t/2] 0 1) For ArcSinh, e.g. to recover 69/128 from Sinh[69/128] (a float, remember), we negate the Sinh: %58 /. Sinh@x_ :> -Sinh@x Out[76]//MatrixForm= (Cosh[69/128] I Sinh[69/128] -I Sinh[69/128] Cosh[69/128]) (we also need the Cosh, which will cost us a √,) and then scan our original cish table large-to-small, only multiplying by the matrices which don't overdeplete: In[61]:= FullSimplify[%%.cish(0)] Out[61]= (cosh(59/128) -I sinh(59/128) I sinh(59/128) cosh(59/128)) (Oops, 0 overdepleted.) In[62]:= FullSimplify[%%%.cish(-1)] Out[62]= (cosh(5/128) I sinh(5/128) -I sinh(5/128) cosh(5/128)) In[63]:= FullSimplify[%.cish(-2)] Out[63]= (cosh(27/128) -I sinh(27/128) I sinh(27/128) cosh(27/128)) Oops, -2 overdepleted. In[66]:= FullSimplify[%%%%.cish(-5)] Out[66]= (cosh(1/128) I sinh(1/128) -I sinh(1/128) cosh(1/128)) In[68]:= FullSimplify[%%.cish(-7)] Out[68]= (1 0 0 1) The correct depleters were -1, -5, and -7: In[69]:= Total[2^{-1,-5,-7}] Out[69]= 69/128 which is the ArcSinh of Sinh[69/128] --rwg Date: 2017-04-03 09:46 From: Mike Speciner <ms(a)alum.mit.edu> To: math-fun <math-fun(a)mailman.xmission.com> Reply-To: math-fun <math-fun(a)mailman.xmission.com> For what it's worth, I looked up how I compute asinh in my javascript library, based on the observations... asinh(x) = sgn(x) ln(|x| + sqrt(x^2+1)) which works best when |x| is "large" asinh(x) = atanh(x/sqrt(1+x^2)) which works best when |x| is "small", using atanh(x) = (ln ((1+x)/(1-x))/2 = (ln(1+x) - ln(1-x))/2 So, trying to get good precision... Math.atanh = function(x) { return .5*(Math.log1p(x)-Math.log1p(-x)); } Math.asinh = function(x) { var s = Math.sqrt(1+x*x); return s<Math.SQRT2 ? Math.atanh(x/s) : Math.sgn(x)*Math.log(Math.abs(x)+s); } On 03-Apr-17 12:32, Henry Baker wrote: > y = asinh(x) = log(x + sqrt(1+x^2)) > > the "obvious" formula. > > We have several choices: > > * Calculate using the obvious log formula > * Calculate using Newton's method on sinh(y) > * More complicated methods > > One more complicated method is to factor the > above expression as: > > y = asinh(x) = f(g(x)), where > f(x) = log(x) and > g(x) = x+sqrt(1+x^2) > > Note that if y=g(x), then x=(y-1/y)/2. > > So we could first invert g(x) using Newton's > method, and then apply the log function. > > The iteration to invert y=g(x) is > > x -> 2*(y+(x-y)/(1+x^2)) > > with an initial guess of 2*y. > > This iteration has quadratic convergence, > and 6 iterations provides fpprec=128 precision. > > It remains to be seen if this is faster and/or > more precise than the obvious formula. > > The other possibility is to get a very good approximation, > and finish it off with a very small (1,2,3 ?) iterations > of Newton to invert y=sinh(x). > > The iteration is x -> x-tanh(x)+y/cosh(x), with > quadratic convergence: > > x0+eps -> x0+eps^2*tanh(x0)/2 > >

1 0