“Your monkey did not jump high enough”

Yesterday, in Futility Closet there was a post:

In Longfellow’s novel Kavanagh, Mr. Churchill reads a word problem to his wife:

“In a lake the bud of a water-lily was observed, one span above the water, and when moved by the gentle breeze, it sunk in the water at two cubits’ distance. Required the depth of the water.”

“That is charming, but must be very difficult,” she says. “I could not answer it.”

Is it? If a span is 9 inches and a cubit is 18 inches, how deep is the water?

The problem is simple enough: if the depth of the water is x inches so that the lotus from bottom to tip is x+9 inches, then x²+36²=(x+9)², which means x=(36²-9²)/18=135/2=67.5.

More interestingly, as I accidentally recognised (I don’t know how), it is from the Sanskrit mathematics text Lilavati (and also found in the Bījagaṇita) of Bhaskaracharya (Bhaskara II). That entire chapter of Kavanagh is essentially quoting the Lilavati (Kavanagh is written in a somewhat embarrassing tone that perhaps explains why it’s so obscure :p); it’s included later below the horizontal line in this post.

Bhaskaracharya, believed to have lived in the 12th century, is considered the last great Indian mathematician, outside of the Kerala school. Like most Sanskrit texts, the Līlāvati is written in verse, so as to be easier to memorise. Unlike many Sanskrit technical works (or for that matter technical works in any language), however, Bhāskara’s works are not written in the typical dry style, and can veer quite poetic at times. His description of the seasons in one of his astronomical works is one of the few true instances of poetry in the Sanskrit astronomical/mathematical corpus. This particular problem, it happens, is written in the beautiful mandākrānta metre: (If it helps: mandakranta is the metre of the Meghadūta, of “शान्ताकारं भुजगशयनं…”, of “नास्था धर्मे न वसुनिचये…”, etc., and you can listen to a recitation in the Marathi tradition by Ashwini Deo.)

चक्रक्रौञ्चाकुलितसलिले क्वापि दृष्टं तडागे
तोयादूर्ध्वं कमलकलिकाग्रं वितस्तिप्रमाणम्
मन्दं मन्दं चलितमनिलेनाऽऽहतं हस्तयुग्मे
तस्मिन्मग्नं गणक कथय क्षिप्रमम्बुप्रमाणम्

cakra-krauñcākulita-salile kvāpi dṛṣṭaṃ taḍāge
toyād ūrdhvaṃ kamala-kalikāgraṃ vitasti-pramāṇam
mandaṃ mandaṃ calitam anilenāhataṃ hasta-yugme
tasmin magnaṃ gaṇaka kathaya kṣipram ambu-pramāṇam

In a certain lake swarming with geese and cranes,
the tip of a bud of lotus was seen one span above the water.
Forced by the wind, it gradually moved, and was submerged at a distance of two cubits.
O mathematician, tell quickly the depth of the water.

Well, that’s my translation, close to Longfellow’s quoted translation by Taylor and to Colebrooke’s better translation, but I may be wrong, so details for anyone who cares to improve it:

In a certain [kvāpi] pool [taḍāge] whose water [salile] was swarming [ākulita] with ruddy geese [cakra] and curlews [krauñcā],
above the water [toyād ūrdhvaṃ] a lotus-bud-tip [kamala-kalikāgraṃ] at a distance of one span [vitasti-pramāṇam] was seen [dṛṣṭaṃ].
Slowly slowly [mandaṃ mandaṃ] by the wind [anilena] moved [calitam] and forced [āhataṃ],
at a distance of two cubits [hasta-yugme] it got submerged [magnaṃ] in the water [tasmin].
O mathematician [gaṇaka], say [kathaya] quickly [kṣipram] the depth of the water [ambu-pramāṇam].

The structure of the book may be worth remarking on: the general formula for exactly this problem is given first (in more technical terms), and then this problem is given as an example!

Glancing through Longfellow, one finds he’s also written a tiny poem called King Trisanku:

Viswamitra the Magician,
By his spells and incantations,
Up to Indra’s realms elysian
Raised Trisanku, king of nations.

Indra and the gods offended
Hurled him downward, and descending
In the air he hung suspended,
With these equal powers contending.

Thus by aspirations lifted,
By misgivings downward driven,
Human hearts are tossed and drifted
Midway between earth and heaven.

Ho hum (1845 America).

The chapter of Kavanagh below this line.

---

Advertisement

People, Pens, Paper, and Computers

(A post from November 2008 that had been marked private for some reason.)

Attended a talk today that was part of the HCI (Human-Computer Interaction) Seminar Series at MIT CSAIL. Some very exciting stuff.

For several decades now (say, since the Xerox Star was introduced in 1981) there have been dreams and hype of the “paperless office”. This dream has not been realised, because paper has many great qualities that suggest that it is not going to go anywhere. In many ways, technologies that have been touted to replace paper have proved rather cumbersome. Somewhat like writing like this:

Pencil encumbered with brick

Some recent technologies that keep the dream alive are the Tablet PC and (new to me) the Anoto (etc.) digital pens that work in conjunction with digital paper (just normal paper printed with a pattern, not “electronic paper”). I played for a few seconds with Livescribe‘s “Pulse Smartpen”, but it was after the talk so I didn’t have much time. Here is a video of all that it can do.

People prefer paper. There have been two lines of work — trying to produce paper-like technology and trying to improve integration between paper and the PC.

I guess both the tablet PC and Livescribe-like technologies fall into the former category. For the Tablet PC, he described a model of interaction that (with a pen) is more natural than the point-and-click model: crossing. The idea is that instead of actions being performed when a target on the screen is clicked upon, actions are performed when targets are crossed across. It is claimed that crossing-based interface is at least as fast as point-and-click, and is faster when you require only “approximate” crossing, and it is possible to change all your applications to work with crossing instead by simply changing a system DLL. He showed a crossing-based drawing application called CrossY; see the video.

Then he showed another work called PapierCraft, which fits into the other line of work. The insight is that although people prefer to read and annotate on paper, they usually get them in digital form. The common example is that academics download an article, then print it out, and work with the printed copy, making annotations etc. The idea is to keep in a database an image of what the printed copy looks like, and then consider people to be working on the digital copy with the printed copy as a proxy for it — when they perform annotations, cut-copy-paste etc., link those operations to the digital copy. See video.

He also showed some two-display e-book readers that can emulate flipping pages, working with different documents, etc; see video.

The speaker was François Guimbretière; see his page for more details. All very cool stuff.

New Year

Some time in the last two weeks, I tried to figure out the answers to two questions:

1. Why does the new year begin on January 1?
2. Why does January 1 occur when it does?

That is, the history of the calendar. The former question is about the structure of the calendar, and the latter about its (arbitrary) point of origin.

I don’t have definitive answers yet (and I’m beginning to wonder if any exist); please help me if you know something.

Meanwhile, here’s what I’ve been able to piece together from reading Wikipedia. The calendar most of us use most of the time can be understood in three phases…

Phase I: The (pre-Julian) Roman calendar: before 45 BCE

The Greeks used several lunar calendars. The Romans probably inherited such a calendar, and their early calendar was a lunar one. “According to Livy, Numa’s calendar was lunisolar with lunar months and several intercalary months spread over nineteen years so that the Sun returned in the twentieth year to the same position it had in the first year.”

According to Roman tradition, Rome was founded around 753 BCE by Romulus, and Romulus “invented” the following calendar:

    Calendar of Romulus
Martius                 (31 days)
Aprilis                 (30 days)
Maius                   (31 days)
Iunius                  (30 days)
Quintilis               (31 days)
Sextilis                (30 days)
September               (30 days)
October                 (31 days)
November                (30 days)
December                (30 days)  [Total 304 days]
"Winter"                (About 61 days of winter, presumably)

Note that the names for months 5 to 10 (Quintilis to December) are just number names.

The arbitrariness of this calendar already makes no sense, but let’s start with it. We have to start somewhere.

In 713 BCE, Numa divided the winter into two months named Ianuarius and Februarius. Also, to make all the month lengths odd (considered lucky), he took away one day from each of the 30-day months.

Martius                 (31)
Aprilis                 (29)
Maius                   (31)
Iunius                  (29)
Quintilis               (31)
Sextilis                (29)
September               (29)
October                 (31)
November                (29)
December                (29)
Ianuarius               (29)	
Februarius              (28) [Total 355 days]

[Apparently by 450 BCE, the civil calendar had also been changed to start with Ianuarius, so half the month names became misnomers. So here’s where the answer to the first question should come from: why was the calendar changed to start with January/Ianuarius instead of March/Martius?]

February was actually two parts of odd number of days each: Part 1, 23 days, ended with Terminalia (and so did the religious year), and then there was a remaining part of 5 days. From time to time, an intercalary month of 27 days (subsuming the last 5, so only 22 additional days) was added. (So the leap year had 377 or 378 days.) So far the months were still more or less lunar, it appears.

Because the true length of a year is roughly halfway between 355 and 377, the intercalary month was needed roughly every alternate year. Adding the intercalary month was left to the Pontifex Maximus, a pontiff in charge of such things.

However, since the Pontifices were often politicians, and because a Roman magistrate’s term of office corresponded with a calendar year, this power was prone to abuse: a Pontifex could lengthen a year in which he or one of his political allies was in office, or refuse to lengthen one in which his opponents were in power. If too many intercalations were omitted, as happened after the Second Punic War and during the Civil Wars, the calendar would drift rapidly out of alignment with the tropical year. Moreover, because intercalations were often determined quite late, the average Roman citizen often did not know the date, particularly if he were some distance from the city. For these reasons, the last years of the pre-Julian calendar were later known as “years of confusion”. The problems became particularly acute during the years of Julius Caesar’s pontificate before the reform, 63–46 BC, when there were only five intercalary months, whereas there should have been eight, and none at all during the five Roman years before 46 BC. For example, Caesar crossed the Rubicon on January 10, 49 BC of the official calendar, but the official calendar had drifted so far away from the seasons that it was actually mid-autumn.

Whoa.

Eventually Julius Caesar became Pontifex Maximus, and reformed the calendar into the Julian calendar in 45 BCE. “The reform was intended to correct [the above] problem permanently, by creating a calendar that remained aligned to the sun without any human intervention.”

Phase II: the Julian calendar (45 BCE to some time after 1582 CE)

The Julian Calendar: Eventually Julius Caesar became Pontifex Maximus, and in 45 BCE, “called in the best philosophers and mathematicians of his time” and reformed the calendar into the Julian calendar. He decided to approximate the tropical year, and so it became a calendar of 365 days with a leap year added to February (still the last month of the religious calendar?) every four years. So a year became exactly 365.25 days on average.

Somewhere here is where one should look for the answer to the second question: what about the start of the year?

“A passage in Macrobius has been interpreted to mean that Caesar decreed that the first day of the new calendar began with the new moon which fell on the night of 1/2 January 45 BC. However, more recent studies of the manuscripts have shown that the word on which this is based, which was formerly read as lunam, should be read as linam, meaning that Macrobius was simply stating that Caesar published an edict giving the revised calendar.”

Ah, if the new moon explanation were correct, it would have answered the second question! So close.

In any case, this wasn’t the end. “the pontifices apparently misunderstood the algorithm for leap years. They added a leap day every three years, instead of every four years. […] After 36 years, this resulted in three too many leap days. Augustus remedied this discrepancy by restoring the correct frequency. He also skipped three leap days in order to realign the year. Once this reform was complete—after AD 8 at the latest—the Roman calendar was the same as the Julian proleptic calendar.”

Ah, finally! The year is fixed. Sort of.

The solstices and the equinoxes were now: 25 December, 25 March, 24 June, 24 September.

Quintilis was renamed Iulius after Iulius Caesar, and Sextilis was renamed Augustus after his successor Augustus Caesar. (Incidentally, these were not the only months to be renamed, just the only renamings to survive: “Caligula renamed September (“seventh month”) as Germanicus; Nero renamed Aprilis (April) as Neroneus, Maius (May) as Claudius and Iunius (June) as Germanicus; and Domitian renamed September as Germanicus and October (“eighth month”) as Domitianus. At other times, September was also renamed as Antoninus and Tacitus, and November (“ninth month”) was renamed as Faustina and Romanus. Commodus was unique in renaming all twelve months after his own adopted names […]” So apparently the trick in getting a month named after you is to do the renaming when the calendar is in flux, not after it’s been fixed.

Phase III: the Gregorian calendar: a few years after 1582 to today

The Gregorian calendar is what we use today, more or less.

The Julian calendar’s average of 365.25 days a year instead of about 365.2425 days a year is about 11 minutes extra each year, or about 3 days extra every 4 centuries. So the year had drifted, which had to be corrected, and in future, 3 leap days had to be removed every 4 centuries. Pope Gregory decreed this in 1582, though it took many countries a few centuries to take (or be forced to take) him seriously. This explains the “century years are not leap years unless divisible by 400” rule. Of course, Gregory’s calculation also wasn’t entirely perfect, but it’s handled nowadays by adding leap seconds etc. to the official clocks, and most of us aren’t even aware of it. (This is a mess, which David Madore has written about here.) When the calendar was introduced, it also dropped 10 days, and those who switched centuries later had to drop 10/11/12/13 days.

That’s about all of the history I have time for right now…
(It seems the answer to starting on 1 January may have something to do with some consul’s decision on when to start; the 2nd question is harder.)

Bonus: Why Christmas is on December 25th. The popular explanation is that it was a pagan winter-solstice festival that was appropriated, but according to some Christians, only the festival is pagan, not necessarily the date.

Not all best rational approximations are the convergents of the continued fraction!

[For more background on continued fractions and why they are so wonderful at approximations (and wonderful generally) — eventually I may edit this post to mention that. For now I just want to quickly clarify something, which surprisingly many popular expositions of continued fractions seem to mislead by leaving out.]

Any real number can be written as a continued fraction. For instance, the square root of 3 is

written as ,

and π is

i.e. (more terms below),

and e is (proved here).

Rational numbers have finite continued fractions, and irrational numbers have infinite continued fractions, of which only quadratic irrationals (like √3 above) have periodic continued fractions. Non-quadratic irrationals may still have some recognisable patterns in their representation, like e above, or not, like π.

The numbers you get by truncating the continued fraction — taking only the first few terms — are called its convergents. The continued fraction for π is [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2…] (sequence A001203 in OEIS), and the sequence of convergents is 3/1, 22/7, 333/106, 355/113, 103993/33102… (A002485/A002486):

Each of these convergents is a best rational approximation, in the following sense.

Definition: A fraction p/q is a best rational approximation of a real number x if p/q is closer to x than any other fraction with a smaller denominator. That is, for any other fraction with and , we have .

Thus among all fractions with denominator at most 7, the fraction 22/7 is closest to π. Among all fractions with denominator at most 113, the fraction 355/113 is closest to π. And so on.

Every convergent is a best rational approximation, but these aren’t all of the best rational approximations! The sequence of best approximations of π is actually 3/1, 13/4, 16/5, 19/6, 22/7, 179/57, 201/64, 223/71, 245/78, 267/85, 289/92, 311/99, 333/106, 355/113, 52163/16604… (A063674/A063673), where only the bold terms are convergents. (Aside: Notice how good 355/113 is: it is the best among all fractions with denominator at most 16603. This is because of the large term 292 in the continued fraction of π.) The others are semi-convergents (intermediate fractions), as explained below.

In general, for any real number, the convergents of its continued fraction are always best rational approximations, but they aren’t all of the best rational approximations. To get all of them, you also have to take the semi-convergents: fractions of the form for some integer n≥1. Specifically, taking — the next term in the continued fraction expansion — gives , and the ones to take are precisely from (if it’s better than the previous convergent, else ) to . This is also mentioned on Wikipedia.

Thus for π = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2…], the best rational approximations are:

3/1     = [3]

13/4    = [3; 4]
16/5    = [3; 5]
19/6    = [3; 6]
22/7    = [3; 7]

179/57  = [3; 7, 8]
201/64  = [3; 7, 9]
223/71  = [3; 7, 10]
245/78  = [3; 7, 11]
267/85  = [3; 7, 12]
289/92  = [3; 7, 13]
311/99  = [3; 7, 14]
333/106 = [3; 7, 15]

355/113 = [3; 7, 15, 1]

52163/16604  = [3; 7, 15, 1, 146]
52518/16717  = [3; 7, 15, 1, 147]
… (terms from [3; 7, 15, 1, 148] to [3; 7, 15, 1, 291])...
103993/33102 = [3; 7, 15, 1, 292]

104348/33215 = [3; 7, 15, 1, 292, 1]
...

The above is the natural meaning of “best rational approximation”. This is also known as “best rational approximation of the first kind”. There is a different definition of “best rational approximation” under which the convergents are precisely all the best rational approximations: basically, instead of considering the distance , we consider . That is: A fraction is a best approximation of the second kind of a real number if for every fraction with and , we have
This measure turns out to have a nicer theory, but to omit specifying that this non-obvious definition is the one being used is misleading.

Program

For illustration, here’s a C program (why it’s written in C is not important right now) that given a positive real number, generates its continued fraction, its convergents, and the sequence of best rational approximations. The function find_cf finds the continued fraction (putting the terms in a[] and the convergents in p[] and q[] — excuse the global variables), and the function all_best prints all the best rational approximations.

#include <math.h>
#include <stdio.h>
#include <assert.h>

// number of terms in continued fraction.
// 15 is the max without precision errors for M_PI
#define MAX 15
#define eps 1e-9

long p[MAX], q[MAX], a[MAX], len;
void find_cf(double x) {
  int i;
  //The first two convergents are 0/1 and 1/0
  p[0] = 0; q[0] = 1;
  p[1] = 1; q[1] = 0;
  //The rest of the convergents (and continued fraction)
  for(i=2; i<MAX; ++i) {
    a[i] = lrint(floor(x));
    p[i] = a[i]*p[i-1] + p[i-2];
    q[i] = a[i]*q[i-1] + q[i-2];
    printf("%ld:  %ld/%ld\n", a[i], p[i], q[i]);
    len = i;
    if(fabs(x-a[i])<eps) return;
    x = 1.0/(x - a[i]);
  }
}

void all_best(double x) {
  find_cf(x); printf("\n");
  int i, n; long cp, cq;
  for(i=2; i<len; ++i) {
    //Test n = a[i+1]/2 separately. Enough to test when a[i+1] is even, actually.
    n = a[i+1]/2; cp = n*p[i]+p[i-1]; cq = n*q[i]+q[i-1];
    if(fabs(x-(double)cp/cq) < fabs(x-(double)p[i]/q[i])) printf("%ld/%ld,", cp, cq);
    //And print all the rest, no need to test
    for(n = (a[i+1]+2)/2; n<=a[i+1]; ++n) {
      printf("%ld/%ld,", n*p[i]+p[i-1], n*q[i]+q[i-1]);
    }
  }
}

int main(int argc, char **argv) {
  double x;
  if(argc==1) { x = M_PI; } else { sscanf(argv[1], "%lf", &x); }
  assert(x>0); printf("%.15lf\n\n", x);
  all_best(x); printf("\n");
  return 0;
}

Examples

Here’s the output of this program, in about 0.003 seconds (i.e., it’s truly better than looping through all possible denominators!), line-wrapped for readability:

% ./a.out
3.141592653589793
 
3:  3/1
7:  22/7
15:  333/106
1:  355/113
292:  103993/33102
1:  104348/33215
1:  208341/66317
1:  312689/99532
2:  833719/265381
1:  1146408/364913
3:  4272943/1360120
1:  5419351/1725033
14:  80143857/25510582
 
13/4, 16/5, 19/6, 22/7, 179/57, 201/64, 223/71, 245/78, 267/85, 289/92, 311/99,
333/106, 355/113, 52163/16604, 52518/16717, 52873/16830, 53228/16943, 53583/17056,
53938/17169, 54293/17282, 54648/17395, 55003/17508, 55358/17621, 55713/17734,
56068/17847, 56423/17960, 56778/18073, 57133/18186, 57488/18299, 57843/18412,
58198/18525, 58553/18638, 58908/18751, 59263/18864, 59618/18977, 59973/19090,
60328/19203, 60683/19316, 61038/19429, 61393/19542, 61748/19655, 62103/19768,
62458/19881, 62813/19994, 63168/20107, 63523/20220, 63878/20333, 64233/20446,
64588/20559, 64943/20672, 65298/20785, 65653/20898, 66008/21011, 66363/21124,
66718/21237, 67073/21350, 67428/21463, 67783/21576, 68138/21689, 68493/21802,
68848/21915, 69203/22028, 69558/22141, 69913/22254, 70268/22367, 70623/22480,
70978/22593, 71333/22706, 71688/22819, 72043/22932, 72398/23045, 72753/23158,
73108/23271, 73463/23384, 73818/23497, 74173/23610, 74528/23723, 74883/23836,
75238/23949, 75593/24062, 75948/24175, 76303/24288, 76658/24401, 77013/24514,
77368/24627, 77723/24740, 78078/24853, 78433/24966, 78788/25079, 79143/25192,
79498/25305, 79853/25418, 80208/25531, 80563/25644, 80918/25757, 81273/25870,
81628/25983, 81983/26096, 82338/26209, 82693/26322, 83048/26435, 83403/26548,
83758/26661, 84113/26774, 84468/26887, 84823/27000, 85178/27113, 85533/27226,
85888/27339, 86243/27452, 86598/27565, 86953/27678, 87308/27791, 87663/27904,
88018/28017, 88373/28130, 88728/28243, 89083/28356, 89438/28469, 89793/28582,
90148/28695, 90503/28808, 90858/28921, 91213/29034, 91568/29147, 91923/29260,
92278/29373, 92633/29486, 92988/29599, 93343/29712, 93698/29825, 94053/29938,
94408/30051, 94763/30164, 95118/30277, 95473/30390, 95828/30503, 96183/30616,
96538/30729, 96893/30842, 97248/30955, 97603/31068, 97958/31181, 98313/31294,
98668/31407, 99023/31520, 99378/31633, 99733/31746, 100088/31859, 100443/31972,
100798/32085, 101153/32198, 101508/32311, 101863/32424, 102218/32537, 102573/32650,
102928/32763, 103283/32876, 103638/32989, 103993/33102, 104348/33215, 208341/66317,
312689/99532, 833719/265381, 1146408/364913, 3126535/995207,
4272943/1360120, 5419351/1725033, 42208400/13435351, 47627751/15160384,
53047102/16885417, 58466453/18610450, 63885804/20335483, 69305155/22060516,
74724506/23785549, 80143857/25510582, 

All these terms are correct, though if you increase MAX you start getting errors because of precision. I’m myself impressed with how many terms you get with only 13 convergents. (As you can see, there’s a small bug where it sometimes doesn’t print the very first “n/1” approximation, or prints it incorrectly — I leave it for you to fix!)

You can try with √2, whose continued fraction is [1; 2, 2, 2, 2…]:

% ./a.out 1.41421356237309504880
1.414213562373095
 
1:  1/1
2:  3/2
2:  7/5
2:  17/12
2:  41/29
2:  99/70
2:  239/169
2:  577/408
2:  1393/985
2:  3363/2378
2:  8119/5741
2:  19601/13860
2:  47321/33461
 
3/2, 4/3, 7/5, 17/12, 24/17, 41/29, 99/70, 140/99, 239/169, 577/408, 816/577, 1393/985, 3363/2378, 4756/3363, 8119/5741, 19601/13860, 47321/33461, 

Or the golden ratio φ = (1+√5)/2 whose continued fraction is [1; 1, 1, 1, …]:

% ./a.out 1.61803398874989484820
1.618033988749895
 
1:  1/1
1:  2/1
1:  3/2
1:  5/3
1:  8/5
1:  13/8
1:  21/13
1:  34/21
1:  55/34
1:  89/55
1:  144/89
1:  233/144
1:  377/233
 
2/1, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, 89/55, 144/89, 233/144, 377/233, 

(See the Fibonacci numbers? Here the convergents are all the approximants.)

Or with rational numbers like 4/3 = [1; 3]:

% ./a.out 1.33333333333333333333
1.333333333333333
 
1:  1/1
3:  4/3
 
3/2, 4/3, 

or 14/11 = [1; 3, 1, 2]:

% ./a.out 1.27272727272727272727
1.272727272727273
 
1:  1/1
3:  4/3
1:  5/4
2:  14/11
 
3/2, 4/3, 5/4, 9/7, 14/11, 

[2011-11-04: Fixed the bug and the description.]