Category Archives: Good Math

You can't write that number; in fact, you can't write most numbers.

Leave a reply

In my Dembski rant, I used a metaphor involving the undescribable numbers. An interesting confusion came up in the comments about just what that meant. Instead of answering it with a comment, I decided that it justified a post of its own. It’s a fascinating topic which is incredibly counter-intuitive. To me, it’s one of the great examples of how utterly wrong our
intuitions can be.

Numbers are, obviously, very important. And so, over the ages, we’ve invented lots of notations that allow us to write those numbers down: the familiar arabic notation, roman numerals, fractions, decimals, continued fractions, algebraic series, etc. I could easily spend months on this blog just writing about different notations that we use to write numbers, and the benefits and weaknesses of each notation.

But the fact is, the vast, overwhelming majority of numbers cannot be written
down in any form.

That statement seems bizarre at best. But it does actually make sense. But for it to
make sense, we have to start at the very beginning: What does it mean for a number to be describable?

Continue reading →

A Quick Bit of Temporal Logic: Introducing CTL

Leave a reply

This post is something that I’m thinking of including in my
book. I haven’t decided whether I want to spend this much time on
logics; they’re really interesting and fun – but there’s lots of
other interesting and fun stuff, and there’s only so much space.

The topic of the moment is temporal logic – that is, a logic which
is built for reasoning about things that change over time.

To begin with, why do we want temporal logic? Most of the time,
when we want to use logical reasoning, we use predicate logic. So why
do we need another logic?

Continue reading →

Can simulations replace animal testing? Alas, no.

Leave a reply

My good friend and blogfather, Orac, posted something yesterday about animal testing
in medical laboratories. I’ve been meaning to write something about that for a while; now
seems like a good time.

I’m not someone who thinks that being cruel to animals is no big deal. I have known
some people like that, but thankfully they’re very rare, and none of them
were scientists whose work involves doing animal testing in real laboratories.

But animal testing isn’t about pointless cruelty. It’s about understanding things that we
simply cannot learn about in any other way. It’s extremely important to minimize the
cruelty we inflict on the subjects of animal tests: there’s no benefit in torturing an animal;
there’s no good reason to inflict unnecessary pain on any living thing. When we
can study something without using animals, we should. When we must use animals
in scientific study, we should be as kind to them as we possibly can. But the fact remains that in many cases, animal studies are necessary.

I don’t want to get into a long discussion of the ethics of it here; that’s a discussion
which has been had hundreds of times in plenty of other places, and there’s really no sense
repeating it yet again. But there is one thing I can contribute to this discussion. One of the
constant refrains of animal-rights protesters arguing against animal testing is: “Animal
testing isn’t necessary. We can use computer simulations instead.”

As a computer scientist who’s spent some time studying simulation, I feel qualified
to comment on that aspect of this argument.

The simplest answer to that is the old programmers mantra: “Garbage in, Garbage out”.

Continue reading →

Two-Three Trees: a different approach to balance

Leave a reply
23-thumb.png

This post is very delayed, but things have been busy.

I’m working my way up to finger trees, which are a wonderful
functional data structure. They’re based on trees – and like many
tree-based structures, their performance relies heavily on the balance
of the tree. The more balanced the tree is, the better they perform.

In general, my preference when I need a balanced tree is a red-black
tree, which I wrote about before. But there are other kinds of balanced trees,
and for finger trees, many people prefer a kind of tree called a 2/3 tree.

A two-three tree is basically a B-tree with a maximum of two values per node.
If you don’t know what a B-tree is, don’t worry. I’m going to explain all the details.

A two-three tree is a tree where each node contains either one or two values. If
the node isn’t a leaf, then its number of children is one more than its number
of values. The basic value constraints are the same as in a binary search tree:
smaller values to the left, larger values to the right.

The big difference in the 2/3 tree is balance: it’s got a much stronger
balance requirement. In a 2/3 tree, every path from the tree root to the leaves
is exactly the same length.

Continue reading →

Mr. Spock is Not Logical (book draft excerpt)

Leave a reply

As I mentioned, I’ll be posting drafts of various sections of my book here on the blog. This is a rough draft of the introduction to a chapter on logic. I would be extremely greatful for comments, critiques, and corrections.

I’m a big science fiction fan. In fact, my whole family is pretty
much a gaggle of sci-fi geeks. When I was growing up, every
Saturday at 6pm was Star Trek time, when a local channel show
re-runs of the original series. When Saturday came around, we
always made sure we were home by 6, and we’d all gather in front of
the TV to watch Trek. But there’s one one thing about Star Trek for
which I’ll never forgive Gene Roddenberry or Star Trek:
“Logic”. As in, Mr. Spock saying “But that would
not be logical.”.

The reason that this bugs me so much is because it’s taught a
huge number of people that “logical” means the same
thing as “reasonable”. Almost every time I hear anyone
say that something is logical, they don’t mean that it’s logical –
in fact, they mean something almost exactly opposite – that it
seems correct based on intuition and common sense.

If you’re being strict about the definition, then saying that
something is logical by itself is an almost meaningless
statement. Because what it means for some statement to be
logical is really that that statement is inferable
from a set of axioms in some formal reasoning system. If you don’t
know what formal system, and you don’t know what axioms, then the
statement that something is logical is absolutely meaningless. And
even if you do know what system and what axioms you’re talking
about, the things that people often call “logical” are
not things that are actually inferable from the axioms.

Continue reading →

Basics: Significant Figures

16 Replies

After my post the other day about rounding errors, I got a ton of
requests to explain the idea of significant figures. That’s
actually a very interesting topic.

The idea of significant figures is that when you’re doing
experimental work, you’re taking measurements – and measurements
always have a limited precision. The fact that your measurements – the
inputs to any calculation or analysis that you do – have limited
precision, means that the results of your calculations likewise have
limited precision. Significant figures (or significant digits, or just “sigfigs” for short) are a method of tracking measurement
precision, in a way that allows you to propagate your precision limits
throughout your calculation.

Before getting to the rules for sigfigs, it’s helpful to show why
they matter. Suppose that you’re measuring the radius of a circle, in
order to compute its area. You take a ruler, and eyeball it, and end
up with the circle’s radius as about 6.2 centimeters. Now you go to
compute the area: π=3.141592653589793… So what’s the area of the
circle? If you do it the straightforward way, you’ll end up with a
result of 120.76282160399165 cm2.

The problem is, your original measurement of the radius was
far too crude to produce a result of that precision. The real
area of the circle could easily be as high as 128, or as low as
113, assuming typical measurement errors. So claiming that your
measurements produced an area calculated to 17 digits of precision is
just ridiculous.

Continue reading →

Gap Buffers, or, Don't Get Tied Up With Ropes?

Leave a reply

Last week, I promised to continue my discussion of ropes. I’m going to
break that promise. But it’s in a good cause.

If you’re a decent engineer, one of the basic principles you should
follow is keeping this as simple as possible. One of the essential skills
for keeping things simple is realizing when you’re making something
overly complicated – even if it’s cool, and fun, and interesting.

Working out the rope code for more complex operations, I found myself
thinking that it really seemed complex for what I was doing. What I’m
doing is writing myself a text editor. I’m not writing a string
processing framework for managing gigabytes of data; I’m just writing a
text editor.

So I decided to try, for the purposes of testing, to look at one of
the simpler data structures. A classic structure for implementing editor
buffers is called a gap buffer. I’ll explain the details below.
The drawback of a gap buffer is that large cursor motions are relatively
expensive – the cost of moving the cursor is proportional to the distance
that you move it.

So I wrote a test. I implemented a basic gap buffer. Then I built a
test that did 300,000 inserts of five characters; then slid the cursor
from the end, to the beginning, back to the end, back to the beginning,
and back to the end again. Total execution time? 150 milliseconds. And
that includes resizing the buffer 12 times, because of a deliberately
stupid buffer sizing and copying strategy.

And with that, out the window went the ropes. Because in Java,
using a slapped together, sloppy piece of test code, which does things in a dumb
brute force way, it can do something much more complicated than anything an editor
will encounter in routine use, the gap buffer achieves performance that is more than
adequately fast. (Based on some experiments I did back at IBM, delays of 1/10th
of a second are roughly when people start to notice that an editor is slow. If you can respond is less than 1/10th of a second, people don’t perceive a troublesome delay.)
If the gap buffer can achieve the needed perfomance that easily, then there’s
absolutely no reason to do anything more complicated.

Continue reading →

Ropes: Twining Together Strings for Editors

Leave a reply

It’s been a while since I’ve written about any data structures. But it just so happens that I’m actually really working on implementing a really interesting and broadly useful data structure now, called a Rope.

A bit of background, to lead in. I’ve got this love-hate relationship with some of the development tools that Rob Pike has built. (Rob is one of the Unix guys from Bell labs, and was one of the principal people involved in both the Plan9 and Inferno operating systems.) Rob has implemented some amazing development tools. The two that fascinate me were called Sam and Acme. The best and worst features of both are a sort of extreme elegant minimalism. There’s no bloat in Rob’s tools, no eye-candy, no redundancy. They’re built to do a job, and do it well – but not to do any more than their intended job. (This can be contrasted against Emacs, which is a text editor that’s grown into a virtual operating system.) The positive side of this is that they’re incredibly effective, and they demonstrate just how simple a programmers text editor should be. I’ve never used another tool that is more effective than Acme or Sam. In all seriousness, I can do more of my work more easily in Sam than I can in Emacs (which is my everyday editor). But on the other hand, that extreme minimalist aesthetic has the effect of strictly eliminating any overlaps: there’s one way to do things, and if you don’t like it, tough. In the case of Acme and Sam, that meant that you used the mouse for damn-near everything. You couldn’t even use the up and down arrows to move the cursor!

This is a non-starter for me. As I’ve mentioned once or twice, I’ve got terrible RSI in my wrists. I can’t use the mouse that much. I like to keep my hands on my keyboard. I don’t mind using the mouse when it’s appropriate, but moving my hand from the keyboard to the mouse every time I want to move the cursor?. No. No damned way. Just writing this much of this post, I would have had to go back and forth between the keyboard and mouse over 50 times. (I was counting, but gave up when I it 50.) A full day of that, and I’d be in serious pain.

I recently got reminded of Acme, because my new project at work involves using a programming language developed by Rob Pike. And Acme would really be incredibly useful for my new project. But I can’t use it. So I decided to bite the bullet, and use my free time to put together an Acme-like tool. (Most of the pieces that you need for a prototype of a tool like that are available as open-source components, so it’s just a matter of assembling them. Still a very non-trivial task, but a possible one.)

Which finally, leads us back to today’s data structure. The fundamental piece of a text editor is the data structure that you use to represent the text that you’re editing. For simplicity, I’m going to use Emacs terminology, and refer to the editable contents of a file as a Buffer.

How do you represent a buffer?

As usual with data structures, you start by asking: What do I need it to do? What performance characteristics are important?

In the case of a text buffer, you can get by with a fairly small set of basic operations:

  • Fast concatenation: concatenating blocks of text needs to be really fast.
  • Fast insert: given a point in a block of text, you need to be able to quickly insert text at that point.
  • Fast delete: given two points in a block of text, you need to be able to quickly remove the text between those points.
  • Reasonably fast traversal: Lots of algorithms, ranging from printing out the text to searching it are based on linear traversals of the contents. This doesn’t have to be incredibly fast – it is an intrinsically linear process, and it’s usually done in the context of something with a non-trivial cost (I/O, regular-expression scanning). But you can’t afford to make it expensive.
  • Size: you need to be able to store effectively unlimited amounts of text, without significant performance degradation in the operations described above.

Continue reading →

Cryptographic Padding in RSA

Leave a reply

Ok, away from politics, and back to the good stuff. When I left off talking about
encryption, we were looking at
RSA, as an example of an asymmetric encryption system.

Since it’s been a while, I’ll start off with a quick review of RSA.

Asymmetric encryption systems like RSA are based on computations that are easy to perform if you know the keys, and incredibly hard to perform if you don’t. In the specific case
of RSA, everything is based on a pair of very large prime numbers. If you know those two
primes, and you know the public key, it’s really easy to compute the private key. But
if you don’t know the two prime numbers, then even given the public key,
it’s incredibly difficult to compute the private key.

To be a bit more specific, in RSA, you get a pair of large prime numbers, P and Q. You
compute from them a totient of their product, which is the number
N=(P-1)×(Q-1). Then you arbitrarily pick a public exponent, E, which is
smaller than N, and which is prime relative to N. You can then compute
the private key exponent, D. If you know what P and Q are, it’s pretty easy to compute
D.

Once you’ve got D and E, your public key is the pair is (N,E), and the private key is the pair is (N,D).

If you’ve got a plaintext message M, then encrypting it with the public key
is done by computing ME mod N. If you’ve got a ciphertext C encrypted
with the public key, then decrypting it is done by computing CD mod N.

Encrypting a plaintext with the public key is exactly the same process
as decrypting a ciphertext produced with the private key. And vice versa.

Continue reading →