August 2013 - mathfun@mailman.xmission.com

[math-fun] Lego aperiodic monotile (AP Goucher)
by Warren D Smith 23 Aug '13

23 Aug '13

Actually now I think about it, those people with the mystery-metal new state of matter could have just used an "atomic force microscope" on it (can see atoms) and mystery would have been over.

1 0

[math-fun] Lego aperiodic monotile (AP Goucher)
by Warren D Smith 23 Aug '13

23 Aug '13

Brilliantly simple! Lovable! Recently a new phase of matter was discovered. It supposedly appears amorphous to Xray crystallography, but nevertheless exact chemical-composition ratios and "nucleation+growth" behavior are seen. I suppose your sort of lego is one possible explanation of that. (PS. How'd you make the cool graphics?) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 2

Re: [math-fun] Lego aperiodic monotile (AP Goucher)
by Warren D Smith 23 Aug '13

23 Aug '13

Actually, that lego is quite strange. If you just take 2 "layers" of the tiling that IS periodic (viewed 2-dimensionally)! Indeed ANY fixed finite number L of "layers" is something that is periodic viewed 2-dimensionally! Proof sketch: It's because ((3+4i)/5)^L is a plain-integer scaling of a Gaussian integer, if L>=0 is any plain integer. In that respect the "Goucher lego" is different than the Conway-Schmitt tiles (or than almost all of them, anyhow).

1 0

Re: [math-fun] absolute value (branchless)
by Henry Baker 23 Aug '13

23 Aug '13

Ship the number off to your GPU (Graphics Processing Unit), which is incredibly deeply pipelined, and either simply do abs(x) or sqrt(x^2) or isqrt(x^2). The only 'real' (pun intended) problem with abs(x) is the possibility of overflow if x is the most negative 2's complement integer. There still is no good way for deep pipelines to deal with problems like overflow. To a first approximation, most arithmetic calculations are _free_ compared with the cost of fetching & storing results; i.e., fetching a result can cost hundreds of cycles waiting for the answer. Loops in hardware now have _inertia_, in the sense that it may be cheaper to fetch hundreds of items in advance; as a result of this, it may take hundreds of cycles to 'slow down' or 'stop' from a tight loop. I've pondered whether it would be possible to make this analogy with inertia (and mass) more accurate... At 01:25 PM 8/23/2013, Warren D Smith wrote: >suppose my computer wants |x| >but it refuses to perform an "if" statement. > >What to do?

1 0

Re: [math-fun] absolute value (branchless)
by Adam P. Goucher 23 Aug '13

23 Aug '13

> well, let's try that... > x = 1 > y = 0 > x^y = 1 > x^y - y = 0 Take a look at your fourth computation. (Also, ^ is bitwise XOR, not exponentiation, although in this example they return the same result.) Sincerely, Adam P. Goucher http://cp4space.wordpress.com > On 2013-08-23 16:45, J.P. Grossman wrote: > > (typo: that should read 'absx', not 'negx') > > > > > > On Fri, Aug 23, 2013 at 4:44 PM, J.P. Grossman <jpg(a)alum.mit.edu> wrote: > > > >> Assuming x is a 32-bit integer, here's one way that uses 3 instructions: > >> > >> int y = x >> 31; > >> int negx = (x ^ y) - y; > >> > >> J.P. > >> > >> > >> On Fri, Aug 23, 2013 at 4:25 PM, Warren D Smith <warren.wds(a)gmail.com>wrote: > >> > >>> suppose my computer wants |x| > >>> but it refuses to perform an "if" statement. > >>> > >>> What to do? > >>> > >>> _______________________________________________ > >>> math-fun mailing list > >>> math-fun(a)mailman.xmission.com > >>> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >>> > >> > > _______________________________________________ > > math-fun mailing list > > math-fun(a)mailman.xmission.com > > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

Re: [math-fun] Lego aperiodic monotile (AP Goucher)
by Adam P. Goucher 23 Aug '13

23 Aug '13

> Warren Smith wrote: > > Brilliantly simple! Lovable! Thank you! > Recently a new phase of matter was discovered. It supposedly appears amorphous > to Xray crystallography, but nevertheless exact chemical-composition > ratios and "nucleation+growth" behavior are seen. I suppose your sort > of lego is one possible explanation of that. X-ray crystallography would probably detect the `layered' aspect of the tiling from certain angles, but appear amorphous from other angles. Doesn't glass have an exact chemical composition (SiO2, empirically) coupled with an amorphous structure (the crystalline phase being quartz)? Aperiodic tilings are observed in quasicrystals. I seem to recall that certain alloys have local icosahedral symmetry, and generalise the Penrose tiling to three dimensions. > (PS. How'd you make the cool graphics?) Wolfram Mathematica 8. I actually cheated by not including the indentations on the bottom (since they wouldn't be visible from that aspect): Module[{block = {Cuboid[{-5, -5, 0}, {5, 5, 3}], GeometricTransformation[ Table[If[Abs[i] + Abs[j] <= 3, Cylinder[{{2 i, 2 j, 3}, {2 i, 2 j, 3.5}}, 0.6], {}], {i, -3, 3}, {j, -3, 3}], {{4/5, 3/5, 0}, {-3/5, 4/5, 0}, {0, 0, 1}}]}}, Graphics3D[{Red, block, Green, Translate[block, {10, 0, 0}], Purple, Translate[block, {10, 10, 0}], Yellow, GeometricTransformation[{block, Orange, GeometricTransformation[ block, {{{4/5, 3/5, 0}, {-3/5, 4/5, 0}, {0, 0, 1}}, {0, 0, 3}}]}, {{{4/5, 3/5, 0}, {-3/5, 4/5, 0}, {0, 0, 1}}, {10, 0, 3}}]}, Boxed -> False]] I think that Mathematica might be able to export 3D models, although it would be far preferable to rebuild the block in a dedicated CAD package. Sincerely, Adam P. Goucher

1 0

[math-fun] Lego aperiodic monotile
by Adam P. Goucher 23 Aug '13

23 Aug '13

Alex Bellos, Ed Pegg and fellow math-funsters: Inspired by a Lego brick, I've discovered a new weakly-aperiodic three-dimensional monotile. Its proof of aperiodicity is reasonably simple, with the only non-trivial lemma being the unique factorisation of the Gaussian integers. A discussion, complete proof and picture are included here: http://cp4space.wordpress.com/2013/08/23/new-aperiodic-monotile/ Other tiles which admit tilings of a similar type are Schmitt's original tile (1988) and the convex Schmitt-Conway-Danzer tile. Sincerely, Adam P. Goucher

1 0

[math-fun] Entangling with Black Holes: Fuzz or Fire?
by Henry Baker 21 Aug '13

21 Aug '13

The UCSB KITP Conference re "Fuzz" of "Fire" going on right now this week. All of the slides & video is online at: http://online.kitp.ucsb.edu/online/fuzzorfire_m13/ I'm downloading all the video as we speak. You may even be able to watch the sessions live, although I haven't tried it. Stephen Hawking is going to Skype in on Friday morning.

1 0

[math-fun] RSA as (bad) secret key cryptosystem (continued...)
by Warren D Smith 20 Aug '13

20 Aug '13

>> Gareth McC: >> Second, the way I had in mind to search for M depended on fact that if >> message (as integer) exceeds M, then modding by M would lose >> information. So this must be forbidden. Hence by binary search to see >> what is forbidden an attacker with black box access to crypto box >> could determine M. > > If this were (1) a problem and (2) the only problem, it would > be easy to deal with. Just pick some m smaller than M but not > too much smaller, and use that instead of M as the bound. --no, you cannot do that, because then the encryptions would exceed m, so the decryptor box would have to accept messages above m, so the binary search for M could be undertaken with that box.

2 1

[math-fun] RSA as secret key (replies to MIke Stay)
by Warren D Smith 20 Aug '13

20 Aug '13

MIke, first of all it does not appear you read my RSA message, I mentioned M for this purpose (secret key mode) need not be p*q, could be merely a prime. Second, the way I had in mind to search for M depended on fact that if message (as integer) exceeds M, then modding by M would lose information. So this must be forbidden. Hence by binary search to see what is forbidden an attacker with black box access to crypto box could determine M. Third, even if you do not buy that (for example if crypto box permitted users to lose information and just silently screwed them in such an event), then still just by guessing M, whereupon the other stuff (secret exponents) could be determined by subexponential algorithms, that'd still be a way to break it using only half the guessing normally needed for a key that size, i.e. break time not 2^N but rather 2^(N/2)*subexponential(N). ---- Also, re my important remark at the end about how a 4-round Feistel network using discrete exponentials as frobbing functions could be a secret key cipher which I do not see how to break -- one could also do 6-round for a bit more safety, and here note there is no requirement that the message not exceed the modulus M because in this application losing a little information is OK. So any modulus M slightly smaller than 2^(#bits) could be used, for example if we wanted a 256-bit cryptosystem, use M = largest prime below 2^128, which would be M = 340282366920938463463374607431768211297. Mersenne prime M have the slight advantage that modding is especially easy. My Feistelized discrete exponential scheme would be extremely simply described and apparently also reasonable BUT would be slow compared to rival schemes, especially if "slow arithmetic" used in which case it would be asymptotically uncompetitive.

3 2