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.


The High School Solar Car Challenge: some physics

This year I am covering the (High School) Solar Car Challenge, as well as the upcoming university competitions. The high school event will take place at the Texas Motor Speedway on July 15–22 (with Covid protocols in place), and will be live-streamed via the event’s YouTube channel. Today I want to say something about high school solar cars in comparison to world-class cars.

 
Left: Cougar Spirit from Covenant Christian Academy is a high school car in the Advanced Classic Division / Right: Nuna11 is a world-class car from Delft University of Technology in the Netherlands (picture by @lightatwork)

The two main drag forces operating on cars are rolling resistance and aerodynamic drag. The former is indicated in the chart below by red lines. It is a function of the product of the rolling resistance Crr of the tyres times the mass M of the car in kilograms.

The aerodynamic drag is indicated in the chart below by blue lines. It is a function of the product of the drag coefficient Cd of the body shape, the frontal area A of the car in square metres, and the square of the velocity.

The chart at the bottom of the page expresses the same information in terms of the power (in watts) required to overcome drag at various speeds.

At the world-class level, where special low-rolling-resistance tyres are available and cars glide through the air like a hot knife through butter (low values of Crr M and Cd A), the aerodynamic drag is much greater than the rolling resistance at race speeds, and shaving a few percent off the Cd A value becomes critical to winning. At high school level, with cars that students can afford and racing speeds from 15 to 50 km/h (10 to 30 mph), aerodynamic drag and rolling resistance are roughly similar, and reducing the weight of the car becomes especially important. Some of the high school classes do not permit hub motors, and for those cars, reducing drive train losses is also critical.

A few high school cars in the Advanced Division are both under 200 kg and quite aerodynamic this year (e.g. Invictus from the Iron Lions and Lumidos from Oregon Solar Car Team), so it will be very interesting to see how they perform.


Some knots

I have been reading up on knots recently, so here is a table of 8 knots with up to 6 crossings (plus 2 extras), along with their Conway polynomials. These are polynomials that can be associated with each knot. Different polynomials imply different knots, but sometimes different knots have the same polynomial. Some examples are shown in red below. I have also included pictures of the ten knots mentioned (not drawn by me).

Knot Conway polynomial
01 (Unknot) 1
31 (Trefoil knot) z2 + 1
41 (Figure-eight knot) 1 − z2
51 (Cinquefoil knot) z4 + 3 z2 + 1
52 (Three-twist knot) 2 z2 + 1
61 (Stevedore’s knot) 1 − 2 z2
62 (Miller Institute knot)  − z4 − z2 + 1
63 z4 + z2 + 1
946 1 − 2 z2
10132 z4 + 3 z2 + 1


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.


2 + 2 = 4 and mathematical models

One of the strangest aspects of 2020 was a number of people arguing that 2 + 2 = 4 wasn’t necessarily true, and that it might be the case that 2 + 2 = 5. In fact, 2 + 2 = 4 is not only true throughout the universe, it is true in every possible alternate universe as well. A great many silly arguments were made by people trying to defend 2 + 2 = 5. But there is a deeper response here that relates to how applied mathematics works, and a few people have been trying to express that.

In general, applied mathematics questions have the form A → B, where A is some real-world situation, and B our desired but unknown answer. We abstract our real-world situation A to the mathematical object X, so that X → Y is the mathematical analogue of our real-world A → B. Mathematical questions have clearly-defined answers (although finding them is not always easy). We can then take our mathematical answer Y and reverse-translate it to the real world, giving something that we claim is a good approximation to B.

In the mathematical world of X and Y, everything is crisp and clear (and 2 + 2 = 4). In the real world, things are messy and ill-defined. Furthermore, in going from A to X we introduce simplifications and approximations which may mean that the mathematical answer Y is not “fit for purpose.”

For example, our real-world question might be “what is the distance from Melbourne to Sydney?” There are three ambiguities here: What is “Melbourne”? What is “Sydney”? And what is “distance”?

The conventional location marker for the city of Melbourne, Australia is the Old Melbourne General Post Office (now a shopping centre, at 37°48′49″S, 144°57′48″E). Likewise, the conventional location marker for the city of Sydney is the Sydney General Post Office (at 33°52′4″S, 151°12′27″E). Let’s use those coordinates. But what is “distance”? If “distance” means “as the crow flies,” then a simple answer might be to find the great-circle distance on a sphere approximating the Earth (let’s use the equatorial radius of 6,378.137 km). This distance can be calculated fairly easily as 714.2 km, which might be a close enough answer for many purposes.

A better mathematical model might be distance on the WGS reference ellipsoid model of the Earth. This gives the slightly lower value 713.8 km (according to Google Earth or raster::pointDistance).

Alternatively, “distance” might mean “by road,” in which case we need a computer representation of Australia’s road network. For this question, Google Maps reports a distance of 878 km via the M31. The expected travel time by car (9 hours and 7 minutes when I looked) might be even more useful.

It may therefore be the case that out of various mathematical answers Y, many are not “what you wanted.” But that failure to abstract correctly does not invalidate the mathematical truths involved in X → Y. In particular, it does not invalidate 2 + 2 = 4. It just means that you picked up the beautiful crystal knife of mathematics and cut yourself with it.

As Korzybski liked to say, “the map is not the territory.”


No, it is not true that 2 + 2 = 5

The year 2020 was an unusual year. One of the strangest aspects was a number of people arguing that 2 + 2 = 4 wasn’t necessarily true, and that it might be the case that 2 + 2 = 5. This is an idea that had been mentioned by George Orwell in his dystopic novel 1984:

All rulers in all ages have tried to impose a false view of the world upon their followers, but they could not afford to encourage any illusion that tended to impair military efficiency. So long as defeat meant the loss of independence, or some other result generally held to be undesirable, the precautions against defeat had to be serious. Physical facts could not be ignored. In philosophy, or religion, or ethics, or politics, two and two might make five, but when one was designing a gun or an aeroplane they had to make four. Inefficient nations were always conquered sooner or later, and the struggle for efficiency was inimical to illusions.

In fact, 2 + 2 = 4 is true regardless of your culture or your skin colour (although you might represent the fact using an alternate set of symbols, like  +  = ). If there are aliens out there, it is true for them too. What’s more, 2 + 2 = 4 is true in every possible alternate universe as well as in this one.

Some defenders of 2 + 2 = 5 have appealed to modular arithmetic, and (to take one example) modulo 3 we have 2 = { −1, 2, 5, … } and 1 = { −2, 1, 4, … }, using overbars to distinguish congruence classes from integers (in order to be precise). Consequently, 2 + 2 = 4 = 1. However, we never get 2 + 2 = 5 in such systems, other than in the trivial case where all integers are equivalent (the proof of this is actually quite straightforward). We certainly do not get 2 + 2 = 5.


All about fixed points

In mathematics, a fixed point of a function f is a value x such that f(x) = x. For example, Wolfram notes that cos(0.7390851332) = 0.7390851332. There need not be such a fixed point, of course, but it is interesting when there is.

Unique fixed points

The Banach fixed-point theorem applies to complete metric spaces – sets where there is a concept of distance and where convergent sequences have a limit.

If f is a function that shrinks things – if, say, the distance between f(x) and f(y) is at most 50%, or 90%, or 99.99999% of the distance between x and y – then the function f will not only have a fixed point, but that fixed point will be unique.

Intuitively, this is clear. You apply the function f to the whole set an infinite number of times, and everything shrinks down to a single point satisfying f(x) = x.


Comic 688 by xkcd, with the fixed point highlighted in pink

It follows that if you stand inside a country, city, or home holding (horizontally) a map of that country, city, or home, then exactly one point in the country, city, or home is exactly underneath the corresponding point on the map. More usefully, this theorem has been used to assign meaning to recursive type expressions in computer science.

Iterated function systems

Iterated function systems are one way of defining fractals. An iterated function system is a family of functions, each of which shrinks things (i.e. is contractive). This family of functions defines a Hutchinson operator on sets of points, and that operator is in turn contractive for a certain definition of distance between sets (see Hutchinson, 1981).

Consequently, that operator has a unique “fixed point,” which is in fact a set of points, like the famous Barnsley fern. The set of points can be (approximately) generated by an iterative process (see code example here):

Least fixed points

As another example of fixed points in action, the Kleene fixed-point theorem assigns meaning to recursively defined computer programs, like these:

  • x = x, a circular definition which is satisfied by infinitely many things, defines x = ⊥, the least defined of all those things
  • z = 0 ⊙ (1 + z), where “” means putting a number in front of a list, defines the infinite list z = 0, 1, 2, 3, 4, 5, …
  • g = function (x) { if (x = 0) then 1 else x * g(x − 1) }, defines g to be the factorial function

Computer programs are modelled by Scott-continuous functions on a partial order where ⊥ is the least element (⊥ means “no information” and is the meaning of any computer program stuck in an infinite loop). Scott-continuous functions may have more than one fixed point, but they have a unique least fixed point, which is the limit of the sequence ⊥ ⊑ f(⊥) ⊑ f(f(⊥)) ⊑ …

This sequence corresponds to what actually happens when the computer attempts to execute recursive definitions like the three in red above.

Brouwer’s fixed point theorem

Even more interesting is Brouwer’s fixed-point theorem. Any continuous function mapping a compact convex set to itself has at least one fixed point.

This is hard to prove in general, though easy to see in the case that the set is simply the interval [0, 1]. We have f(0) − 0 ≥ 0 and f(1) − 1 ≤ 0, so that f(x) − x = 0 for at least one x in the range 0 to 1:

An implication is that, when I stir my cup of coffee, at least one speck of liquid winds up exactly where it started.

Fixed points and dynamics

If the function f represents a state transition function, then a fixed point corresponds to a state that remains the same over time. For example, the logistic mapx (1 − x) has fixed points 0 and 0.75. However, these are both unstable – if you start out close to them, repeated application of the function takes you further away:

  • 0.000001, 0.000004, 0.000016, 0.000064, 0.000256, 0.001024, 0.00409, 0.016295, 0.064117, 0.240023, 0.729649, 0.789046, 0.66581, 0.890028, 0.391511, 0.952921, 0.179452, 0.588995, 0.96832, 0.122706, 0.430598, …
  • 0.749999, 0.750002, 0.749996, 0.750008, 0.749984, 0.750032, 0.749936, 0.750128, 0.749744, 0.750512, 0.748975, 0.752045, 0.745893, 0.758147, 0.733441, 0.782021, 0.681856, 0.867713, 0.459147, 0.993324, 0.026525, …

On the other hand, the logistic map 2.5 x (1 − x) has a stable fixed point (an attractor) at 0.6. Starting at, say, 0.5, repeatedly applying the function gets you closer and closer to 0.6:

  • 0.5, 0.625, 0.585938, 0.606537, 0.596625, 0.601659, 0.599164, 0.600416, 0.599791, 0.600104, 0.599948, 0.600026, 0.599987, 0.600007, 0.599997, 0.600002, 0.599999, 0.6, 0.6, 0.6, 0.6, …

Fixed points are everywhere! Not only that, but the concept is a fruitful one in a diverse collection of fields. For more on fixed points, see this book (available electronically here).