Pell and Continued Fractions

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

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)

Download DFF Library Source  (DFFLibV14_12Nov2016 )

Download executable 

 

 

  

 

 

         

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2016, Gary Darby    All rights reserved.