[Most Recent Entries] [Calendar View] [Friends]
Below are the 20 most recent journal entries recorded in
Mark Gritter's LiveJournal:
| Sunday, May 19th, 2013 | ||||||||||||||||||||||
| 6:41 pm | Classic Math Geek Sunday ...will not become a regular feature, unlike  timprov's classic photos.But I did get a question from a high school student about a calculation I'd done about the game Tonk, five years ago on 2+2: http://forumserver.twoplustwo.com/21/dr I didn't mention the technique in the forum post, but I used a generating function to count the possibilities. If you multiply (1+yxk) together for each value of "k" in the deck (as a multiset, not a set), you get a polynomial whose coefficient on yixj is the number of ways to make a "j"-point hand with "i" cards. Back in 2008 there wasn't a readily available symbolic manipulation tool available on the web, so I hacked some python together to do the math. Today there's Wolfram Alpha, whose limited-duration (free) computation is powerful enough to give: simplify | Coefficient[(1+y x)^4 (1+y x^2)^4 (1+y x^3)^4 (1+y x^4)^4 (1+y x^5)^4 (1+y x^6)^4 (1+y x^7)^4 (1+y x^8)^4 (1+y x^9)^4 (1+y x^10)^16, y, 5] aswhich (fortunately) seem to be the numbers I came up with in October 2008. I wonder how well Wolfram Alpha's freemium model is working for them. :) | |||||||||||||||||||||
| Monday, May 13th, 2013 | ||||||||||||||||||||||
| 9:41 am | Late-night group theory Nearly every undergrad who takes abstract algebra learns the proof that the 15-puzzle cannot be solved if two of the tiles are reversed. That's because the permutations generated by the sliding motions are a subset of the entire permutation group (Sn), called the alternating group (An). The alternating group contains permutations that can be expressed as an even number of transpositions (called, unsurprisingly, "even permutations"), and a single-tile swap is an odd permutation. So what if the motions are instead wraparound "slides"? That is, take an entire row or column and move it as many squares as you want, with tiles wrapping around from left to right or top to bottom. Does that set of moves produce the entire permutation group? Or is it the alternating group, or some other subgroup? For odd-sized grids, the slide moves produce just even permutations. For example, sliding the top row on a 3x3 puzzle like this: 3 1 2 4 5 6 7 8 9 is the cycle (1 2 3) = (1 3)(1 2), which is even. For even-sized grids it seems possible to generate a single-transposition--- say, (1 2)--- since the slides are odd permutations, but how to prove it? Well, one way is brute force. For a 4x4 grid it might be just feasible to find the shortest "word" (combination of generating moves) which generates a particular transposition, although the search space is of size 16! =~ 2*10^13. I thought for a bit and bounded depth-first-search seemed better than BFS or heuristic search, because the queue size could become very large. But the size grows very quickly, even with two pruning heuristics at work. The 8 basic moves on a 4x4 grid are H1, H2, H3, H4, V1, V2, V3, V4, where Hy slides the y'th row right by one, and Vx slides the x'th column down by one. The reverse moves can be generated by cycling around, i.e., H1^-1 = H1.H1.H1. So there are two easy ways to prune the DFS tree. The first is that we should never use the same move more than three times in a row. The second is that all the H's commute with each other (and so do all the V's), so we shouldn't explore both H3.H2.H1 and H1.H2.H3 since they are the same. Depth # of words (w/o pruning commutative pairs) 4 2443 4673 6 95883 298057 8 3761907 10 147594811 12 5790738743 So much for brute force--- we didn't find (1 2) in this search, and going to 14 would take more than overnight. But, that undergraduate algebra class probably talked about commutators as well, moves of the form y^-1.x^-1.y.x. In solving a Rubik's cube these moves tend to swap just a subset of the cubes, making it easier to find a move which fixes a portion of the cube while leaving the rest alone. The same is true here. (Note that composition of group operators is read from right to left.) A useful commutator, X = V2^-1 . H1^-1 . V2 . H1 (first row right, second column down, first row left, second column up) introduces a 3-cycle among 1, 2, and 14: *14 *1 3 4 5 6 7 8 9 10 11 12 13 *2 15 16 So V2.X.X produces the desired swap of 1 and 2, but has messed up the column: [2 1] 3 4 5 *14 7 8 9 *6 11 12 13 *10 15 16 But, another three-cycle can be used to correct this. Let Z = V2^-1 . H3^-1 . V2 . H3, which looks like this: 1 2 3 4 5 *10 7 8 *6 *9 11 12 13 14 15 16 We just need to move the '10' into position, perform the cycle, and then back out again. That means something of the form Y^-1.Z.Y, where Y = V1^-1 . H4^-1. Here's Y alone: 5 2 3 4 9 6 7 8 14 10 11 12 1 15 16 13 which screws up a bunch of stuff, but here's Y^-1.Z.Y: 1 2 3 4 5 *10 7 8 9 *14 11 12 13 *6 15 16 which is a nice well-behaved three-cycle, exactly the one we want to patch up V2.X.X. Putting it all together, Y^-1.Z.Y.V2.X.X = 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 or in word form: H4.V1.V2.V2.V2.H3.H3.H3.V2.H3.V1.V1.V1.H But, this is sufficient to show that the slide moves generate the whole symmetric group S_16, since we can generate any other desired transposition in the same way, and the transpositions are generators for S_16. How could we encode the directed search I performed by hand, into a computer algorithm for finding efficient (but not necessarily minimal) sets of moves for a given permutation? | |||||||||||||||||||||
| Saturday, May 11th, 2013 | ||||||||||||||||||||||
| 12:49 pm | Why is 50% the limit? In today's Star Tribune, an orchestra board member makes the case that musician salaries must be cut: Deficits will continue to grow unless we are able to address cost savings in our musicians’ contract, since their direct compensation makes up nearly 50 percent of the orchestra’s total expenses. Nearly 50 percent! Good heavens! I'll be generous and blame the Star Trib itself for the sub-head "The musicians are half the cost, and that can’t continue." But even so, why shouldn't musicians--- you know, the ones that actually form the orchestra--- be more than 50% of the budget? This is an awful way to try to make your case. (The board's web site trying to compare orchestra salaries to PhD-holders is almost as bad.) It would be better to state--- as the web site does--- that 80% of the budget is "musicians and concert-related costs." Even so, it would be refreshing to see an honest breakdown of what it really costs to have an orchestra--- not why the current cost structure of the orchestra doesn't work. | |||||||||||||||||||||
| Tuesday, May 7th, 2013 | ||||||||||||||||||||||
| 7:55 pm | Towards a Taxonomy of Match-3 Games Field: square lattice, hexagonal lattice, freeform, 1-d Moves: slide (15-puzzle style), rotate around lattice "great circle", rotate around interior point, swap, drop (singles or groups, with restricted placement at edges), place (arbitrary free location) Matching result: promote/build (objects are combined to a next-tier object), clear Minimum match size: 3, 4, 5+
I am sure I have seen a "clear"ing game with the slide-to-empty-space mechanic, but I cannot come up with it. "Alchemy" is something of a cheat. I am less sure that the "promote" row can be filled in. So many games use the swap mechanic that I feel like there must be a "build+swap" game but I can't think of one. One obvious variation is to perform rotations around the center on a square grid. I.e., the center rotation would move 4 squares, the one outside that would move 12 squares, the next ring has 22 squares. | |||||||||||||||||||||
| 1:28 am | "30 Greatest Orchestral Works"? The modern orchestra's not all that old. If you want to list greatest paintings you can go at least back to the 1500's. Greatest literature? Much further. So I saw a "Great Courses" ad for their "30 Greatest Orchestral Works" and was a bit discomfited to realize that there was nothing more recent than 1953 on the list. It starts in the 1720's with Vivaldi and Bach, but ends in the 1953 with Shostakovich's Symphony No. 10. (And a sad lack of Sibelius...) So, 230 years of orchestral works == about one "greatest" every eight years. Is it plausible that we have gone 60 years without any great orchestral music? Possible, certainly. A nearly equal span of time passed between the Bach and Mozart pieces Dr Greenberg chose. And the rise of all the strains of popular music has certainly diverted some energy and talent from the orchestral tradition. But no movie composers? No postwar modernists? None of the Jazz musicians who have tried their hand? I would think it shocking for any great literature survey to cut off the last 60 years of work by ending with "Invisible Man" or "The Old Man and the Sea." I can't decide whether this is a deliberate critical choice, a preference for honoring dead composers over live ones, or just a failure to engage. | |||||||||||||||||||||
| Sunday, May 5th, 2013 | ||||||||||||||||||||||
| 10:32 am | Building robots.txt Google searches for "Netflix X" where X is a movie title usually find the Netflix page for that movie, even though their robots.txt prevent it being searched. (Not too surprising--- if there are enough links, Google can find it even if it can't scan the page itself.) So out of curiousity I took a look at robots.txt and not only is it commented but it also has a disabled portion listed: The implication is that the deployment process for the website just does a "copy", not a "build." This is pretty common for websites--- you can find lots of comments and comment-disabled portions in HTML and Javascript documents. http://www.tintri.com/robots.txt has a ton of boilerplate text that obviously came with the web server or framework. There are exceptions: http://cnn.com/robots.txt doesn't have any comments. http://facebook.com/robots.txt has comments that are directed at outside people (like they should be)! But what surprises me most is that I couldn't quickly find tools or best-practices guide for stripping out "internally"-directed comments, other than the JavaScript compaction + obfuscation tools whose main goal is reducing size. | |||||||||||||||||||||
| Friday, May 3rd, 2013 | ||||||||||||||||||||||
| 9:59 pm | Finding all the Pythagorean triples My interest was sparked by this Quora question: How would you find all the Pythagorean triplets in an array of N numbers? The first answer was the straightforward O(N^2) examination of all pairs of numbers. It seemed like there might be a better way. One of the comments initially suggested O(N^2) was probably the best possible, because of its similarity to 3SUM, but I knew that Pythagorean triples were sparse (and had structure) so there might be a way to beat the "generic" algorithm. In fact primitive Pythagorean triples have a quite lovely structure: they can be generated in a ternary tree using a set of three matrices. (In two different ways, no less! The second set of matrices was only discovered in 2008.) There are several implementations of this idea on Rosetta Code (often contrasted with the naive approach.) Primitive triples are those whose three elements have no common divisor. We can use this structure to do better than O(N^2), under certain conditions. Pick the largest element of N, call it L. Using depth-first search on the ternary tree, generate all primitive Pythagorean triples with hypotenuse length <= L. Note that this method of generation always produces larger hypotenuses in the children of each node, so we can effectively prune our search. There is a result from the turn of the century which says that the number of primitive Pythagorean triples <= L is, in the limit, a constant fraction of L (in fact 1/2*pi). So, the depth first search takes time O(L), because we generate a unique triple each step, and prune no more than 3x the number of valid triples. How long does it take us to generate all triples from just the primitive ones? Well for (3,4,5) we create an additional L/5 triples. For (5,12,13) we create an additional L/13 triples. I claim that this is bounded by L*H(L), where H(k) = the k'th element in the harmonic series (i.e., 1 + 1/2 + 1/3 + 1/4 + ... + 1/k.) A little handwaving is required here because some hypotenuses appear in more than one Pythagorean triple. I was not able to find a reference online confirming my guess about this bound on the number of Pythagorean triples. (Mathworld cites only the limit result for the number of primitive triples.) However, using OEIS's list of the number of triangles I can verify that L*H(L) =~ L*log(L) is a good bound up to 10^12. This process produces all the Pythagorean triples with no repeated elements. So, for our algorithm we put all elements on N into a hash table. (Note that randomized algorithms can produce a perfect hash in O(N) time, if we're worried about that aspect.) Then iterate through all Pythagorean triples with hypotenuse <= L, and check whether all three elements are in the hash table, which is a constant-time operation. Thus the total run time is O(L log L). If N is O(L) then this algorithm is much better than O(N^2). That is, as long as the number of elements in the set is proportional to the largest number--- or even somewhat worse--- we win. The naive algorithm is better if there are only a few, large numbers. I coded up both in Python (they are just a few lines each) and ran a handful of experiments (times are in seconds:) L N quadratic tree 1000000 1000 0.21 2.18 1000000 2000 0.83 2.22 1000000 4000 3.37 2.20 2000000 4000 3.39 4.82 2000000 6000 7.73 4.95 A possibly interesting follow-up question is which algorithm parallelizes better. Both algorithms have pretty trivial partitionings (tree sub-branches vs. subsets of the pairings.) With an unbounded number of processors the "quadratic" algorithm can be made constant-time, but the tree algorithm is not. Code on pastebin (because I'm not one of the cool kids on github.) | |||||||||||||||||||||
| Tuesday, April 16th, 2013 | ||||||||||||||||||||||
| 11:48 pm | Python programming problem Suppose you have a set A and you want all possible ordered triples of elements in A. In Python you can just do for x in itertools.product( A, repeat = 3 )Now, what if A has a special element X and you want only the ordered triples that include at least one X. What's the best way of doing so? (Assuming we want to pick only among the implementations which don't generate all triples and then filter.) I was thinking of but this seems a bit indirect (of course, I'm allowing for the general case here.) The idea is to iterate over (X, any, any), then (not X, X, any) then (not X, not X, X) which should cover all possibilities exactly once. Other alternatives? | |||||||||||||||||||||
| Monday, April 15th, 2013 | ||||||||||||||||||||||
| 11:50 pm | limited NOTs One branch of theoretical computer science looks at "circuit complexity", studying the size and depth of boolean logic circuits necessary to produce a particular function. A puzzle in this area is whether we can invert three binary digits using just two inverters (but as many AND and OR gates as we want.) The answer (in the affirmative) actually shows that all 88 3-bit to 3-bit functions can be represented using at most two inverters. Given A, B, C, and not-A, not-B, not-C, we can construct any arbitrary 1-bit function as an OR of ANDs, enumerating the cases where the output should be 1. Do this three times in parallel and you have all the 3-to-3 functions. So, of those 16 million functions, how many can be represented with 0 or 1 NOT gates? This seems like it should be feasible to explore via brute search. The 4-bit case, with 2*1019 possible functions, would require some cleverness. (That is probably why many results focus on one-bit outputs such as decision problems. :) Circuits with no inverters are referred to as "monotone"--- one circuit complexity result is that the "k-clique" problem (detection of a clique of size k in a graph) can be solved with a monotone circuit, but requires a superpolynomial number of gates. | |||||||||||||||||||||
| 1:42 pm | Using CRT to calculate Bernoulli Numbers I happened across "A multimodular algorithm for computing Bernoulli numbers" which implements a cute hack. The Bernoulli number B(k) mod p can be efficiently calculated for prime p > 5. You can calculate a bunch of B(k) mod p_i in parallel, then use the Chinese Remainder Theorem to stitch those results back into the desired number. This algorithm's now part of the Sage toolkit. Calculating B(20000000) took 79 days in 2012, using this implementation. I wonder what other functions could be decomposed this way? Once you start paying attention to bits (and not just words), operating "mod p" can save you a lot of time spent multiplying, both theoretically and practically. | |||||||||||||||||||||
| Monday, April 8th, 2013 | ||||||||||||||||||||||
| 8:33 am | Tintri website re-launch, Tintri OS 2.0 Tintri went live with its new website this morning, and announced version 2.0 of the Tintri OS, which includes support for per-VM replication. The team has been working very hard for the past months on getting this functionality built and tested, and early feedback from our alpha and beta customers has been good. I'm very proud of what Tintri has accomplished so far, and I think per-VM replication helps cement our leadership in storage for virtual machines. Launch coverage so far on Yellow Bricks and The Register. Tintri is hiring for a large variety of roles, check out the Careers page or drop me a line if you're interested. | |||||||||||||||||||||
| Saturday, April 6th, 2013 | ||||||||||||||||||||||
| 10:48 pm | MinneBar 8 MinneBar 8 has come and gone. I had a good time, as usual, and touched base with a lot of friends who were attending. "All the Monitoring" by Bryan Brandau from Best Buy: good overview of monitoring tools (other than Nagios). Showed Sensu, Graphite, Logstash. What the heck is up with all the different open-source dashboard projects, though? He mentioned at least five by name. "Agile Financial Modelling" by the Investyr guys. A little weak, their main point was not to spend a bunch of time on useless stuff--- put a quick spreadsheet together spending 80% of your time on year 1, 15% on year 2, don't bother beyond year 3. I wish they had done more with showing what sort of scenarios you could play with once you had a spreadsheet in place, instead they actually built it on the fly. "Do 'Data Science'" by a bunch of folks from NativeX. I walked out of this one--- should have gone to learn about Julia or attend the lightning talks instead, but both rooms were packed. The presentation was dull and process-oriented to start, and included an explanation of Bayes' Theorem that was tedious to those who already knew it and probably confusing to those who didn't. Really would have been a ton better if they'd started with "here's what we did for the company, want to learn how we did it" rather than some bogus "we follow the scientific method unlike you Technical Support for Developers panel by Chris Warren, Luke Francl, and Kevin Whinnery. This was a lot of fun. The support they provide is mainly API support rather than purely end-user but they had good stories comparing different approaches (dedicated team vs. development team) and the value of direct customer feedback. Shopping for Nerds by Neal Tovsen. This was a brief talk on how to weigh the risks of different technical "talent": outsourcing, freelancers, co-founder, etc. I think Neal accurately described the trade-offs, and his point that you need to make sure somebody is "looking out for you" is well taken. But the session could have been stronger with more examples to help illustrate what has worked and what hasn't--- we mainly got some (usually anonymized) horror stories. I asked whether anybody in the room had actually been successful at throwing out their outsourced/cobbled-together MVP and building the "real" product afterwards. Nate Yourchuck said he's done a couple of consulting projects where he built a real product to replace emailed-around Excel spreadsheets. I remain dubious that you can really "build one to throw away" (pace Fred Brooks.) I got to hear Neal give his pitch for "Apruve" several times today and yesterday, and I think there is quite a bit of potential there. Journey to the Bottom of the Storage Stack by me. I thought it went pretty well, but I suspect I spoke too quickly. Also I kept wandering too close to another live microphone and causing feedback. My friend Scott brought a friend from Isilon along to keep me honest. That gentleman suggested an alternate proposal for an anomaly I'd found, of hot data blocks pointed to be cold metadata--- that frequently-written metadata blocks might never be flushed from the journal. I'm dubious, I don't know if ext4 actually implements that optimization. Slides will go up on the Minnestar wiki within the next few days, hopefully. Scaling with Cassandra by Jeff Bollinger + another NativeX (nee W3i) guy. Talked about why they chose to move from SQL Server to Cassandra, and about Cassandra's data and consistency model. The numbers they gave for their production system: 12 nodes (each running 12 cores @ 2GHz) with 2x480GB commodity Intel flash drives. Per node they see about 240 writes/sec peak, and 888 reads/sec. (These numbers seemed low, I think they are observations rather than benchmarks.) They see about 3ms writes, 4ms reads (end-to-end) which is not too bad considering the extra network hop, but not blazing fast--- their SQL server achieves 1.5ms read latency, but most of the data is in memory after moving bulk data to Cassandra. Their solution is hybrid now, they kept SQL for the data that really was relational, and talked about the importance of understanding the data movement characteristics while doing the design. Jeff also mentioned that it took them a few times to get the hardware right, so they wished in retrospect they'd done more prototyping and experimentation using cloud resources instead of in-house boxes. I always feel like I should stick around longer during the happy hour, but as usual I had had about all the monkeys I could take, and even on the edges of the large cafeteria area the conversational noise is quite high. | |||||||||||||||||||||
| Saturday, March 30th, 2013 | ||||||||||||||||||||||
| 9:19 pm | Knuth on Combinatorial Algorithms From "Combinatorial Analysis and Computers", February 1965: When the size of a combinatorial problem grows very rapidly, we can usually expect the computer to do only about one case larger than can be done by hand. I am curious whether there are readily-available examples where this is still true. | |||||||||||||||||||||
| Saturday, March 23rd, 2013 | ||||||||||||||||||||||
| 3:37 pm | Guardian and Google and Statistics The Guardian has a piece about how Google's failed products get killed, on average, after 1459 days. But it's completely wrong to use this as a prediction of likely product lifetime, because it discounts all the products still in use. Suppose there are three siblings age 31, 33, and 35. If the younger two of them die in an accident, would you then proclaim that the average age of death for the family is 32? Of course not, it can't be any less than 33--- and probably much larger. Or suppose that you take a sample of the Winter 2012 Y Combinator class and observe that two of them closed shop as of 2013. Would you average those two samples and conclude that the average Y Combinator startup fails in less than one year? While the Guardian article makes it clear they are talking only about failed products, if you want an expected product lifetime you have to include the "successful" ones too. | |||||||||||||||||||||
| Wednesday, March 20th, 2013 | ||||||||||||||||||||||
| 12:24 am | First-Sale Doctrine applies to imports too The Supreme Court had an interesting 6-3 split (Ginsburg, Kennedy, and Scalia dissenting) on its decision that the First Sale doctrine applied to books published outside the U.S. and brought back in. Copyright law cannot be used to prohibit import and resale of cheap textbooks from foreign countries. (As the dissenters pointed out, such a ruling neuters the "import" monopoly granted in law.) But media coverage has, as usual, been pretty shallow about explaining why publishers don't want to allow this practice. This Ars Technica piece, for example: But while price discrimination is certainly lauded by the companies that rely on it, it's not at all clear that having courts perpetuate such pricing schemes benefits anyone beyond shareholders of those companies. Ignore the economic-theory arguments about goods that need price discrimination to get produced at all, isn't it obvious that the students who get lower-priced books benefit?! Were I ruling I'd probably side with the majority here... but I do now work in an industry dominated by price-discrimination through the use of high list prices (compared to street prices). It is also worth taking some care to preserve the right of authors to sell foreign publishing right separately, rather than providing a loophole where North American rights are converted to global English rights by the expedient of "selling" books to a subsidiary. | |||||||||||||||||||||
| Sunday, March 10th, 2013 | ||||||||||||||||||||||
| 10:43 pm | Python coroutines I learned today that python generators can be run in reverse to create coroutines. The basic idiom is: def myCoroutine():
while True:
x = (yield)
doSomethingTo( x )Then you can use it by calling .send() to provide the return value of the yield expression. See a short course here: http://dabeaz.com/coroutines/This sort of structure is very useful when you want to create a pipeline of operations, some of which (but not all) can be batched. (A sufficiently smart compiler could even put the operations in different threads.) It's possible to build quite complex flows in this way, with each coroutine having multiple sources and sinks. | |||||||||||||||||||||
| Friday, March 8th, 2013 | ||||||||||||||||||||||
| 9:58 pm | SimCity launch A lot of people are framing the SimCity launch problems as a DRM issue, and there's some fairness to that. But SimCity's design is "online always" (even your cities are saved to the cloud) so I think it is more apt to compare the game to the launch of a new MMO. One that went horribly, horribly wrong. (Whether or not you want an MMO SimCity is a different issue.) The leaks that have come out so far are not particularly technical in nature. But it seems to me that EA made at least three errors: * No QA at scale. This is excusable since it's very hard to simulate 100,000 real users. But many MMOs have an open beta period to get some feel for how well they scale and whether there's a problem looming. EA did some beta testing, but either did not take the right sort of measurements, or ignored the warning signs. (Internet-scale services are especially difficult to QA because the heterogeneity of client behavior easily dwarfs anything you can capture in a test plan.) * Insufficient operational planning. Any time you have to "roll out three additional servers" as part of your response, it's a sign you got cheap on the back-end. There was a fundamental disconnect between expected user base, and the capabilities of the service. These systems should have been overprovisioned to start, but potentially cut back post-launch if the service was working well. * Non-scalable architecture. Most serious SaaS companies can spin up additional servers in the cloud, and have architectures that permit this. (But not all.) The ability to use public-cloud resources is a powerful scaling tool. The fact that EA was cutting game features in order to handle the load suggests that their system was not able to partition load effectively across a pool of resources. (Or, they were unwilling to pay for additional resources for the pool.) From a distributed systems perspective, the failure is perfectly understandable--- but amateurish. Few startups could successfully go from 0 users to tens of thousands on the first day, and all experience growing pains across all three of the above axes. EA has little excuse, though. It feels like they thought they were just building a DRM infrastructure, when really their design required a much more aggressive operational capabilities. | |||||||||||||||||||||
| Thursday, March 7th, 2013 | ||||||||||||||||||||||
| 11:36 pm | Comics, Hits and Misses Comics I've loved recently: Power Nap: It's about a world full of sleepless, and the monsters in dreams. Irregularly updated, but I'm hooked to see what they'll do next. Nimona: It's about villany! And an impertinent shapeshifting sidekick. It won the Cartoonist Studio Prize (for webcomics) this year. Strong Female Protagonist: A young superhero tries to give up hero-ing and go to college. I also liked Fables: Cubs in Toyland a bit better than the previous few collections. I've started reading Guilded Age, which usually presents as a humorous high-fantasy comic, but has some occasional interesting depth. (It is almost disqualified for worst page navigation layout possible, however.) I'm also giving Scott Kurtz' new project, Table Titans, a try, although I'm not entirely sure why. Comics I did not love recently: The Manhattan Projects: The nuclear bomb was just a cover for the real secret research! Features Robert Oppenheimer's Evil Cannibalistic Twin, Albert Einstein's Alternate-dimension Evil Doppelganger, and Richard Feynman, who evidently gets to be his own evil opposite. The satire, if it is meant to be such, is fairly heavy-handed and we quickly exit World War 2 for some nonsense with aliens. I wanted this to be better. Instead it reads like somebody who thought Warren Ellis was great, just too subtle and understated. Re-read Planetary instead. Saga: What. I don't get why people love this so much. Lots of bodily fluid jokes embedded in a fantasy/science-fiction hybrid setting. Oh, and there's a pointless ramble through a planet-sized bordello. Kaboom: Early Jeph Loeb, and boy does it show. Hyperactive and not particularly engaging. It's about some magic gloves, and seems very manga-inspired. There are two potential girlfriends and N daemons, all that's missing is some sort of tournament. | |||||||||||||||||||||
| Sunday, February 17th, 2013 | ||||||||||||||||||||||
| 3:22 pm | One for the Daily WTF While trying to restore a VMware Workstation VM that I had paused:  Error messages are hard. (No, really, they are!) | |||||||||||||||||||||
| Friday, February 15th, 2013 | ||||||||||||||||||||||
| 10:14 pm | LLVM's integer types When I read the LLVM assembly language definition a while back, I thought "cool, it's got support for integer types with any specified number of bits." (Well, up to about 8 million bits but that's plenty.) With the three-day weekend I thought I would relax by getting more familiar with LLVM, and maybe build a toy language idea I had kicking around, which would perform type inference on integer lengths. (i32 * i32 != i32, dammit!) Unfortunately, while LLVM version 3.2 seems to generate valid code to add large integers, it does not seem to multiply them correctly. (And, for sufficiently large integers, the x86 assembler asserts.) Here's a function that adds two 132-bit unsigned integers: define i133 @add132( i132 %a, i132 %b ) nounwind uwtable {
%wideA = zext i132 %a to i133
%wideB = zext i132 %b to i133
%result = add i133 %wideA, %wideB
ret i133 %result
}LLVM assembles to code which truncates the arguments to 132 bits and then adds them correctly: add132:
andq $15, %rdx
andq $15, %r9
addq %rcx, %rdi
adcq %r8, %rsi
adcq %rdx, %r9
andq $31, %r9
movq %rdi, %rax
movq %rsi, %rdx
movq %r9, %rcx
retHowever, multiplying two 35-bit numbers: define i70 @mul35( i35 %a, i35 %b ) nounwind uwtable {
%wideA = zext i35 %a to i70
%wideB = zext i35 %b to i70
%result = mul i70 %wideA, %wideB
ret i70 %result
}ends up using a bare mulq instruction, which is only 64-bit:mul35:
movabsq $34359738367, %rax # imm = 0x7FFFFFFFF
andq %rax, %rsi
andq %rax, %rdi
movq %rsi, %rax
mulq %rdi
ret
but, log2( (2^35-1)(2^35-1) ) is just a shade south of 70 so this code will result in wraparound. | |||||||||||||||||||||