Month: May 2013

Extreme syntax

Posted on by John

In his book Let Over Lambda, Doug Hoyte says

Lisp is the result of taking syntax away, Perl is the result of taking syntax all the way.

Lisp practically has no syntax. It simply has parenthesized expressions. This makes it very easy to start using the language. And above all, it makes it easy to treat code as data. Lisp macros are very powerful, and these macros are made possible by the fact that the language is simple to parse.

Perl has complex syntax. Some people say it looks like line noise because its liberal use of non-alphanumeric characters as operators. Perl is not easy to parse — there’s a saying that only Perl can parse Perl — nor is it easy to start using. But the language was designed for regular users, not beginners, because you spend more time using a language than learning it.

There are reasons I no longer use Perl, but I don’t object to the rich syntax. Saying Perl is hard to use because of its symbols is like saying Greek is hard to learn because it has a different alphabet. It takes years to master Greek, but you can learn the alphabet in a day. The alphabet is not the hard part.

Symbols can make text more expressive. If you’ve ever tried to read mathematics from the 18th or 19th century, you’ll see what I mean. Before the 20th century, math publications were very verbose. It might take a paragraph to say what would now be said in a single equation. In part this is because notation has developed and standardized over time. Also, it is now much easier to typeset the symbols someone would use in handwriting. Perl’s repertoire of symbols is parsimonious compared to mathematics.

I imagine that programming languages will gradually expand their range of symbols.

People joke about how unreadable Perl code is, but I think a page of well-written Perl is easier to read than a page of well-written Lisp.  At least the Perl is easier to scan: Lisp’s typographical monotony makes it hard to skim for landmarks. One might argue that a page of Lisp can accomplish more than a page of Perl, and that may be true, but that’s another topic.

* * *

Any discussion of symbols and programming languages must mention APL. This language introduced a large number of new symbols and never gained wide acceptance. I don’t know that much about APL, but I’ll give my impression of why I don’t think APL’s failure is not proof that programmers won’t use more symbols.

APL required a special keyboard to input. That would no longer be necessary. APL also introduced a new programming model; the language would have been hard to adopt even without the special symbols. Finally, APL’s symbols were completely unfamiliar and introduced all at once, unlike math notation that developed world-wide over centuries.

* * *

What if programming notation were more like music notation? Music notation is predominately non-verbal, but people learn to read it fluently with a little training. And it expresses concurrency very easily. Or maybe programs could look more like choral music, a mixture of symbols and prose.

Synchronizing cicadas with Python

Posted on by John

Suppose you want to know when your great-grandmother was born. You can’t find the year recorded anywhere. But you did discover an undated letter from her father that mentions her birth and one curious detail:  the 13-year and 17-year cicadas were swarming.

You do a little research and find that the 13-year cicadas are supposed to come out next year, and that the 17-year cicadas came out last year. When was your great-grandmother born?

Since 13 and 17 are relatively prime, the 13-year and 17-year cicadas will synchronize their schedules every 13 × 17 = 221 years. Suppose your great-grandmother was born n years ago. The remainder when n is divided by 13 must be 12, and the remainder when n is divided by 17 must be 1. We have to solve the pair of congruences n = 12 mod 13 and n = 1 mod 17. The Chinese Remainder Theorem says that this pair of congruences has a solution, and the proof of the theorem suggests an algorithm for computing the solution.

The Python library SymPy has a function for solving linear congruences.

    >>> from sympy.ntheory.modular import solve_congruence
    >>> solve_congruence( (12, 13), (1, 17) )
    (103, 221)

This says we’re 103 years into the joint cycle of the 13-year and 17-year cicadas. So your great-grandmother was born 103 years ago. (The solution 324 = 103 + 221 is also mathematically possible, but not biologically possible.)

You can use the same SymPy function to solve systems of more congruences. For example, when is the next year in which there will be summer Olympic games and the 13-year and 17-year cicadas will swarm? Here are a couple ways to approach this. First, you could find the last time this happened, then find when it will happen next. You’d need to solve n = 1 mod 4 (since we had summer Olympics last year) and  n = 12 mod 13 and n = 1 mod 17.

    >>> solve_congruence( (1, 4), (12, 13), (1, 17) )
    (545, 884)

So the cicadas and the summer Olympics were in sync 545 years ago. (Well, they would have been if the modern Olympics had existed in the middle ages.) This says they’ll be in sync again in 885 – 545 = 339 years.

Here’s a more direct approach. We want to know when the summer Olympics will be 3 years ahead of where they are now in the cycle, when the 13-year cicadas will be 1 year ahead, and the 17-year cicadas will be 16 years ahead.

    >>> solve_congruence( (3, 4), (1, 13), (16, 17) )
    (339, 884)

By the way, you can use negative integers with the congruences, so you could have used (-1, 17) to say the 17-year cicadas will be 1 year back instead of 16 years ahead in their cycle.

Related: Applied number theory

Searching for Perrin pseudoprimes

Posted on by John

A week ago I wrote about Perrin numbers, numbers Pn defined by a recurrence relation similar to Fibonacci numbers. If n is prime, Pn mod n = 0, and the converse is nearly always true. That is, if  Pn mod n = 0, n is usually prime. The exceptions are called Perrin pseudoprimes.

Matt McIrvin wrote an excellent post explaining how to compute Perrin pseudoprimes. Here I’m just going to elaborate on a couple points in his post.

Matt’s first point is that if you want to search for Perrin pseudoprimes, the most direct approach won’t get you very far. The obvious thing to do is compute Pn and then see whether it has remainder 0 when you divide by n. The problem is that Pn grows exponentially with n. In fact, Pn is approximately ρn where ρ = 1.3247… is the plastic number. This means that Pn has about n log10 ρ digits. So searching for pseudoprimes less than one billion would require working with numbers with over 100,000,000 digits. This can be done, but it’s slow and unnecessary.

Since the goal is to compute Pn mod n rather than Pn per se, we can carry out all calculations mod n and avoid extended precision arithmetic as long as n itself can fit in an ordinary precision integer. If we want to find pseudoprimes less than one billion, we calculate Pn mod n for each n up to N = 109. This only requires ordinary arithmetic.

However, this approach takes O(N2) time unless we’re clever. We have to compute Pn mod n separately for each n, and the most direct approach takes n steps. This leads to Matt’s second point: use matrix multiplication (mod n) to calculate Pn mod n. This requires calculating the nth power of a 3×3 matrix, which can be done in O(log n) time using fast exponentiation. This makes the search for pseudoprimes less than N require O(N log N) rather than O(N2) time. This is enough to make the search for pseudoprimes less than a billion practical.

Related: Applied number theory

Looking in both directions

Posted on by John

From David Mumford’s May 2013 interview in SIAM News:

The applied mathematician has the difficult job of looking at a problem in context with no explicit mathematics and trying to see what kinds of mathematical ideas are under the surface that could clarify the situation. I think the most successful applied mathematicians are those who look in both directions, at the science and the math.

You can’t become too attached to one way of looking at things. Applied math has always rejuvenated pure, and theorems in pure math can unexpectedly lead to new tools with vast applications.

Emphasis added. I wish Mumford had said “at the problem and at the math” because not all applications of math are to science.

Related posts

Dogfooding

Posted on by John

Dogfooding refers companies using their own software. According to Wikipedia,

In 1988, Microsoft manager Paul Maritz sent Brian Valentine, test manager for Microsoft LAN Manager, an email titled “Eating our own Dogfood”, challenging him to increase internal usage of the company’s product. From there, the usage of the term spread through the company.

Dogfooding is a great idea, but it’s no substitute for usability testing. I get the impression that some products, if they’re tested at all, are tested by developers intimately familiar with how they’re intended to be used.

If your company is developing consumer software, it’s not dogfooding if just the developers use it. It’s dogfooding when people in sales and accounting use it. But that’s still no substitute for getting people outside the company to use it.

Dogfooding doesn’t just apply to software development. Whenever I buy something with inscrutable assembly instructions, I wonder why the manufacturer didn’t pay a couple people off the street to put the thing together on camera.

NYT Book of Mathematics

Posted on by John

Today’s newspaper may be interesting because it reports new information.

Newspapers from decades ago may be interesting for different reasons, not for the explicit content but for the implicit content. What were the contemporary reactions to what’s now well known? What were the readers expected to know and not know? To be impressed by?

But the newspapers in between are not so interesting. They’re not news and they’re not history.

The New York Times has just published their Book of Mathematics, a collection of over 100 math articles written from 1892 to 2010. Most of the articles are toward the 2010 end of the timeline. I found most of the articles to be old news but not old enough to be historically interesting.

However, I’m a professional mathematician, and these articles were written for a popular audience. The intended audience for the original articles, as well as the new compilation, would probably enjoy the book more. On the other hand, these are newspaper articles: lots of text, no color, and few illustrations. People who read popular math books might have less patience for this book.

One of the articles I did enjoy was “The Electronic Digital Computer: How It Started, How It Works and What It Does” from 1967. It’s the longest article in the book at 20 pages, and goes into some depth. Of course parts of it are also quaint.

I also enjoyed “A Soviet Discovery Rocks World of Mathematics” from 1979. It’s jarring now to hear the adjective “Soviet” applied to a mathematical result, but I assume this was not remarkable at the time. The article is about Khachiyan’s discovery of the first polynomial time algorithm for solving linear programming problems. The algorithm was impractical but groundbreaking. It quickly led to new algorithms that were efficient in theory and in practice. The article has a hint of panic between the lines, something like the reaction to Sputnik but to a lesser degree.

* * *

Andrew Gelman wrote a short review of this book on his blog a few days ago. I put off reading his review until I had written my own above. His reaction was similar to mine:

… Fun for the math content and historical/nostalgia value. … I have too much of a technical bent to be the ideal reader for this sort of book, but it seems like an excellent gift for a non-technical reader who nonetheless enjoys math. … My own preference would have been … more old stuff.

Efficiency vs. Robustness

Posted on by John

Something is efficient if it performs optimally under ideal circumstances.

Something is robust if it performs pretty well under less than ideal circumstances.

Life is full of trade-offs between efficiency and robustness. Over time, I’ve come to place more weight on the robustness side of the trade-off. I imagine that’s typical. With more experience, you become more willing to concede that you haven’t thought of everything that could happen. After a while, you notice that events with a “one in a million” chance of occurring happen much more often than predicted.

Robust things are often more efficient than efficient things are robust. That is, robust strategies often do fairly well under ideal circumstances. You may not give up much efficiency for robustness. But efficient strategies can fail spectacularly when the assumptions they’re based on don’t hold.

Related post: Six-sigma events

Asteroids can have moons

Posted on by John

This afternoon my postman delivered a review copy of The Space Book by Jim Bell. This is the latest book in a series that includes Cliff Pickover’s math, physics, and medical books. Like the other books in the series, The Space Book alternates one-page articles and full-page color images.

Here’s something I learned while skimming through the book: Asteroids can have moons. (That’s the title of the article on page 414.) This has been known since the early 1990’s, but it’s news to me.

The first example discovered was a satellite now named Dactyl orbiting the asteroid 243 Ida. The Space Book says Dactyl was discovered in 1992. Wikipedia says Dactyl was photographed by the Galileo spacecraft in 1993 and discovered by examining the photos in February of 1994. Since that time, “more than 220 minor planet moons have been found.”

Almost if and only if

Posted on by John

The Perrin numbers have a definition analogous to Fibonacci numbers. Define P0 = 3, P1 = 0, and P2 = 2. Then for n > 2, define

Pn+3 = Pn+1 + Pn+0.

The Concrete Tetrahedron says

It appears that n is prime “almost if and only if” Pn mod n = 0.

The “only if” condition is true without qualification: if n is prime, Pn mod n = 0. It’s the “if” part that’s almost true. When Pn mod n = 0, n is usually prime. Composite numbers that satisfy the Perrin condition Pn mod n = 0 are called Perrin pseudoprimes. The smallest Perrin pseudoprime is 271,441. The next is 904,631.

There are only 17 Perrin pseudoprimes less than a billion. By comparison, there are 50,847,534 primes less than a billion.

So if you used the Perrin condition to test whether numbers less than a billion are prime, you would correctly identify all 50,847,534 primes as primes. But out of the 949,152,466 composite numbers, you would falsely report 17 of these as prime.  In other words, you would be 100% accurate in identifying primes as primes, but only 99.999998% accurate in identifying composite numbers as composite.

Related posts