Fast Fibonacci numbers

There was some discussion on reddit recently of the Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1,597, 2,584, 4,181, 6,765, 10,946, 17,711, 28,657, 46,368, 75,025, 121,393, 196,418, 317,811, 514,229, 832,040, …) and efficient ways of calculating them.

One way of doing so is using numbers of the form a + b σ where  σ is the square root of 5. Multiplication of such numbers satisfies:

(a + b σ) × (c + d σ) = ac + 5bd + (ad + bc) σ.

We can define the golden ratio φ = (1 + σ) / 2 and also ψ = 1 − φ = (1 − σ) / 2, in which case the nth Fibonacci number Fn will be exactly (φn − ψn) / σ. This is known as Binet’s formula.

We can use this formula to calculate Fibonacci numbers using only integer arithmetic, without ever evaluating the σ. We will have:

(2 φ)n − (2 ψ)n = (1 + σ)n − (1 − σ)n = 0 + p σ

for some integer p, and division by a power of two will give Fn = p / 2n.

I am using the R language, with the gmp package, which provides support for large integer matrices, and this allows us to use the relationship:

If we call this matrix A and calculate An−1, the first number in the resultant matrix will be the nth Fibonacci number Fn. The following R code calculates F10 = 55 using a combination of multiplication and squaring:

n <- 10

A <- matrix.bigz(c(
	1, 1,
	1, 0), 2)

p <- function(n) {
	if (n == 1) A
	else if (n %% 2 == 1) A %*% p(n-1)
	else {
		b <- p(n/2)
		b %*% b
	}
}

p(n-1)[1,1]

This same code will calculate, for example:

The time taken to calculate Fn is approximately proportional to n1.156, with the case of n = 1,000,000,000 (giving a number with 208,987,640 digits) taking about a minute.


Rods and cones in the human eye

I already posted these images (click to zoom) on Instagram. They illustrate the sensitivity to colour of the rods (lower right) and the three types of cones in the human eye. Cone sensitivity data is from CVRL.

Notice that red light is pretty much invisible to the rods. This is why red light does not interfere with night vision, and is used in e.g. this aircraft cockpit:


The pancake theorem

A previous post mentioned the Borsuk–Ulam theorem. A corollary (for the case of a circle) is the pancake theorem: given two plane regions, there is a cut (line) which divides both in half by area.

The example shows a cut dividing both South America and Africa in half (the theorem doesn’t tell us how to find the cut; I used simulated annealing).

The corollary for the 2-sphere is the ham sandwich theorem: given three 3-dimensional objects, there is a cut (plane) which divides all three in half by volume.


The Borsuk–Ulam theorem

The mathematical tidbit for today is the Borsuk–Ulam theorem, which states that every continuous function f from the n-dimensional sphere to n-dimensional space must satisfy f(p) = f(−p) for some point p.

In particular, every continuous function f from a 2-dimensional sphere (say, the Earth’s surface) to the plane must satisfy f(p) = f(q) for some antipodal pair of points p and q.

Thus, if we can describe weather by a pair of numbers (say, temperature and rainfall), there must be an antipodal pair of points p and q with the same weather (because two numbers specify a point in the plane).

The maps above (for average maximum temperature) and below (for rainfall) show July weather at various places on Earth, and a pair of points with the same weather is highlighted.

It’s a miracle that it works in this case, of course, because the maps only define temperature and rainfall on the land; I would not have been able to recognise a suitable antipodal pair of points if one or both were at sea.


The Projective Plane

I have been thinking some more about the famous Möbius strip (see also my post on the Klein bottle). The so-called “Sudanese Möbius Band” in the video above is a Möbius strip stretched so as to make the boundary perfectly circular (it is not named after the country, but after the topologists Sue E. Goodman and Daniel Asimov, and you can purchase a plastic one here).

If we glue two of these Möbius strips together (not actually possible in 3 dimensions), we get a Klein bottle. If we glue one to a disc (also not possible in 3 dimensions), we get a projective plane.

Just for fun, the video below shows a Game of Life glider on the projective plane. The top and bottom of the square are considered to be joined, as are the left and right sides. In both cases, there is a reversal of orientation (a manoeuvre not really possible in 3 dimensions). The glider changes colour as it changes orientation.

Video produced using the R animation package.


The Klein Bottle

I have been thinking about the famous Klein bottle (above). To quote a limerick by Leo Moser:

A mathematician named Klein
Thought the Möbius band was divine.
Said he: “If you glue
The edges of two,
You’ll get a weird bottle like mine.”

Just for fun, here is a Game of Life glider on a Klein bottle. The top and bottom of the square are considered to be joined, so as to form a tube. The ends of the tube (vertical sides of the square) are also joined, but with a reversal of orientation (a manoeuvre not really possible in three dimensions). The glider changes colour as it changes orientation.

Video produced using the R animation package.


A Narnian Timeline

I’ve been on a bit of a Narnia binge recently. Continuing that theme, here is a timeline of the Chronicles of Narnia (click to zoom). The Terran time axis has varying scales (although piecewise linear), since 5 of the 7 Narnia books (53% of Narnian history) are set during 1940–1942. For simplicity, I also assume a piecewise linear mapping of Narnian time to Terran time (see graph below), although the text of the books indicate that the mapping is more complex than that. For Narnian events in the chart, only the vertical position has meaning (the sideways curve is only there to create space).

The Crucifixion of Jesus is included as a significant Terran event, since its Narnian parallel is the key event of The Lion, the Witch and the Wardrobe. Some scholars date this to the year 30, rather than 33.

The chart was produced using R. The curved lines are plotted with colours from colorRampPalette(). Images were added using png::readPNG, as.raster(), and rasterImage(), with circles using plotrix::draw.circle(). For the title, the extrafont package was used.


Topic Analysis on the New Testament

I have been experimenting recently with Latent Dirichlet allocation for automatic determination of topics in documents. This is a popular technique, although it works better for some kinds of document than for others. Above (click to zoom) is a topic matrix for the Greek New Testament (using the stemmed 1904 Nestle text, removing 47 common words before analysis, and specifying 14 as the number of topics in advance). The size of the coloured dots in the matrix shows the degree to which a given topic can be found in a given book. The topics (and the most important words associated with them) are:

A better set of topics can probably be obtained with a bit more experimentation. Alternatively, here (as a simpler form of analysis) are the relative frequencies of some Greek words or sets of words, scaled to the range 0 to 1 for each word set (with the bar chart showing the total number of words in each New Testament book). Not surprisingly, angels appear more frequently in Revelation than anywhere else, while love is particularly frequent in 1 John:


World Population

Some feedback on my last post expressed surprise that Ptolemy’s specification of the Oikoumene now holds holds 80.6% of the world’s population. Above (click to zoom), I have redrawn the classic bar charts of world population which explain this fact. Africa, Asia, and Europe contain about 86% of the world’s population. Ptolemy excluded what we now know to be Southern Africa (which only drops the total to 85%) and didn’t extend his Oikoumene quite far enough to the east.

The chart below shows the same thing, but using NASA’s image of the Earth at night. It can be seen that the spikes on the bar chart correspond to major cities.


The Oikoumene of Ptolemy

I was reading recently about the Geographia of Ptolemy (written around 150 AD). This classic book applied Greek mathematical skills to mapping and map projection – and if there was one thing the Greeks were good at, it was mathematics. According to Neugebauer, Ptolemy believed the Oikoumene, the inhabited portion of the world, to range from Thule (63° North) to 16°25′ South, and 90 degrees East and West of Syene in Egypt.

The map above illustrates this Oikoumene, with a modern population overlay in red (data from SEDAC). Ptolemy was not too far wrong – today this region holds 80.6% of the world’s population, and the percentage would have been greater in antiquity.

Also shown on the map are some of the many cities listed in the Geographia. Open circles show Ptolemy’s coordinates (from here, adjusted to a Syene meridian), and filled circles show true positions. Ptolemy had reasonably good latitude values (an average error of 1.2° for the sample shown on the map), but much worse longitude values (an average error of 6.8°). The longitude error is mostly systemic – Ptolemy’s estimate of 18,000 miles or 29,000 km for the circumference of the earth was only 72% of the true value (several centuries earlier, Eratosthenes had come up with a much better estimate). If Ptolemy’s longitudes are adjusted for this, the average error is only 1.5°.

However, Ptolemy’s book deserves considerable respect – it is not surprising that it was used for more than a thousand years.