[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]
Pell's equation: given a positive integer N, find a positive integer y such that Ny2+1 is a perfect square. i.e. x2 - Ny2 = 1. This is an old problem, first addressed in the 7th century and by an Indian mathematician. Euler wrongly attributed the study of the equation to John Pell, an amateur English mathematician, and the name stuck. Here's a site with more of the history of the problem.
I ran across it because several of the problems in the MathsChallenge Project Euler which require study of Pell's Equation and the related topics of continued fractions and square roots.
There is lots of information to digest on the web concerning the mathematics behind solving the equation, and a number of solution calculators, but I could not find any in Delphi, so here's my small contribution.
Briefly, every irrational number can be expressed as a fraction with an infinite number of terms of the form 1/(a0+1/(a1+1/(a2+1/(a3+.......)))). the an terms are called partial quotients and the values of the fraction as it is calculated are called the convergents. The convergents are denoted in various ways similar to (a0; [a1,a2,a3,a4....]). For any specific n, the convergent can also be expressed as the ratio of 2 integers, pn, qn which can be calculated as a function of the partial quotients. . For quadratic problems like this one, it is always the case that the partial quotients become cyclic at some point and once the cycle is determined, specific terms of the pn, qn series provide the minimal solution to Pell's equation. The term that provides the 1st solution depends on whether the cycle ,length is odd or even.
As the convergents are calculated, each pn / qn value provides a better approximation of the square root of the original N value. I added a button to show this approximation. Why is this so? Mathematically I can see that it's true but I haven't come up with a good intuitive explanation. Perhaps some viewer will help me out on this. In any event, it is true that the method does converge to the true sqrt(N).
Programmatically, the original problem was solved largely using information from Mathworld's Pell Equation page. The complication was that we need very large numbers to solve for some values of N or to get very accurate estimate of the square root. Our BigInt and BigFloat units add the necessary capability. They are included with the code downloads below.
Addendum April 12, 2005: For ease of maintenance, the source code for this program was uploaded today to excluded UBigIntsV2 which is now part of the DFF Library. If you want to recompile the program you will need both zip files.
Running/Exploring the Program
Download source code (Requires DFF Library source DFFLibV02 or later)
Copyright © 2000-2013, Gary Darby
All rights reserved.