「うさぎドロップ」/「 LC斐爾 」

One of the few famous quotes in Canadian politics is one by Brian Mulroney, leader of the Progressive Conservative Party of Canada and the 18th Prime Minister of Canada, during the 1984 campaign. As the leader of the Liberal Party of Canada that took over after Pierre Trudeau resigned, John Turner inherited Trudeau’s premiership (yes, we can swap prime ministers without elections) and government in the latter part of his term. Just before resigning, Trudeau had appointed a ton of loyalists to various positions.

Technically, it is the Governor General of Canada (who acts as the representative the Crown) who makes these appointments, but he or she only does so on the advice of the prime minister. In this case, the appointments had only been recommended by Trudeau but weren’t finalized by the governor general when Turner became prime minister, so he could have stopped them. During the 1984 leaders’ debate, Mulroney attacked Turner for allowing these appointments and Turner replied that he had no option. This was the lead-in to Mulroney’s famous line:

You had an option, sir. You could have said, ‘I am not going to do it. This is wrong for Canada, and I am not going to ask Canadians to pay the price.’ You had an option, sir — to say ‘no’ — and you chose to say ‘yes’ to the old attitudes and the old stories of the Liberal Party. That sir, if I may say respectfully, that is not good enough for Canadians.

This left Turner shattered in the debate and pretty much won the election for Mulroney. Unfortunately, ever since then, media coverage of electoral debates has always focused on finding that snappy equivalent knockout line, but no one has produced one since.

I like Usagi Drop. Yes, I have read the entire thing. No, the ending was not what I would have liked, but I’m not particularly angry about it. I mean, 95% of it was great, which is a far better ratio than most stuff out there. What’s more is that I think the initial reaction absent the surrounding context made it seem much worse than it actually was, especially with the important reveal that Rin isn’t actually Grandpa’s biological kid.

In fact, I’d say that I don’t really have a problem with most of the ending “arc” and it’s only the very last chapter that makes me raise an eyebrow. I can buy that Rin could have developed romantic feelings for Daikichi. After all, I think it’s an important note that she sees him as a guardian and not her father. He’s always simply been Daikichi to her.

The problem, then, and the part I find hard to believe is Daikichi’s response, which pretty much amounts to a ‘welp, guess I have no choice’. It’s really strange because, even though he was clearly uncomfortable the idea, he didn’t put up that much resistance. It’s strange enough that he offers to wait two years and hopes the problem might go away. After the two year wait period, Rin kind of goes ‘hey, it’s been two years’ and he’s sort of resigned to the whole thing.

What I’m struck by with Usagi Drop’s ending is that Daikichi had an option: he could have said no, but he chose to say yes. It would have been perfectly fine for him to say no. Rin couldn’t have seriously been expecting Daikichi to reciprocate. She would’ve been fine if things continued the way they were. She was prepared to have things stay the same. Things might’ve been awkward for a while, but a ‘no’ would have closed the matter. Instead, we’re left with, well, whatever it is that we have now.

I’d like to stress again that I still think the manga is excellent, even the second half of it. However, Daikichi’s response is baffling and his rationale is unconvincing. Quite frankly, it’s not good enough, especially for such an otherwise great manga. I’ll defend it, but I’ll concede that the end is not at all what I wanted.

「Steins;Gate」/「いさりび」

In Steins;Gate 12, the Future Gadget Lab is faced with a problem. They need to send a copy of a person’s memory, or about 3.24 TB, to the past, but they can only send 36 bytes. What is a MADDO SCIENTISTO to do? What they end up doing is sending that data to the Large Hadron Collider to compress with a black hole. Problem solved! Or is it?

Obviously, using a black hole to compress data is silly, since a black hole would probably just destroy the data. In fact, it’s probably unnecessary, since if it were physically possible to achieve that kind of compression, you’d be able to do it on any computer because of the Church-Turing thesis. The only thing that would change is how quickly the algorithm would run. Luckily, in theoretical computer science, when dealing with the question of whether something is possible or not, we don’t care how long it’ll take. So, is there a compression algorithm that can give us the desired result?

Basically what we’re doing when were compressing stuff is we’re trying to rewrite a bunch if zeroes and ones, or strings, into a smaller bunch of zeroes and ones that mean the same thing. In general, this is impossible to do, since there are less strings of zeroes and ones when you have less digits, so you can’t arbitrarily stuff, say eight bits of information into seven bits. What you can do is create a way to describe the zeroes and ones in a way that is smaller than what you start out with.

For instance, we can describe strings of zeroes and ones in plain English. It’s shorter to write “one hundred zeroes followed by one hundred ones” than writing

00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111

The obvious problem with our compression scheme so far is that there are some strings that are not very easy to describe and it might be longer to describe in English than it would be to just write the bits themselves.

Again, it appears to be difficult to create a compression scheme that works for any old string. It’s much easier to create such an algorithm when you know something about the kind of string you want to compress, like if it’s a certain size or if it has any patterns or something. In the case of the FG lab, we know they won’t need to worry about compressing strings of length 288 or less. Unfortunately, there isn’t much more we know about the strings they want to compress other than the fact that they’re huge.

Actually, there’s another problem, which is that they need a way to decompress the string they’ve sent. If I give you a description of the string in English, it’s not going to do you any good unless you already know English. So in addition to sending a compressed string, they need to send information about the compression scheme they used, all in 36 bytes.

In information theory, the length of the shortest description of a string $x$ is its Kolmogorov complexity, which we’ll denote $C(x)$. Formally, $C(x)$ is defined in terms of encodings of Turing machines that generate $x$, but it’s pretty easy to argue that the choice of how we describe $x$ doesn’t matter up to a constant term.

We know that $C(x) \leq |x| + O(1)$ (where $|x|$ is the length of $x$), since we can always just write out $x$. We also know that for every length $n$, we can always find a string $x$ such that $C(x) \geq |x|$ since there are $2^n$ strings of length $n$ but only $2^n-1$ shorter descriptions of those strings. These strings that can’t be compressed are defined to be random.

We can quantify this idea of compressibility by saying that a string $x$ is $c$-compressible if $C(x) \leq |x| – c$. And so, we can argue about how likely it is that we have a string that can be compressed to the degree that we want. For strings of length $n$, we have that at least $2^n – 2^{n-c+1} + 1$ of them are incompressible by $c$.

We have some numbers, so let’s play around with them. Remember from earlier that the approximate size of Okarin’s memories is 3.24 TB, or $3.24 \times 2^{40} \times 8$ bits, while the limit we can send is 36 $\times$ 8 = 288 bits. If we want to squeeze Okarin’s memories into a text message, we’ll have $c = 3.24 \times 2^{40} \times 8 – 288 = 2.849934139166592 \times 10^{13}$. WolframAlpha helpfully tells me that this is slightly more than 1.4 times as many red blood cells in the human body.

We can calculate the probability that we have a compressible string by figuring out the probability that incompressible, which we can do with our lower bound on the number of incompressible strings we have. Taking $n = 3.24 \times 2^{40} \times 8$, the probability is given by $1 – \frac{2^n – 2^{n-c+1} + 1}{2^n} = \frac{1}{2^{c-1}} – \frac{1}{2^n}$. Plugging our numbers in, we get $\frac{1}{2^{3.24 \times 2^{40} \times 8 – 288 – 1}} – \frac{1}{2^{3.24 \times 8 \times 2^{40}}}$.

And unfortunately, after this step, WolframAlpha kind of refused to try to do the computation. I gave it a shot on my laptop in Python but all that happened was CPU usage went up to 100% for a few minutes and it started eating all of my memory. I kind of wanted to keep using my computer instead of waiting it out for a MemoryError exception, so I interrupted it. Doing some further estimation, I threw $2^{2^{40}}$ at WolframAlpha, since it’s kind of about the same neighbourhood in magnitude as the number we’re trying to get. Apparently, it’s a number that’s about 300 billion digits long, so one in that are the kind of odds you’re looking at.

I guess this is another way of saying there’s no chance in hell that what the FG Lab tried to do would ever work. And remember that we’re not talking about any particular compression algorithms or technologies here. We can’t come up with a better algorithm or scheme. We can’t use faster computers. We can’t use quantum computers (Holevo’s theorem says that we can’t, in general, use less qubits than classical bits for the same string). From an information theoretic standpoint, it is impossible.

But I’m pretty sure everyone already could’ve guessed that anyway.

A typical 19th century French galerie... or is it?

Ikoku Meiro no Croisée, or La croisée dans un labyrinthe étranger, was a pleasant surprise and one of my favourite shows this season. Even though Junichi Sato is only doing series composition, it still feels like Aria. We have girls leaving their homes to go to a strange foreign land and learn about it, set to classy music. All we have to do is trade MANHOME for Japan, Space-Venice for Paris, 23rd century for 19th century, and strings for clarinets.

But there was one thing that caught my eye and has bugged me ever since.

Why does this text on my window look so round?

Now, I’m not a graphic design student or anything. I just think typography is cool, so please bear with me as I play amateur type historian. I’m also not that confident in my ability to identify typefaces on the spot. I’m relying heavily on Linotype’s excellent sans serif history articles and Robert Bringhurst’s excellent The Elements of Typographic Style for more general stuff. I’ve been using a combination of Identifont and FontBook to attempt to identify stuff. Anyhow, I expect I will say some wrong things.

A few months ago, I got the chance to read through some type history for a paper. While most of it was on neoclassical type, which was late 1700s/early 1800s, I did skim through 19th and 20th century stuff. Armed with that knowledge, I thought it was a bit weird seeing stores with sans serif signage in general. But other than the problem of sans serifs possibly existing before they were created, they just felt wrong because they looked too “new”. Croisée is set some time in the second half of the 19th century and a quick search revealed that the earliest sans serif faces showed up early in the 19th century but didn’t get big until almost 100 years later.

An attempted reproduction of the above

So I’m pretty sure this is Futura. If it’s not, it’s definitely a geometric sans serif. And as it turns out, geometric sans serifs are products of the early 20th century, with Futura being created in the 1920s. Geometric faces are born from attempts to form idealized letterforms out of circles and lines, coming out of the whole Constructivist movement. It’s a pretty huge contrast to anything from the Romantic era, which is why it look so strange hiding among all of the old shops in the Galerie.

Definitely not Arial

Here, we have what appears to be Helvetica, that venerable Swiss typeface that is used everywhere nowadays, from subway signage to being slapped on photos on tumblr. Or, at least, I’m pretty sure it’s Helvetica, based on the G. The problem is that Helvetica was created in the 1950s. Of course, that’s not a lot of letters to go by and it could be one of Helvetica’s ancestors, but the earliest of those seems to have appeared in the 1880s or 1890s at the earliest. These typefaces, called Grotesques, were pretty popular in Germany, but didn’t catch on elsewhere until the 20th century. This might make its appearance in Paris a little strange, although I’m not sure of the exact timeline.

The lowercase letters were especially helpful

On this cart, we have a gothic sans serif. Gothics are a British creation from the late 19th century and early 20th century. These are recognizable as the ones that show up in old-timey newspaper headlines. Again, I’m not sure about the exact timeline so I’m not sure how it propagated in Europe, but they were pretty popular in the States. However, it’s my understanding that very few gothics were drawn before 1900.

It was annoying trying to take screens with this lady in the way

Finally, here’s what appears to be a humanist sans serif, based on the R and the C. Humanists are supposed to resemble writing more than the mechanical construction of geometrics or grotesques, but it’s hard to tell from just the capital letters. And again, since there aren’t too many letters to go by, it could turn out to be something else, but I don’t recall seeing anything that resembles that C when going through the other early 20th century typefaces. Anyhow, I feel like that could’ve come straight off of a Windows 7 screen or something.

What other typographical shenanigans are hiding on those storefronts?

I focused on sans serif typefaces because they’re relatively easy to pick out and differentiate between. I’m not pro enough to be able to distinguish between serifed fonts yet. But, this little exercise makes me wonder if there isn’t any typographical weirdness lurking among the signage set in serif faces.

I got started on this entire thing because I remembered Mark Simonson writing about the fonts on the maps in the Indiana Jones movies. I actually didn’t think about it until that Le Papillon d’Or sign caught my eye and made me go ‘waaaaaaait a second’. It’s the first time I remember doing that for anime, probably because most of the time, the signs are in Japanese. I guess the fact that it’s trying to present an accurate historical depiction of Paris also creates a sort of uncanny valley effect and things that would normally get passed over start to pop out.

Anyway, everyone should watch this show, because clarinets and cheese and baguettes and 19th century weeaboos and Yuneeeeeeeeee.

I’ve only been to Anime North once before, four years ago. Back then, I was still reading Naruto, the most novel thing I’d watched was Haruhi, and Lucky Star just started airing. It’d be about another year before I got into my current anime and other Japanese media consumption habits. I ended up coming away from AN unimpressed and I was pretty sure I was done with it. However, a few years of reading interesting blog posts coming out of it and actually having time to go now that I’ve graduated let me dive in and take another look at this anime convention stuff.

Yeah, the first time I went, I basically went on a Saturday and wandered around the dealers’ room with no money, so that probably had something to do with my lacklustre experience. This time, I’d be staying at a hotel with my software engineering pals and would try to actually go to some stuff. Also, I had monies and had an idea of what I wanted to acquire.

Friday started out with discovering that none of the big events actually starts on time. The first thing we went to see (other than the last half of the opening ceremonies because they couldn’t finish on time) was The 404s. They were okay, I guess, but I don’t know if watching Whose Line coloured my impressions of their show. The audience suggestions kinda sucked too so they didn’t have the greatest stuff to work with. Basically, it was not hilarious enough to compel me to watch their show again on Saturday.

After dinner, we managed to spend some time wandering around the dealers’ room, where I scoped out some stuff I wanted to come back for on Saturday after checking prices on Amazon once I got back to the hotel. I ended up with a few CDs (Houkago Tea Time II, cosMo/初音ミクの消失, and buzzG/Symphony) by the time we moved on to line up for Anime Hell. Anime Hell was actually pretty terrible, in large part because about 10% of the content was anime. The rest was just videos on the internet that the MC thought were hilarious. And actual pacing and comedic timing issues aside, it felt like I could’ve spent two hours on /b/ for the same experience.

Saturday was better. I’d went and got those things I’d left behind on Friday in the dealers’ room (Hidamari Sketch for $30/volume and Mameshiba). AN Idol was equal parts decent and eyebrow-raising. Four of the six performances stuck out: the girl with the shiny pants who sang the least best Card Captor Sakura opening, the guy who was off beat and off key for the first half of some One Piece song (who ended up winning), the kid who sang that Full Moon o Sagashite song that inadvertently revealed all the shotacons in the audience, and the break-dancing Gackt guy who forgot the lyrics.

The AMV contest results were okay, other than there being a really low proportion of AMVs that I actually liked. It mostly reinforced my dislike of the entire concept of AMVs. Like, cutting Final Fantasy FMV sequences to a sweeping orchestral track is not something that is hard to do. There was even one of those stereotypical Linkin Park AMVs. How the hell did that happen?

After waiting a few minutes for onigiri and finding out that they forgot to turn on the rice cooker, it was off to wait for the Masquerade thing to start. It was kind of irritating because the MC was really slow and people in the audience don’t stfu and shout generally unfunny things. Most of the costumes were nice and there were a few super impressive ones. Unfortunately, no one really did any characters I really wanted to see. I really liked the FF9 cosplayers though.

Sunday was panel day. AI in anime was kinda dry and I couldn’t hear Refighting WWII because people were being loud assholes right outside the door. Pokemon Biology was the most fantastic thing ever. It involved extrapolating hilarious things from game mechanics and lore, which is exactly the sort of thing I love to do. Topics included the evolution of humans from Mews, Arceus deniers, and Tangela’s ballin’ shoes. The visual novel panel was okay, I guess. There wasn’t much new, but it was kind of neat to see people talking about visual novels, I guess. And then it was back to the dealers’ room to look for artbooks and finding some super expensive pixiv catalogues and not buying them.

I think if I go again, I’ll stay away from the big highlight events and check out more panels or video rooms. I think staying in a hotel that was a 30 minute walk was a huge factor. Of course, it beats going back home across the city each night, but I think I would’ve been much more open to exploring stuff if I’d stayed at the Doubletree.

Loots are: an edamame Mameshiba, Houkago Tea Time II, cosMo/初音ミクの消失, buzzG feat. 初音ミク×VOCALISTS/Symphony, Hidamari Sketch, and Hidamari Sketch ×365.

Happy $\pi$ day. We’ll begin with an obligatory video.

One of the reasons I enjoyed Summer Wars so much is because the main character’s superpower is math. Well, okay, you say, he’s really good at math, but so what? A lot of people complain about the implausibility of OZ, but those of us with a basic understanding of cryptography and number theory will have been drawn to Kenji’s quick problem solving work with an eyebrow raised. So let’s talk about why Kenji is a wizard.

Kenji doing some friggin mathematics

We’ll start with modular arithmetic, which Kenji mentions to Natsuki on the train ride to Ueda. When we divide numbers, we often end up with remainders. Suppose we divide some integer $k$ by $N$ and we get a remainder of $r$. Then we say that $k$ and $r$ are equivalent $\bmod{N}$ and we denote that by $k = r \bmod{N}$. Because it’s how division works, for any integer $k, r$ will be some number from $0$ to $N-1$. It turns out a lot of arithmetic operations work the same way in modular arithmetic: adding, subtracting, and multiplying numbers and then taking the modulus of the result will give you the same number as adding, subtracting, and multiplying the moduli of the numbers you started out with.

However, division doesn’t work as we would expect it to. So we have to think about division (or the equivalent operation) differently. Instead of thinking of division as splitting a group of stuff into smaller groups, we’ll think of it as multiplying by an inverse. What’s an inverse? Well, we can try thinking of it in terms of addition. It’s pretty intuitive that subtraction is the opposite of addition. If we have some integer $k$, then the additive inverse of $k$ is $-k$. When we add $k$ and $-k$, we get $0$, the additive identity. The identity is just the special number that we can add to anything and get that same thing back unchanged ($n+0 = n$). In the same way, if we multiply $k$ by its inverse, $k^{-1}$, then we’ll get $1$, since $k \times 1$ is just $k$ again. What this means is that the inverse of $k \bmod{N}$ is just some other number $j$ from $0$ to $N-1$ such that $j\cdot k = 1 \bmod{N}$ and it’s just multiplication again.

Now, the problem with this is that it’s not guaranteed that there’s always an inverse hanging around in $\bmod{N}$. In particular, if $k$ and $N$ share any divisors, then $k$ won’t have an inverse $\bmod{N}$. This is interesting because it also tells us that if we consider integers mod a prime number $P$, then every integer $\bmod{P}$ has an inverse, since $P$ doesn’t share any divisors with any integers from $0$ to $P-1$. We call these things that have inverses units. So if we have a unit $k$, then $k^m$ is also a unit, for any integer $m$. We even have a funny function $\phi$ defined such that $\phi(n)$ is the number of units in $\bmod{n}$.

Love Machine solicits help

So taking everything we’ve learned, we can set up a cryptosystem! The one we’ll be looking at is called RSA, after the guys who invented it. We have Bob who wants to securely send a message $M$ to Alice. Alice chooses two prime numbers $p$ and $q$ and figures out $m = pq$. She also goes and figures out $\phi(m)$, which happens to be $(p-1)(q-1)$. Finally, she picks some integer $k$, a unit in $\bmod{\phi(m)}$. She lets everyone know $m$ and $k$, but she keeps $p$, $q$, and $\phi(m)$ secret.

So Bob wants to send $M$, which is just his message conveniently in number form. He makes $M$ into a number between $0$ and $m$, and if $M$ is too big, he can just break it up into chunks. Bob figures out the smallest $b$ such that $b = a^k \bmod{m}$ and sends $b$ over to Alice. Now, since Alice has $k$ and $\phi(m)$, she can also find $k^{-1}$ pretty easily. Once she has that, she can get the original message by figuring out $b^{k^{-1}} = (M^k)^{k{-1}} = M \bmod{m}$, since $kk^{-1} = 1 \bmod \phi(m)$.

The interesting thing here is that all of the information is out there for someone to encrypt a message to send to Alice, but no one is able to decrypt it. Well, they’re able to decrypt it if they know what $p$ and $q$ are, since once they’ve got that, they can get $\phi(m)$. But it turns out getting $p$ and $q$ from $m$ (which Alice just throws up on the interwebs) is really hard. And it really works for reals, because RSA is pretty widely deployed for things like keeping your credit card information safe while you send it through the tubes to Amazon.

A conveniently displayed ciphertext

Let’s go back and think about units some more. Of course, there are only $N$ numbers in the integers $\bmod{N}$, so there’s a point at which $k^m$ is just $1$ again and starts over. If $k^m = 1 \bmod{N}$, we say that $m$ is the order of $k$. But why do we care about finding the order of $k$?

It turns out finding the order of elements is very, very similar to factoring an integer into primes and other related problems, like discrete logarithms. If we can find orders of elements, it won’t be too hard to figure out how to factor a number. In this case, the eavesdropper wants to figure out what $p$ and $q$ are, so they’ll want to factor $m$. And it turns out a lot of other public-key cryptosystems (like elliptic curves) are based on the difficulty of factoring.

How hard could it be? Well, we could just check every possibility, which doesn’t seem that bad for a number like 48, but once we get into numbers that are hundreds of digits long, that might start to suck. It turns out the fastest known algorithms for order finding take approximately $e^{O(\log N \log \log N)^{\frac{1}{2}}}$ steps. Current key lengths for RSA are at least 1024 bits, which would give us about 4.4 x 10²⁹ operations. Assuming three trillion operations per second (3 GHz), it’d take a PC about 4.7 billion years. Sure, you could just throw more powerful computers at it, but they’d just double the key size and suddenly, you’d need to do 10⁴⁴ operations.

It's a lot easier to write math than typeset it

Well, that’s not entirely true. One of the breakthroughs in quantum computing was coming up with a fast algorithm for factoring. It turns out quantum order finding takes $O((\log N)^2 \log \log N \log \log \log N)$ steps, which, for a 1024-bit key is just over 60 operations. Doubling the key-size to 2048 bits only increases the number of operations by just over 20. Unfortunately (or fortunately, because we’d be pretty screwed if someone could easily break RSA right now), we haven’t built any quantum computers that large yet, nor are we capable of doing so anytime soon.

tl;dr – Kenji is a quantum computer.