← All writing Ancient algorithms, 15 min read

The chakravala method for Pell's equation, from Bhaskara II, in Python

Pell's equation solved by Bhaskara II's chakravala method (1150): the Sanskrit verses word by word, his N = 61 and N = 67 examples, and tested Python.

Find whole numbers x and y with x^2 - 61y^2 = 1. The smallest answer is x = 1,766,319,049 and y = 226,153,980, and Bhaskara II works exactly this case in his Bijaganita of 1150. In English this is Pell's equation, x^2 - N*y^2 = 1 for any N that is not a square, and his tool was the chakravala, a cycle whose rounds bring k, the right-hand side of x^2 - N*y^2 = k, down to 1.

The cycle is older than Bhaskara II. Its earliest known statement is in verses of Jayadeva, quoted in a commentary written in 1073. It runs on Brahmagupta's rule for combining solutions, from 628, and on the kuttaka, the first post in this series. Below are Bhaskara II's verses, translated word by word, both of his examples rerun, and a Python version tested against brute force and continued fractions (code on GitHub; series: Ancient algorithms, implemented).

What Pell's equation asks

Take N = 2. Then 3^2 - 2 × 2^2 = 9 - 8 = 1, so x = 3, y = 2 works. That one you can find by trying small numbers. Now take N = 61. Trying y = 1, 2, 3, ... you would reach the answer after 226 million tries.

The equation matters because a solution gives a fraction x/y very close to sqrt(N). From x^2 - N*y^2 = 1:

x2y2=N+1y2\frac{x^2}{y^2} = N + \frac{1}{y^2}

For N = 61 that fraction matches sqrt(61) to 17 decimal places. Solutions also come in endless families, because 2 solutions can be combined into a third, which is what Brahmagupta discovered.

In the Sanskrit texts the problem is vargaprakriti, the "square with a coefficient". Bhaskara II's own example asks for a square that, multiplied by 67 and increased by 1, gives a square, and the same for 61. In English the equation carries the name of John Pell.

Who wrote it, and when

  • Brahmagupta, Brahmasphutasiddhanta, chapter 18, written in 628 CE. He gives the rule of composition (bhavana) in verses 64 and 65, and rules that turn a solution for 4 or -4 into one for 1 in verses 67 and 68 (numbering of Dvivedin's 1902 edition, as in GRETIL). Colebrooke's 1817 translation numbers these sections 65 to 66, 69 and 71.
  • Jayadeva, before 1073. His own work is lost. Udayadivakara quotes 20 of his verses in the Sundari, a commentary on Bhaskara I's Laghubhaskariya written in 1073, and 15 of them state the cyclic method. K. S. Shukla first ascribed the method to Jayadeva, in 1954. Selenius (1975) puts Jayadeva "about 1000 or earlier", at least 100 years before Bhaskara II, and finds his method "essentially the same" as Bhaskara II's. Bhaskara II does not name him.
  • Bhaskara II, Bijaganita, chapter on vargaprakriti. He says he completed the Siddhantasiromani, of which the Bijaganita is a part, in Saka 1072, which is 1150 CE, and that he was born in Saka 1036. He states the cyclic method, says it is called chakravala ("They called this the circle"), and works 2 examples, N = 67 and N = 61.
  • H. T. Colebrooke, Algebra, with Arithmetic and Mensuration, from the Sanscrit of Brahmegupta and Bhascara (London, 1817). The first English translation of both texts, with notes from the Sanskrit commentators Suryadasa and Krishna. It is in the public domain, and I quote it below.

Chakravala means "circle" or "horizon". Colebrooke's note, from the commentator Suryadasa, explains the name: the method "proceeds as in a circle", from roots to a multiplier and back to roots.

The verses

The text is from the Bijaganita as edited by V. G. Apate (Poona, 1930), in Takao Hayashi's e-text on GRETIL, which marks this group as verse 75. Colebrooke numbers it sections 83 to 86. GRETIL prints the words split apart; I have joined them with the usual sound changes (sandhi). The meter is anushtubh: each verse has 4 quarter-verses (pada) of 8 syllables, printed as 2 lines.

ह्रस्वज्येष्ठपदक्षेपान् भाज्यप्रक्षेपभाजकान् ।
कृत्वा कल्प्यो गुणस्तत्र तथा प्रकृतितश्च्युते ॥

गुणवर्गे प्रकृत्यूनेऽथवाल्पं शेषकं यथा ।
तत्तु क्षेपहृतं क्षेपो व्यस्तः प्रकृतितश्च्युते ॥

गुणलब्धिः पदं ह्रस्वं ततो ज्येष्ठमतोऽसकृत् ।
त्यक्त्वा पूर्वपदक्षेपांश्चक्रवालमिदं जगुः ॥

चतुर्द्व्येकयुतावेवमभिन्ने भवतः पदे ।
चतुर्द्विक्षेपमूलाभ्यां रूपक्षेपार्थभावना ॥

hrasvajyeṣṭhapadakṣepān bhājyaprakṣepabhājakān |
kṛtvā kalpyo guṇas tatra tathā prakṛtitaś cyute ||

guṇavarge prakṛtyūne 'thavālpaṃ śeṣakaṃ yathā |
tat tu kṣepahṛtaṃ kṣepo vyastaḥ prakṛtitaś cyute ||

guṇalabdhiḥ padaṃ hrasvaṃ tato jyeṣṭham ato 'sakṛt |
tyaktvā pūrvapadakṣepāṃś cakravālam idaṃ jaguḥ ||

caturdvyekayutāv evam abhinne bhavataḥ pade |
caturdvikṣepamūlābhyāṃ rūpakṣepārthabhāvanā ||

Word by word

4 words recur. Hrasva ("short") or kanishtha ("least") is the smaller root, y. Jyeshtha ("greatest") is the larger root, x. Kshepa ("thrown in") is the additive, k in x^2 - N*y^2 = k. Prakriti ("nature", the given number) is N.

SanskritPartsMeaning
hrasvajyeṣṭhapadakṣepānhrasva + jyeṣṭha + pada + kṣepathe least root, greatest root and additive (object)
bhājyaprakṣepabhājakānbhājya + prakṣepa + bhājakaas dividend, additive and divisor
kṛtvākṛ, "to make"having made (them)
kalpyo guṇas tatrakalpya, guṇathere a multiplier is to be found (by the kuttaka)
tathā ... yathāin such a way ... that
prakṛtitaś cyute guṇavargeprakṛti, cyuta, guṇa + vargawhen the square of the multiplier is taken from N
prakṛtyūne 'thavāprakṛti + ūna, athavāor is reduced by N
alpaṃ śeṣakamalpa, śeṣakathe remainder is small
tat tu kṣepahṛtaṃ kṣepaḥkṣepa + hṛtathat, divided by the additive, is the new additive
vyastaḥ prakṛtitaś cyutevyastawith its sign reversed, when (the square) was taken from N
guṇalabdhiḥ padaṃ hrasvamguṇa + labdhi, pada, hrasvathe quotient that goes with the multiplier is the least root
tato jyeṣṭhamfrom it, the greatest root
ato 'sakṛtataḥ, asakṛtfrom these, again and again
tyaktvā pūrvapadakṣepāntyaktvā, pūrva + pada + kṣepasetting aside the previous roots and additive
cakravālam idaṃ jaguḥcakravāla, jaguḥthis they called the circle
caturdvyekayutaucatur + dvi + eka + yutawith additive 4, 2 or 1
abhinne bhavataḥ padeabhinna, padathe 2 roots come out whole
caturdvikṣepamūlābhyāmcatur + dvi + kṣepa + mūlafrom the roots for additive 4 or 2
rūpakṣepārthabhāvanārūpa + kṣepa + artha + bhāvanācomposition, for the sake of additive 1

My translation

Make the least root, the greatest root and the additive into the dividend, additive and divisor of a kuttaka, and find a multiplier from it, chosen so that its square minus N, or N minus its square, is small. That remainder divided by the additive is the new additive, with its sign reversed if the square was taken from N. The quotient that goes with the multiplier is the new least root, and from it comes the greatest root. Repeat this again and again, setting aside the previous roots and additive. They called this the circle. In this way roots come out whole for additive 4, 2 or 1, and composition turns roots for 4 or 2 into roots for 1.

Colebrooke's 1817 translation, which is in the public domain:

Making the "least" and "greatest" roots and additive, a dividend, additive and divisor, let the multiplier be thence found. The square of that multiplier being subtracted from the given coefficient, or this coefficient being subtracted from that square, (so as the remainder be small;) the remainder, divided by the original additive, is a new additive; which is reversed if the subtraction be [of the square] from the coefficient. The quotient corresponding to the multiplier [and found with it] will be the "least" root: whence the "greatest" root may be deduced. With these, the operation is repeated, setting aside the former roots and additive. This method mathematicians call that of the circle. Thus are integral roots found with four, two, or one [or other number, for] additive: and composition serves to deduce roots for additive unity, from those which answer to the additives four and two [or other number.]

H. T. Colebrooke, Algebra ... from the Sanscrit of Brahmegupta and Bhascara (1817), pp. 175 to 176

Composition, the other half

The verse depends on bhavana, Brahmagupta's composition, which Bhaskara II gives a few verses earlier (Colebrooke's sections 77 and 78). Write each solution as a triple: least root, greatest root, additive. From 2 triples (y1, x1, k1) and (y2, x2, k2) for the same N:

y=y1x2+y2x1,x=Ny1y2+x1x2,k=k1k2y = y_1 x_2 + y_2 x_1, \qquad x = N y_1 y_2 + x_1 x_2, \qquad k = k_1 k_2

is a new triple. In Colebrooke's words, the roots "are to be reciprocally multiplied crosswise" and "the product of the additives will be the [new] additive". Bhaskara II adds a second rule (section 79): divide both roots by any number q and the additive by q^2.

What the verses leave open

  1. Which multiplier. The kuttaka gives a whole family of multipliers, each differing from the next by the additive. The verse says to choose one whose square is close to N, without saying how close. I take the one that makes |m^2 - N| smallest. When 2 candidates tie, as for (1, 8, 6) with N = 58, the text does not choose; the code takes the one below sqrt(N).
  2. Where to start. The verse starts from any triple. Bhaskara II's examples take the least root as 1 and the greatest as the whole number whose square is nearest N.
  3. When to stop. The verse names additives 4, 2 and 1 as the stopping points. The commentator Krishna, in Colebrooke's notes, reads them as positive or negative, and Bhaskara II's examples stop at -2 and -4. Without the shortcut, the cycle reaches 1 by itself, and the code can run either way.
  4. Whether it always ends. Bhaskara II gives no proof that the cycle reaches additive 1 for every N. A. A. Krishnaswami Ayyangar proved it in 1929 to 1930, and Selenius (1975) notes that it also follows from the theory of continued fractions. I have not read Ayyangar's paper; this rests on Selenius and on Srinivas's summary of it. The benchmark here runs every non-square N below 10,000, and the tests check every one up to 200.

Working Bhaskara II's example, N = 67

Start with least root 1. The square nearest 67 is 64, so the greatest root is 8 and the additive is 64 - 67 = -3. Each row below is 1 round of the cycle:

RoundLeast root yGreatest root xAdditive kMultiplier mCheck: 67y^2 + k = x^2
start18-3767 - 3 = 64
1541651,675 + 6 = 1,681
21190-798,107 - 7 = 8,100
327221-248,843 - 2 = 48,841

Round 1 in detail, from the start row:

  • The kuttaka. We need m with 1 × m + 8 divisible by 3. That gives m = 1, 4, 7, 10, ....
  • The choice. 7^2 = 49 is closest to 67, so m = 7. Bhaskara II gets there from the kuttaka's answer by adding a multiple of the divisor, as Colebrooke's worked solution shows.
  • The new additive. (49 - 67) / -3 = 6. The square was taken from N, so the sign flips from -3 to 6.
  • The new least root. (1 × 7 + 8) / 3 = 5, the quotient of the kuttaka.
  • The new greatest root. (8 × 7 + 67 × 1) / 3 = 41, by the rule Colebrooke's note gives from the commentator Krishna.

After round 3 the additive is -2, so the shortcut applies. Compose (27, 221, -2) with itself:

  • y = 27 × 221 + 27 × 221 = 11,934
  • x = 67 × 27 × 27 + 221 × 221 = 97,684
  • k = (-2) × (-2) = 4

Divide both roots by 2 and the additive by 4: y = 5,967, x = 48,842, k = 1. Check: 48,842^2 - 67 × 5,967^2 = 1. Colebrooke's translation prints the same numbers, L 5967 G 48842 A 1.

The second example, N = 61

Start from (1, 8, 3). The kuttaka allows m = 1, 4, 7, 10, ..., and 7 is closest to sqrt(61). 1 round gives (5, 39, -4): 61 × 25 - 4 = 1,521 = 39^2.

Now Bhaskara II takes the shortcut through fractions:

  1. Divide by 2 (the additive by 4): (5/2, 39/2, -1).
  2. Compose it with itself: (195/2, 1523/2, 1). The additive is 1, but the roots are fractions.
  3. Compose that with (5/2, 39/2, -1) again: (3805, 29718, -1). Whole numbers.
  4. Compose (3805, 29718, -1) with itself: (226153980, 1766319049, 1).

Colebrooke prints L 3805 G 29718 for step 3 and L 226153980 G 1766319049 for the answer.

Brahmagupta has a direct formula for additive -4 (Brahmasphutasiddhanta 18.68). With greatest root x = 39, it gives ((x^2 + 3)(x^2 + 1)/2 - 1)(x^2 + 2) = 1,766,319,049 and (x^2 + 3)(x^2 + 1)/2 × 5 × 39 = 226,153,980, the same answer in 1 step.

The full cycle, without the shortcut, takes 13 rounds for N = 61. It passes through (3805, 29718, -1) on round 6, the same triple Bhaskara II reaches by composition.

Why the chakravala method works

Compose the current triple (y, x, k) with the trivial triple (1, m, m^2 - N), which holds for any m because N × 1 + (m^2 - N) = m^2:

(xm+Ny)2−N(ym+x)2=k(m2−N)(x m + N y)^2 - N (y m + x)^2 = k (m^2 - N)

Divide both sides by k^2:

(xm+Nyk)2−N(ym+xk)2=m2−Nk\left(\frac{x m + N y}{k}\right)^2 - N \left(\frac{y m + x}{k}\right)^2 = \frac{m^2 - N}{k}

This is a new triple, and the 3 parts are the 3 rules of the verse: new least root (ym + x)/k, new greatest root (xm + Ny)/k, new additive (m^2 - N)/k. The only question is whether they are whole numbers.

  • The least root is whole when k divides ym + x. That is a kuttaka problem, and it is why the verse sets up "dividend, additive, divisor".
  • The additive is then whole too. From x ≡ -ym (mod k) and x^2 - N y^2 = k, we get y^2 (m^2 - N) ≡ 0 (mod k). If y and k share no factor, k divides m^2 - N.
  • The greatest root follows: xm + Ny ≡ -y(m^2 - N) ≡ 0 (mod k).

The code checks that the starting roots share no factor, since the argument needs it. Bhaskara II's starting roots, 1 and the nearest square root, always pass.

The choice of m keeps the numbers small. The new additive is (m^2 - N)/k, so an m with m^2 close to N gives a small new additive. The valid values of m repeat every |k|, so one of them always lies within |k|/2 of sqrt(N).

The Python

A short version, without the shortcut, run until the additive is 1:

from math import isqrt


def chakravala(n: int) -> tuple[int, int]:
    """Smallest x, y > 0 with x*x - n*y*y == 1, by the cyclic method."""
    root = isqrt(n)
    if root * root == n:
        raise ValueError(f"n must not be a square, got {n}")
    y, x = 1, root if n - root * root <= (root + 1) ** 2 - n else root + 1
    k = x * x - n  # x^2 - n*y^2 = k
    while k != 1:
        step = abs(k)
        m = next(m for m in range(step) if (y * m + x) % step == 0)  # what the kuttaka finds
        m += (root - m) // step * step  # move m next to sqrt(n)
        if abs((m + step) ** 2 - n) < abs(m * m - n):
            m += step
        y, x, k = (y * m + x) // step, (x * m + n * y) // step, (m * m - n) // k
    return x, y


print(chakravala(61))  # (1766319049, 226153980)
print(chakravala(67))  # (48842, 5967)

The repo version finds the multiplier with the series' own kuttaka, pulverize from the kuttaka module. It records every round, takes a custom starting triple, and finishes by composition from additive -1, 2, -2, 4 or -4. From 4 or -4 it halves the triple and composes with the half until the roots are whole: for N = 61 that is 5 compositions to the 6th power, the same triple Bhaskara II reaches in 3. From a custom start the answer can be a larger solution, for example (70, 99) for N = 2 from (5, 7, -1). The tests check:

  • the rounds for N = 67, triple by triple and multiplier by multiplier, against Colebrooke's translation;
  • the composition and halving that give (5967, 48842, 1);
  • the route for N = 61 through (5/2, 39/2, -1) and (3805, 29718, -1) to (226153980, 1766319049, 1);
  • Bhaskara II's composition examples for N = 8 and N = 11 (Colebrooke, section 82);
  • brute-force search for every non-square N below 61;
  • property tests with Hypothesis: the cycle matches the continued-fraction solution for random N up to 200; the shortcut gives the same answer as the full cycle; every round keeps N y^2 + k = x^2; composition keeps the identity for random triples; and any coprime starting triple still reaches a solution.

Against continued fractions

The textbook method today expands sqrt(N) as a continued fraction and tests each convergent p/q until p^2 - N q^2 = 1. The first convergent that works gives the smallest solution, and the chakravala lands on the same one in every case I tested.

I counted chakravala rounds and continued-fraction steps for each method, with benchmarks/chakravala_vs_continued_fraction.py:

NRounds, with shortcutRounds, full cycleContinued-fraction stepsy
13259180
6111321226,153,980
673795,967
944915221,064
1093212915,140,424,455,100
18132941183,567,298,683,461,940
99121435912,055,735,790,331,359,447,442,538,767

Summed over every non-square N below each limit:

N belowRounds, with shortcutRounds, full cycleContinued-fraction stepsFull cycle / continued fraction
100842403860.622
1,0004,0497,42711,0860.670
10,000131,507216,352316,0680.685
Bar chart of total steps for the 968 non-square N below 1,000: continued fractions 11,086, the chakravala 7,427, and the chakravala with Bhaskara II's shortcut 4,049. Bar chart of total steps for the 968 non-square N below 1,000: continued fractions 11,086, the chakravala 7,427, and the chakravala with Bhaskara II's shortcut 4,049.

The full cycle needs about two-thirds of the steps. Letting m^2 fall on either side of N lets the cycle skip convergents: where the continued fraction has a run of partial quotients equal to 1, the chakravala skips about half of them (Srinivas 2013, after Selenius's papers of 1960 to 1963). Srinivas cites Matthews and others (2010), who estimate the ratio of the 2 cycle lengths at log2 of the golden ratio, about 0.694, close to the 0.685 measured here. Bhaskara II's shortcut cuts the count further: for N = 61 it replaces 12 of the 13 rounds with 3 compositions. Each round does more arithmetic than a continued-fraction step, so these are step counts and say less about running time.1

Parallels and lineage

  • Brahmagupta (628). Composition, and the formulas for additives 4 and -4. His chapter 18, as Colebrooke translates it, does not state a cycle.
  • Fermat, Brouncker, Wallis (1657). Colebrooke (1817) records that Fermat posed the problem as a challenge in 1657, and that William Brouncker and John Wallis answered it. He adds that Bhaskara II's rule for fractional solutions (his sections 80 to 81) is "exactly the same" as Brouncker's.
  • Euler and Lagrange. Colebrooke credits Euler with seeing that this equation underlies all quadratic indeterminate problems, and Lagrange with the first proof that it always has a solution in whole numbers, in work of 1767 to 1769.

What is debated

  • How Bhaskara II chose m. "So that the remainder is small" allows more than 1 rule. The code minimizes |m^2 - N|, and Bhaskara II's 2 worked examples match it at every round.
  • The name. Euler called it Pell's equation, and the usual explanation is that he confused Brouncker, who solved it, with John Pell, whose only known link to it is his help with an algebra book by Rahn that discusses it (MacTutor). Selenius (1975) suggested "Jayadeva-Bhaskara equation" instead.

Key takeaways

  • Pell's equation, x^2 - N y^2 = 1, is vargaprakriti in Sanskrit. Brahmagupta (628) found how to combine solutions. The chakravala, a cycle that always reaches a solution, is first attested in Jayadeva's verses, quoted in 1073; Bhaskara II's Bijaganita (1150) is the version used here.
  • Each round composes the current triple with (1, m, m^2 - N) and divides by the additive. The kuttaka picks m so the division is exact, and m^2 close to N keeps the numbers small.
  • Bhaskara II's examples, N = 67 and N = 61, rerun exactly in Python: (48842, 5967) and (1766319049, 226153980).
  • The full cycle takes about two-thirds of the continued-fraction steps for N below 10,000.
  • The code, tests and benchmark are in ancient-algorithms. Next: the katapayadi system, the letter code Kerala astronomers used to write numbers in verse.

Sources

Footnotes

  1. I counted steps, which do not depend on the machine or the Python version. The numbers grow with each round: for N = 991, y has 29 digits. ↩

Common questions

What is the chakravala method?↓

The chakravala (cakravāla, 'circle') is a cyclic algorithm for whole-number solutions of Pell's equation, x^2 - Ny^2 = 1. Its earliest known statement is by Jayadeva, quoted in a commentary written in 1073; Bhaskara II states it in his Bijaganita (1150). Each round takes a solution of x^2 - Ny^2 = k, uses the kuttaka to choose a multiplier m with m^2 close to N, and produces a new solution with a smaller k. When k reaches 1, -1, 2, -2, 4 or -4, Brahmagupta's composition finishes the job.

How does the chakravala method work for N = 61?↓

Start from 8^2 - 61 × 1^2 = 3. The multiplier 7 gives 39^2 - 61 × 5^2 = -4. Halve both numbers to get a fractional solution with -1, and compose it with itself until the numbers are whole: 29718^2 - 61 × 3805^2 = -1. Composing that with itself gives x = 1,766,319,049 and y = 226,153,980.

Is the chakravala faster than continued fractions?↓

It needs fewer steps: in my benchmark the full cycle took about two-thirds of the continued-fraction steps for N below 10,000. Each chakravala round does more arithmetic than a continued-fraction step, so the step count says less about running time.

Who was Bhaskara II?↓

Bhaskara II (Bhāskarācārya) was an Indian astronomer and mathematician who completed the Siddhantasiromani in Saka 1072, which is 1150 CE, by his own statement. The Bijaganita (algebra) and the Lilavati (arithmetic) are parts of it. He says he was born in Saka 1036 (1114 CE).

Share this
← More writing Get in touch