Log semiring

Here’s a strange way to do arithmetic on the real numbers.

First, we’ll need to include +∞ and -∞ with the reals.

We define the new addition of two elements x and y to be -log (exp(-x) + exp(-y) ).

We define the new multiplication to be ordinary addition. (!)

In this new arithmetic +∞ is the additive identity and 0 is the multiplicative identity.

This new algebraic structure is called the log semiring. It’s called a semiring because it satisfies all the properties of a ring except that elements don’t necessarily have additive inverses. We’ll get into the details of the definition below.

***

Let’s put a subscript S on everything associated with our semiring in order to distinguish them from their more familiar counterparts. Then we can summarize the definitions above as

  • a +S  b = -log (exp(-a) + exp(-b) )
  • a *S  b = a + b
  • 0S = +∞
  • 1S = 0

Note that if we define

f(a, b) = a +S  b

then

f(a, b) = -g(-a, -b)

where g(a, b) is the soft maximum of a and b.

***

Finally, we list the axioms of a semiring. Note that these equations all hold when we interpret +, *, 0, and 1 in the context of S, i.e. we imagine that each has a subscript S and is as defined above.

  • (a + b) + c = a + (b + c)
  • 0 + a = a + 0 = a
  • a + b = b + a
  • (a * b) * c = a * (b * c)
  • 1 * a = a * 1 = a
  • a * (b + c) = (a * b) + (a * c)
  • (a + b) * c = (a * c) + (b * c)
  • 0 * a = a * 0 = 0

Each of these follows immediately from writing out the definitions.

Read More

Writing down an unwritten language

In this post I interview Greg Greenlaw, a friend of mine who served as a missionary to the Nakui tribe in Papua New Guinea and developed their writing system. (Nakui is pronounced like “knock we.”)

JC: When you went to PNG to learn Nakui was there any writing system?

GG: No, they had no way of writing words or numbers. They had names for only seven numbers — that was the extent of their counting system — but they could coordinate meetings more than a few days future by tying an equal number of knots in two vines. Each party would take a vine with them and loosen a knot each morning until they counted down to the appointed time — like and advent calendar, but without numbers!

(more…)

Read More

Imaginary gold, silver, bronze, …

The previous post gave a relationship between the imaginary unit i and the golden ratio. This post highlights a comment to that post explaining that the relationship generalizes to generalizations of the golden ratio.

GlennF pointed out that taking the larger root of the equation

\phi_n = n + \frac{1}{\phi_n}

defines the golden ratio when n = 1, the silver ratio when n = 2, etc. φn is also the continued fraction made entirely of n‘s.

With this definition, we have

2 \sin \left( i \log \phi_n \right)  = ni

Read More

Mental callouses

In describing writing his second book, Tom Leinster says

… I’m older and, I hope, more able to cope with stress: just as carpenters get calloused hands that make them insensitive to small abrasions, I like to imagine that academics get calloused minds that allow them not to be bothered by small stresses and strains.

Mental callouses are an interesting metaphor. Without the context above, “calloused minds” would have a negative connotation. We say people are calloused or insensitive if they are unconcerned for other people, but Leinster is writing of people unperturbed by distractions.

You could read the quote above as implying that only academics develop mental discipline, though I’m sure that’s not what was intended. Leinster is writing a personal post about the process of writing books. He’s an academic, and so he speaks of academics.

Not only do carpenters become more tolerant of minor abrasions, they also become better at avoiding them. I’m not sure that I’m becoming more tolerant of stress and distractions as I get older, but I do think I’m getting a little better at anticipating and avoiding stress and distractions.

 

 

Read More

Categories, Birds, and Frogs

Freeman Dyson divided mathematicians into birds and frogs in his essay by that title.

Some mathematicians are birds, others are frogs. Birds fly high in the air and survey broad vistas of mathematics out to the far horizon. They delight in concepts that unify our thinking and bring together diverse problems from different parts of the landscape. Frogs live in the mud below and see only the flowers that grow nearby. They delight in the details of particular objects, and they solve problems one at a time.

It’s an interesting metaphor. Like all metaphors it has its limits and Dyson discusses that. Some people are somewhere between a bird and a frog, whatever kind of creature that would be, and some alternate between being birds and frogs.

The other day I thought about Dyson’s classification and wondered whether category theorists would be birds or frogs. At first category theory seems avian, looking for grand patterns across mathematics. But as you wander further in, it seems more batrachian, absorbed in drawing little boxes and arrows.

I find it interesting that category theory can profound or trivial, depending on your perspective.

The motivations and applications are profound. Category theory has been called “metamathematics” because it formalizes analogies between diverse areas of math. But basic category theory itself is very close to its axioms. The path from first principles to common definitions and theorems in category theory is much shorter than, say, the path from the definition of the real numbers to the fundamental theorem of calculus.

(This diagram quantifies the last claim to some extent: the graph of concept dependencies in category theory is more wide than deep, and not that deep. Unfortunately I don’t have a similar diagram for calculus.)

Related post: Concepts, explosions, and developments

Read More

“Conventional” is relative

I found this line from Software Foundations amusing:

… we can ask Coq to “extract,” from a Definition, a program in some other, more conventional, programming language (OCaml, Scheme, or Haskell) with a high-performance compiler.

Most programmers would hardly consider OCaml, Scheme, or Haskell “conventional” programming languages, but they are conventional relative to Coq. As the authors said, these languages are “more conventional,” not “conventional.”

I don’t mean to imply anything negative about OCaml, Scheme, or Haskell. They have their strengths — I briefly mentioned the advantages of Haskell just yesterday — but they’re odd birds from the perspective of the large majority of programmers who work in C-like languages.

Read More

Real World Haskell

I’m reading Real World Haskell because one of my clients’ projects is written in Haskell. Some would say that “real world Haskell” is an oxymoron because Haskell isn’t used in the real world, as illustrated by a recent xkcd cartoon.

It’s true that Haskell accounts for a tiny portion of the world’s commercial software and that the language is more popular in research. (There would be no need to put “real world” in the title of a book on PHP, for example. You won’t find a lot of computer science researchers using PHP for its elegance and nice theoretical properties.) But people do use Haskell on real projects, particularly when correctness is a high priority.[1] In any case, Haskell is “real world” for me since one of my clients uses it. As I wrote about before, applied is in the eye of the client.

I’m not that far into Real World Haskell yet, but so far it’s just what I was looking for. Another book I’d recommend is Graham Hutton’s Programming in Haskell. It makes a good introduction to Haskell because it’s small (184 pages) and focused on the core of the language, not so much on “real world” complications.

A very popular introduction to Haskell is Learn You a Haskell for Great Good. I have mixed feelings about that one. It explains most things clearly and the informal tone makes it easy to read, but the humor becomes annoying after a while. It also introduces some non-essential features of the language up front that could wait until later or be left out of an introductory book.

***

[1] Everyone would say that it’s important for their software to be correct. But in practice, correctness isn’t always the highest priority, nor should it be necessarily. As the probability of error approaches zero, the cost of development approaches infinity. You have to decide what probability of error is acceptable given the consequences of the errors.

It’s more important that the software embedded in a pacemaker be correct than the software that serves up this blog. My blog fails occasionally, but I wouldn’t spend $10,000 to cut the error rate in half. Someone writing pacemaker software would jump at the chance to reduce the probability of error so much for so little money.

On a related note, see Maybe NASA could use some buggy software.

Read More

Where combinator names come from

Today I found out where the one-letter names of some functions in combinatory logic come from. I’d seen these before (for example, in To Mock a Mockingbird) but I had no idea what inspired the names.

These functions — I, K, S, T, and Z — are known as the Schönfinkel combinators, and their names are somewhat mnemonic in German. (Only somewhat. Don’t get your hopes up.)

Definition Name Name origin
λx. x I Identitätsfunktion (identity function)
λx,y. x K Konstanzfunktion (constant function)
λx,y,z. xz(yz) S Verschmelzungsfunktion (amalgamation function)
λx,y,z. xzy T Vertauschungsfunktion (exchange function)
λx,y,z. x(yz) Z Zusammensetzungsfunktion (composition function)

Source: Practical Foundations of Mathematics, footnote on page 89. Available online here.

If you’re not familiar with the notation in the function definitions, see this introduction to lambda calculus.

Read More

What good is an old weather forecast?

Why would anyone care about what the weather was predicted to be once you know what the weather actually was? Because people make decisions based in part on weather predictions, not just weather. Eric Floehr of ForecastWatch told me that people are starting to realize this and are increasingly interested in his historical prediction data.

This morning I thought about what Eric said when I saw a little snow. Last Tuesday was predicted to see ice and schools all over the Houston area closed. As it turned out, there was only a tiny amount of ice and the streets were clear. This morning there actually is snow and ice in the area, though not much, and the schools are all open. (There’s snow out in Cypress where I live, but I don’t think there is in Houston proper.)

Aftermath of last Tuesday’s storm

Related posts:

Interview with Eric Floehr
Accuracy versus perceived accuracy
History of weather prediction

Read More

Time and Productivity

Contractors were working on my house all last week. I needed to be home to let them in, to answer questions, etc., but the noise and interruptions meant that home wasn’t a good place for me to work. In addition, my Internet connection was out for most of the week and I had a hard disk failure.

Looking back on the week, my first thought was that the week had been an almost total loss, neither productive nor relaxing. But that’s not right. The work I did do made a difference, reinforcing my belief that effort and results are only weakly correlated. (See Weinberg’s law of twins.)

Sometimes you have a burst of insight or creativity, accomplishing more in a few minutes than in an ordinary day. But that didn’t happen last week.

Sometimes your efforts are unusually successful, either because of the preparation of previous work or for unknown reasons. That did happen last week.

Sometimes you simply work on more important tasks out of necessity. Having less time to work gives focus and keeps work from expanding to fill the time allowed. That also happened last week.

***

I did get out of the house last Tuesday and wrote about it in my previous post on quality over quantity. This turned out to the theme of the week.

Read More