Category Archives: Good Math

My Favorite Strange Number: Ω (classic repost)

I’m away on vacation this week, taking my kids to Disney World. Since I’m not likely to
have time to write while I’m away, I’m taking the opportunity to re-run an old classic series
of posts on numbers, which were first posted in the summer of 2006. These posts are mildly
revised.

Ω is my own personal favorite transcendental number. Ω isn’t really a specific number, but rather a family of related numbers with bizarre properties. It’s the one real transcendental number that I know of that comes from the theory of computation, that is important, and that expresses meaningful fundamental mathematical properties. It’s also deeply non-computable; meaning that not only is it non-computable, but even computing meta-information about it is non-computable. And yet, it’s almost computable. It’s just all around awfully cool.

Continue reading

Continued Fractions (classic repost)

I’m away on vacation this week, taking my kids to Disney World. Since I’m not likely to have time to write while I’m away, I’m taking the opportunity to re-run an old classic series of posts on numbers, which were first posted in the summer of 2006. These posts are mildly revised.

One of the annoying things about how we write numbers is the fact that we generally write things one of two ways: as fractions, or as decimals.

You might want to ask, “Why is that annoying?” (And in fact, that’s what I want you to ask, or else there’s no point in my writing the rest of this!)

It’s annoying because both fractions and decimals can both only describe rational numbers – that is, numbers that are a perfect ratio of two integers. The problem with that is that most numbers aren’t rational. Our standard notations are incapable of representing the precise values of the overwhelming majority of numbers!

But it’s even more annoying than that: if you use decimals, then there are lots of rational numbers that you can’t represent exactly (i.e., 1/3); and if you use fractions, then it’s hard to express the idea that the fraction isn’t exact. (How do you write π as a fraction? 22/7 is a standard fractional approximation, but how do you say π, which is almost 22/7?)

So what do we do?

Continue reading

e: the Unnatural Natural Number (classic repost)

I’m away on vacation this week, taking my kids to Disney World. Since I’m not likely to have time to write while I’m away, I’m taking the opportunity to re-run an old classic series of posts on numbers, which were first posted in the summer of 2006. These posts are mildly revised.

Anyway. Todays number is e, aka Euler’s constant, aka the natural log base. e is a very odd number, but very fundamental. It shows up constantly, in all sorts of strange places where you wouldn’t expect it.

Continue reading

Roman Numerals and Arithmetic

. I’m away on vacation this week, taking my kids to Disney World. Since I’m not likely to
have time to write while I’m away, I’m taking the opportunity to re-run an old classic series
of posts on numbers, which were first posted in the summer of 2006. These posts are mildly
revised.

I’ve always been perplexed by roman numerals.

First of all, they’re just weird. Why would anyone come up with something so strange as a
way of writing numbers?

And second, given that they’re so damned weird, hard to read, hard to work with, why do
we still use them for so many things today?

Continue reading

i: the Imaginary Number (classic repost)

I’m away on vacation this week, taking my kids to Disney World. Since I’m not likely to have time to write while I’m away, I’m taking the opportunity to re-run an old classic series of posts on numbers, which were first posted in the summer of 2006. These posts are mildly revised.

After the amazing response to my post about zero, I thought I’d do one about something that’s fascinated me for a long time: the number i, the square root of -1. Where’d this strange thing come from? Is it real (not in the sense of real numbers, but in the sense of representing something real and meaningful)? What’s it good for?

Continue reading

Zero (classic repost)

This post originally came about as a result of the first time I participated in a DonorsChoose fundraiser. I offered to write articles on requested topics for anyone who donated above a certain amount. I only had one taker, who asked for an article about zero. I was initially a bit taken aback by the request – what could I write about zero? This article which resulted from it ended up turning out to be one of the all-time reader-favorites for this blog!

Continue reading

Book Review: The Manga Guide to Statistics

51b3a5avR5L._SL160_.jpg

I recently got an offer from someone at No-Starch Press to review the
newly translated book, The Manga Guide to Statistics. I recieved the book a couple of weeks ago, but haven’t had time to sit down and read it until now.

If you haven’t heard of the “Manga Guides”, they’re an interesting idea. In Japan, comic books (“Manga”) are much more common and socially accepte than they typically are in the US. It’s not at all unusual to see Japanese adults sitting in the subway reading Manga. Manga has a very distinctive artistic style, with its own
set of common artistic conventions. The Manga Guides are textbooks written as
Manga-style comics. In this case, it’s an introductory text on statistics.

The short version of the review: terrific book; engaging, thorough, and fun. Highly recommended. Details beneath the fold.

Continue reading

Public Key Cryptography using RSA

Technorati Tags: , , , ,

The most successful public key cryptosystem in use today is RSA – named for its inventors Rivest, Shamir, and Adleman. I first learned about RSA in grad school from one of my professors, Errol Lloyd, who was one of Ron Rivest’s students. Errol is without a doubt the best teacher I’ve ever had (and also a thoroughly nice guy). If you want to go to grad school to study algorithms, you frankly couldn’t do better than heading to Delaware to work with Errol. I have very fond memories of Errol’s class where we talked about this. He’s got a way of teaching where he doesn’t come out and tell you anything; what he does is ask questions that lead you through the process of figuring it out yourself. That’s an incredibly effective way to teach if you can carry it off. Personally, I can’t. And I’ve never known anyone except Errol who could do it for a topic like RSA encryption!

Anyway, moving on… In general, public key cryptosystems are based on problems that are easy to solve computationally in one direction, but really hard to solve computationally in the other. In the case of RSA, the basic underlying problem involves prime numbers: if you’ve got two really large prime numbers, then multiplying them together is easy; but if you’ve got a number that’s the product of two really large primes, factoring it is very hard.

Continue reading

Scale: How Large Quantities of Information Change Everything

Technorati Tags: , ,

Since people know I work for Google, I get lots of mail from folks with odd questions, or with complaints about some Google policy, or questions about the way that Google does some particular thing. Obviously, I can’t answer questions about Google. And even if I could, I wouldn’t. This isn’t a Google blog; this is my blog, which I write as a hobby in my free time.

But there are intersections between my work life and my hobby. And one of the ideas that underlies many of the questions that I receive, and which also
hits on my work, and my hobby. And that’s the idea of scale. Scale is computer-science talk for how things change as they get bigger. In particular, I’m talking about the scale of information; the amount of information that we use on a daily basis has increased dramatically, and the amount of dramatic, fundamental change that has resulted is both amazing, and amazingly unnoticed by most people.

Continue reading

Asymmetric Cryptography: the Basic Idea of Public Key Cryptosystems

I’ve been trying for a couple of weeks to put together a couple of interesting posts on the cryptographic modes of operation for confidentiality and integrity, and I just can’t do it. I’m finding it boring to write about, and if it bores me to write it, I know there’s no way that it’s going to be engaging to readers!

So, I’m going to move on. I’ve explained the basic idea of the message authentication code as an integrity check, and I’ve described one simple way of integrating it into a common mode of operation. If you’re really interested in learning more, I recommend Bruce Schnier’s book on cryptography, which has ton of material on modes of operation and protocols, how they work, and how they can fail.

Meanwhile, I’m going to move on to something that doesn’t bore me to write about, and therefore hopefully won’t bore you to read about: asymmetric cryptography, also commonly referred to (although not entirely accurately) as public key cryptography.

Continue reading