# Sleeping Cyborg

Jonathan David Page talks about whatever he happens to be thinking about. Sometimes other people join in.

## Digest for 5 April 2013

by on 5 April 2013
under , , , , , , , ,

Today marks 50 years until first contact with the Vulcan.

The Mozilla Javascript team posted a really interesting article explaining how the SpiderMonkey engine works and what they just did to make it better.

I finally got around to reading an article which turned out to be one of the better analyses of the social media phenomenon. I call it an analysis because it doesn’t say “social media is a Bad Thing”, like a lot of the more sensational article-writers (including myself, at times) do. It talks more about how some patterns of social media are Bad Things, which is more constructive since it can lead to ways to fix those patterns.

Bad Catholic published a guest post with perhaps the single best explanation of the Catholic obsession with the Virgin Mary that I’ve ever read.

And finally, I’ve decided that I am going to start posting digests (like this one) with links to interesting articles and some remarks on them.

## Approximating Pi Redux

by on 20 December 2012
under , ,

No, it isn’t Pi Day, or anything resembling it. I was editing some stuff, and I noticed the original “Approximating Pi” article. I’d been meaning to rewrite the code since I learned about continued fractions, and since I didn’t have anything better to do1, I decided to do so. A detailed explanation follows the source code2, since this is less mathematically facile than the previous version.

This version is slightly different from the previous one, in that it generates all of the best rational approximations of pi, in order. According to Wikipedia:

A best rational approximation to a real number x is a rational number n/d, d > 0, that is closer to x than any approximation with a smaller denominator.

The first 16 terms output are:

rational decimal
3/1 3.000000000000000
13/4 3.250000000000000
16/5 3.200000000000000
19/6 3.166666666666667
22/7 3.142857142857143
179/57 3.140350877192982
201/64 3.140625000000000
223/71 3.140845070422535
245/78 3.141025641025641
267/85 3.141176470588235
289/92 3.141304347826087
311/99 3.141414141414141
333/106 3.141509433962264
355/113 3.141592920353983
52163/16604 3.141592387376536
52518/16717 3.141592390979242

This suggests that as far as rational approximations of pi go, 355/113 looks like it might be the best bang for your buck. (The jump in size without much improvement corresponds to an abnormally large term in the continued fraction expansion.)

View the code on Github

### General Concepts

This code relies pretty heavily on continued fractions, which take a little bit of explaining. They’re basically a slightly arcane way of writing real numbers which has some nice properties. Let’s take 3.456 — or 432/125 — as an example. It’s kind of like 3, but a bit more. More like 3 + 1/2. But not really 2, more like 2 + 1/5. But not really 5, more like 5 + 1/5. But not really 5, more like 5 + 1/2. Actually, exactly like 5 + 1/2. This leaves us with the following monster3:

But instead of writing out all of those 1s, we could just write [3; 2, 5, 5, 2]. That’s a continued fraction. If you want to make things more complicated, you could have something other than 1s in the numerators, in which case you’d have a generalized continued fraction. (The normal kind are also known as simple continued fractions, to distinguish them from the generalized kind.)

Why would you want such a horrible thing? There are a variety of reasons (some of which I don’t even pretend to understand), but in this case, we’re going to take advantage of their approximation superpowers.

### pi_noncanon_seq()

You know how I said that you can make things more complicated? Well, that’s exactly what this function does. It spits out a generalized continued fraction which is equal to pi4. We have to use a generalized continued fraction, because the simple continued fraction for pi has no known pattern, and appears to be more or less random.

### canonicalize(seq)

Because generalized continued fractions tend to not only be slightly inconvenient to work with, but also lack the property that we’re after (more on that later), we convert it into a simple continued fraction.

Given a continued fraction, define x to be the expansion of the whole sequence, and x' to be the part that we don’t know. Thus, before we receive any terms, we have x = x'.

In this function, the variables a through d represent the homographic5 function . This function establishes bounds on the value of x. Assume that x' is between 0 and infinity6. At one end, x' = 0, so that x = b/d. On the other end, if we take the limit as x' approaches infinity, x = a/c. These represent our lower and upper and bounds of x, not respectively.

Now, if we take a term (p, q), indicating that the unknown part x' = p + q/x'', where x'' is the part that is still unknown, we can substitute into our homographic form and get

Multiplying the numerator and denominator by x'' simplifies this to

This is equivalent to the expression a, b, c, d = p*a+b, q*a, p*c+d, q*c in the code.

We then evaluate the integer parts of the bounds, and when they are the same, we know for sure what the integer part of the number is, so we can yield that, and remove it from the total.

The reciprocation is there, of course, because we’re trying to do a simple continued fraction, and we want it to match general form above. This is equivalent to the expression a, b, c, d = c, d, a-t*c, b-t*d.

The result is that the function takes in terms of the generalized continued fraction, until it can produce a term of the simple continued fraction, at which point it does so, removing it from the running total.

### condense()

This function follows the same pattern as canonicalize(), but instead of spitting out the integral part as soon as it knows it, waits until it has taken all of the terms (note that it takes a finite sequence), and outputs a rational number equivalent to the simple continued fraction we started with. Note that the upper bound is given, since the last term of a terminating continued fraction is always infinity.

### seq_cmp(seqa, seqb)

This one is pretty much straight from Gosper7:

If we call the integer part of a continued fraction the 0th term, then we can say that the a (regular) continued fraction is an increasing function of its even numbered terms, and a decreasing function of its odd numbered terms. Thus, to compare two continued fractions, compare the terms at the first position where they differ, then reverse the decision if this position is odd numbered. If one continued fraction terminates before differing from the other, regard the shorter one to be suffixed by an infinite term.

Here, I use None to represent infinity.

### best_rational_approximations(seq)

This is the function which performs the main purpose of the script. It essentially takes advantage of the fact that you can use the continued fraction to generate a best rational approximation of a number by truncating the continued fraction at some point, then converting it to a regular fraction. Furthermore, the last term of the truncated sequence can be reduced by up to half of its value to produce yet more best rational approximations. There’s a borderline case for even trailing terms, since they are divisible by two exactly; in that case, the result is a best rational approximation only if it’s better than the previous one in the sequence. This is equivalent8 to checking whether the terms encountered so far, reversed, are a greater continued fraction than the remaining terms9.

1. This is a lie. I do, in fact, have a number of things to do that various people might define as “better”, but I didn’t feel like doing any of them. I felt like sitting around in my bathrobe and writing Python.

2. Sorry about the horizontal scrolling; the code is wrapped to 80 characters, but my blog is rather narrower than that. If it bothers you, there’s a link at the bottom of the code so that you can view it on GitHub.

3. If you’re reading this in an RSS reader or something, you may want to consider clicking over to the actual site. There’s a script which converts all of the LaTeX to images.

4. According to doi:10.2307/2589152, it’s a special case of the arctan function.

5. Strictly speaking, if c = 0, then it isn’t homographic. It’s a linear polynomial.

6. Since x' is a continued fraction composed of positive integers, it’s trivial to demonstrate that x' is itself positive. Note that it’s a toroidal space, so the interval could be inside or outside the bounds, depending on a variety of things, including the sign of d

7. Because Gosper says so.

8. The nonsense with tee() is due to the fact that Python generators are so narrow-minded as to go one-way, and they can’t be cloned. Haskell lists are actually perfect for continued fractions in pretty much every way, but the Haskell version of this code is, unsurprisingly, even more incomprehensible than this, so I decided not to complicate the issue.

## Why I Hate Politics

by on 12 September 2012
under , ,

Okay, there are a couple reasons I hate politics1. The one I want to talk about right this instant is this one which I’m sure many engineers2 agree with: that the system itself is broken. Yes, the Constitution, as written, is a great basis. It’s flexible, largely balanced between various branches, contains provisions for its own modification, pretty fair, protects human rights: all good stuff. Then again, a lot of people feel this way, and they can argue about politics all day. What is my point?

My point, and my problem, is that I regularly find myself looking at a political question and, rather than choosing a side, find myself unasking3 the question. In other words, I take the position that the question itself is wrong. Not only that, but when someone presents an argument against my opinion based on another government policy, my response ends up being “actually, that’s broken too.” (This response tends to be pretty well-received.)

I’m sure many other people with much more sense than I feel this way, but for some reason I find it crippling when it actually comes down to acting on my opinions. Perhaps they see the system, and realize that it’s too entrenched4 to change, and so decide to make the best of a bad lot. Now that I am able to vote, I find myself struggling more and more to decide what the best course of action to take there is. I wish to vote, but I also don’t want to vote for someone championing a suboptimal solution.

Perhaps I’m just too much of an idealist (read: hipster5) for my own good? How does everyone else handle this?

1. When I say “politics” in this article, I specifically mean USA politics. Not because I think it more important, or because I like it better, but simply because I am far more familiar with it than other countries’ politics. Perhaps what is written here is more widely applicable, or perhaps not. But I feel that this is a useful bit of context to have here.

2. An engineer’s dream is to be told “You can tear this all down and start over from scratch with no strings attached, and design it in exactly the way you feel best.” Legacy solutions are often kludgy and inelegant, and large-scale examples of clean, elegant engineering are sadly rare due to the fact that they go from small and clean, to large and patched, because a) it’s really really hard to design systems which scale cleanly, and b) requirements change over time. In my terribly humble opinion, this particularly goes for bureaucracies6. But it is just that — a base. And what we have currently built on it is, in fact, very flawed in a variety of ways7

3. Take, for example, the question, “Have you stopped beating your wife?” (This is actually the traditional example!) Of course, you’ve never beaten your wife, so both “yes” and “no” are incorrect answers. Yet any other response does not answer the question, since it is a yes-no question. Therefore, one might suggest that the question itself is wrong, rather than any of the answers. You might therefore “unask” the question. Most people will do this implicitly by saying something like “I never started.” Explicitly unasking the question names the problem so it can be discussed. I first ran into the concept discussed philosophically in the context of Zen Buddhism as discussed in Hofstadter’s GEB8. In one chapter, he discusses the idea of mu — a response which unambiguously indicates that the question was faulty. (One of my favourite things about being in the Honors program at Uni is that I can respond to a question with “mu” and not always get a funny look back.)

4. Is it?

5. It has been asserted (I use the passive voice intentionally) that the word I should use here is not “idealist”, but “hipster”. This is because I used the word “metadiscussion” once, and apparently only hipsters can use “meta”. However, that is a rant for another day.

6. Sad but true: I can’t spell “bureau” or anything derived from it without looking it up in a dictionary/spellchecker.

7. Trendy things to rant about as flawed: patent law, copyright law, social security, tax law, lobbying, campaigns, effectively over-strong executive branch, federal government is too strong, federal government is too weak, and any number of other things which are not the point.

8. Hofstadter, Douglas. Gödel, Escher, Bach. New York: Basic Books, 1979.

## Excerpt from “The Everlasting Man”

by on 1 September 2012
under , , , ,

A man did not stand up and say ‘I believe in Jupiter and Juno and Neptune,’ etc., as he stands up and says ‘I believe in God the Father Almighty’ and the rest of the Apostles’ Creed. Many believed in some and not the others, or more in some and less in others, or only in a very vague poetical sense in any. There was no moment when they were all collected into an orthodox order which men would fight and be tortured to keep intact. Still less did anybody ever say in that fashion: ‘I believe in Odin and Thor and Freya,’ for outside Olympus even the Olympian order grows cloudy and chaotic. It seems clear to me that Thor was not a god at all but a hero. Nothing resembling a religion would picture anything resembling a god as groping like a pigmy in a great cavern, that turned out to be the glove of a giant. That is the glorious ignorance called adventure. Thor may have been a great adventurer; but to call him a god is like trying to compare Jehovah with Jack and the Beanstalk. … Polytheism fades away at its fringes into fairy-tales or barbaric memories; it is not a thing like monotheism as held by serious monotheists. … Finally it did satisfy, or rather it partially satisfied, a thing very deep in humanity indeed; the idea of surrendering something as the portion of the unknown powers; of pouring out wine upon the ground, of throwing a ring into the sea; in a word, of sacrifice.

The Everlasting Man, by G. K. Chesterton. From “V. Man and Mythologies”, which is rapidly becoming my favourite chapter in the entire book. I had to resist the urge to quote more.

EDIT: On the next page:

Certainly the pagan does not disbelieve like an atheist, any more than he believes like a Christian. He feels the presence of powers about which he guesses and invents. St. Paul said that the Greeks had one altar to an unknown god. But in truth all their gods were unknown gods. And the real break in history did come when St. Paul declared to them whom they had ignorantly worshipped.

by on 22 August 2012
under , ,

A clarification regarding my use of the word “simple(ish)”: I am assuming, firstly, that you are already comfortable with programming in an imperative language such as C, Java, or Python, and secondly, that you already know at least a little Haskell.

Haskell type signatures, to the uninitiated, are a little odd. Take the following simple two-argument function:

plus :: Int -> Int -> Int
plus a b = a + b


If you’re coming from an imperative language, you might be tempted to read that signature as “this function takes an Int and an Int and returns an Int”. That’ll do in most cases, but it isn’t really true. And the fact that it isn’t true is a really cool feature of Haskell.

The little -> arrow is a right-associative operator. So you whould read Int -> Int -> Int as Int -> (Int -> Int), which doesn’t help anything at all, because now it looks even worse. And now here is the kicker: all functions in Haskell take exactly one argument. One. Even our plus function there. Which is odd, because it sure looks like it takes two arguments. The thing is, Haskell does a little magic trick for us (which isn’t really magic). This magic is called currying.

The trick is that when you do plus 2 3, two things happen. First, 2 is applied to plus. Application is a fancy way of saying that an argument is given to a function. This application results in a new function, which also takes one argument. 3 is applied to that function, which one might notate as (plus 2), and returns an Int, 5.

In short, plus 2 3 is the same as (plus 2) 3. So the Int -> (Int -> Int) means that plus is a function which takes an Int, returning a function which takes an Int, returning an Int.

So why is that useful? Well, consider the builtin function map, which has the signature:

map :: (a -> b) -> [a] -> [b]


Basically, it takes a function which takes a thing of type a and returns a thing of type b, and an array of things of type a. It then spits out an array of things of type b, which is generated by applying the function to every argument the array of things of type a.

So map (\b -> plus 2 b) [3 1 4 1 6] returns [5 3 6 3 8].

Now, remember that (plus 2) returns a function, right? So you could also do:

map (plus 2) [3 1 4 1 6]


and get the same result.

tl;dr: Calling a Haskell function with not enough arguments basically returns what you might think of as a half-called function. It’s got some arguments already, you just need to supply the remaining ones. And it’s just another function.