dtm: (Default)
We visited family in northern Wisconsin over New Year's, and one of the things that happened there is that we were introduced to the show "The Big Bang Theory", and I watched the whole first season on DVD.

So we've been working our way through the second season's DVDs here the past few weeks. As you may know if you've seen the show, in one episode this season they introduce the game of "Rock, Paper, Scissors, Lizard, Spock" (a game originally described here as "Rock Paper Scissors Spock Lizard"), an extension of "Rock, Paper, Scissors". (I'm going to call this game "RPSSL" in this post)

This got me thinking more generally about extensions to "Rock, Paper, Scissors", (hereafter, RPS) so let me define:
A degree-n RPS extension, where n is an odd number >= 3, is a two-player game in which players secretly select one of n symbols and then simultaneously reveal their choices; assuming the player selected differently from each other, the winner of the game is determined by the game's ruleset. The ruleset of an RPS extension must specify that every token wins against (n-1)/2 of the other tokens, and loses against the other (n-1)/2 tokens.

So RPSSL is a degree-5 RPS extension, because for any choice player A makes, exactly two choices for player B will let A win (and exactly two will let B win).

Two RPS extensions are equivalent if you can obtain one from the other merely by renaming tokens.

So here's what I've come up with:

  • There's at least one degree-n RPS extension for every odd n >= 3.
  • Up to equivalency, there's only one degree-5 RPS extension.
  • Up to equivalency, there are at most two degree-7 RPS extensions.

I need to work more with the two different degree-7 extensions I have to prove that they definitely aren't equivalent. Getting some paper and writing it down would probably help, rather than trying to just keep it in my head.

For the other two points, I'll just note that if you re-arrange the tokens in RPSSL into the order:
Rock, Spock, Paper, Lizard, Scissors

And imagine those tokens in a circle, then every token loses to the two tokens that immediately follow it and beats the two that immediately precede it. This shows a general pattern that can work for any n and working out that with five tokens, there must be such an order proves the second point.
dtm: (Default)
I've been meaning to post this for a while, several months in fact, but I haven't. However, just this morning I discovered Scalzi's Law, and it seemed like a sign.

This is a reconstruction of a conversation I had at Google. It was had in 5-minute chunks over breakfast, over the course of several weeks, and has mostly died down now. I'll try to reconstruct it, but may miss some important bits since I wasn't writing it down at the time. In particular, I may well attribute important bits of the conversation to the wrong person. As background, Google provides us with breakfast if we're there early enough, but only two of us in my group ever are:

me: (looking at D's plate) You're going to regret that.
D: What? ... Oh (unpleasant face)
me: Yeah. The turkey bacon just isn't bacon.
D: The turkey sausage is fine, though.
me: Oh yeah, that's fine. Turkey's a fine meat, and they do make great sausage out of it; it just doesn't make good bacon.
D: (holding up the plate) It's not turkey bacon today.
me: Yeah, this is good.
D: Another day of the adjective-free bacon.
me: yeah, but I can't believe you tried that vegan sausage.
D: Oh, it looked so incredibly wrong I just couldn't pass it up. (tries) Oh bleah! The turkey bacon is disappointing, but that's just wrong. I guess I deserved that.
It gets weirder )
dtm: (Default)
Okay, haven't posted in two whole months, I haven't told you what it's like working at Google since the first day, etc. I will say that my lack of blogging here has absolutely nothing to do with my internal-to-Google blog, since I haven't actually signed up for that either.

And this post isn't going to interest most of you who have me on your friends list, but if I waited for that, it'll be another two months or more before I post anything again. So here's a post on something I was thinking about this morning.

I was reading through some of Steve Yegge's old blog ("who is he?", you ask? He's just this guy that used to work at Amazon, now works for Google, and had an Amazon-internal blog that he made mostly public after leaving Amazon. Some of it's interesting) about interviewing programmers and he gave this as an example of the naive solution to the problem "find the nth Fibbonacci number":

static long fib(int n) {
  return n <= 1 ? n : fib(n-1) + fib(n-2);

One of the comments noted that they'd expect any candidate to be able to tell that that implementation as it stands is O(2n).

That didn't feel right to me - I mean, clearly it is O(2n) in the sense that big O provides an upper bound, but it's not a tight bound - that is, it isn't ϴ(2n). So what is a tight bound?

It turns out that this algorithm is actually ϴ(fib(n)), which is to say that it's ϴ(φn), where φ is the golden ratio (1 + √5)/2.

Why is this? Well, I think I'll leave that as an exercise for the reader, or maybe I'll add it later to this post underneath a cut tag. Suffice it to say that there's a nice recurrence relation that defines the number of invocations of fib necessary to calculate the nth Fibbonacci number, and that it requires a bit of fiddling after that, but not too much.

Anyway, that's something I was thinking about this morning.
dtm: (Default)
First though, some more Katherine babble. This morning she really, really wanted for breakfast a "simpon squirrel beggle". In normal speech, this would be a "cinnamon swirl bagel".

Now, a game theory theorem that I've had stuck in my head for over ten years. Hopefully writing it down will exorcise it. Namely: In any two-player tic-tac-toe-like game, there can be no winning strategy for the second player.

Proof (and rigorous definition of "tic-tac-toe-like") behind the cut.
Read more... )
dtm: (Default)
So in the effort to get me posting about anything, and prevent my journal from idling for another month, I'm going to talk about a toy I bought myself on eBay a few weeks ago.

It's a slide rule.

It's a moderately nice one, though the sight on it is slightly askew, such that if I don't touch it, the line isn't quite vertical. It's only a 10 inch model; the really accurate 20-inch and longer ones aren't selling on eBay, or are too pricey.

It has scales L, C, D, A, B, K, Ci, CF, DF, CiF, S, T, ST, LL1, LL2, LL3, LLO, and LLOO.

Just think - there was a time when every engineering student would know what all of those scales meant. I've included a discussion of what those scales mean, and what it means I can compute with this, below the cut.
The rest gets rather math-heavy )
dtm: (Default)
I wrote this in Notepad on the train, but hadn't had a chance to post it until now - it's been a bit of a hectic day:

So last night, for reasons that may be apparent if you read [livejournal.com profile] jmartin2's journal, I had several hours during which I could just wander around Marlton, and perhaps not too surprisingly I found myself walking around the big Barnes and Noble that's at the corner of Rts. 70 and 73.

And, as often happens, wandering around that big bookstore made me sad. I've been trying to express why, but big bookstores like a Borders or a Barnes and Noble have that effect on me. The same thing does not happen in little stores like the several used-and-antique bookstores we sometimes visit in Bordentown, even on those occasions when I don't find anything to buy.
Looking at math books )
Then, having thoroughly depressed myself in the mathematics section, I wander a few shelves over to the computers section.
"Computers" )
dtm: (Default)
A math problem vaguely inspired by life:

Say you have to walk from point A to point B. Now, the catch is that you have to take each step so as to not wake the baby sleeping at point A. If you wake her, you have to go back to point A and spend the time during which you could take n steps comforting her until she goes back to sleep. The probability of the baby waking during any step is equal to the portion of the distance covered during that step - in other words, if you try to go from A to B in one step, she'll certainly awaken (longer steps are louder, you see). If you try to take it in two equal-sized steps, you have a 1/4 chance of making it across.

Now, you're trying to get to point B as quickly as possible. (Assume that each step takes the same amount of time). What's your optimal strategy? What is the expected number of steps taken?

First take this problem with n = 0; that is, the only penalty for waking the baby is that you have to start over from point A.

What if we change things so that the probability of her waking is equal to k times the portion of the distance covered? (So that for k=2, she is certain to wake if we try to cover half the distance in a single step)
dtm: (Default)
Yeah, yeah, it's been a long time since updating and all that. (Ever read those old Peanuts cartoons in which they write to their pen pal? Almost every letter begins with a variant of "sorry I haven't written in so long...")

Anyway, Jennifer is still pregnant, and getting more very pregnant every minute. (she's due January 20th)

So enough about life; I'm going to talk about math.
Something your middle- or high-school algebra teacher should have told you, and probably didn't )
dtm: (Default)
So the gospel lesson this week was Mark 6:30-44 which says in part:
38 And he said to them, How many loaves have you? Go and see. And when they knew, they say, Five, and two fishes. 39 And he commanded them to make them all sit down, arranging the guests on the green grass. 40 And they sat down, arranged in hundreds, and fifties. 41 And when he had taken the five loaves and the two fishes, raising his eyes to heaven, he blessed, and brake the loaves, and gave to the disciples to set before them, and divided the two fishes among them all. 42 And they all ate, and were satisfied. 43 And they carried away twelve baskets full of the fragments and of the fishes. 44 Now they who had eaten were about five thousand men.

So there you have it - Biblical justification for the axiom of choice. I don't know why the connection hadn't occurred to me before.
dtm: (Default)
So let's suppose you have a Java double (or float) and you want to come up with a string that represents the double/float in decimal but, and here's the kicker, you want the shortest string that'll adequately represent the number. For example, if you have the float corresponding to 0.85, when printing it out you might get:
Not what you want (to get that in java you have to cast the float to a double, but you can get slightly less ugly artifacts simply by producing the float out of a long calculation - accumulated roundoff and whatnot).

What if you want to say "give me the shortest decimal assuming that this double's mantissa is only accurate to 20 bits"? (a java double has 23 bits in the mantissa)

Now suppose you want to do this in a tight loop where speed is critical. (otherwise, it wouldn't be much fun, would it?)

I've got vague references to stopping conditions using only integer arithmetic in this paper from 1992, but it's hard to clear though what the other stuff they say to get to what I want. Also, most of the paper assumes that the reader is fully aware of the contents of a presentation made at some ACM SIG* conference in 1990. Not too helpful, so I may just end up working it out on my own.

May 2017

212223242526 27


RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 19th, 2017 06:55 pm
Powered by Dreamwidth Studios