My Weblog

Blog about programming and math

Pell’s equation

Most of you are familier of pell’s equation .I found couple of question related to this problem and finally rewrote it in python as c code was not very much understandable.There are some good discussion about solving pells equation.If you want to solve the problems refer to these sites having very well organised theory about pells equation http://en.wikipedia.org/wiki/Pell’s_equation http://mathworld.wolfram.com/PellEquation.html . I came across this problem on project euler in many variants. This problem use the continued fraction theory.Python code for pell’s equation.

# To change this template, choose Tools | Templates
# and open the template in the editor.


import math
if __name__ == "__main__":
   while(True):
        D=int(raw_input())
        if(D==0):break
        L,a_0,p_0,q_0=[],int(math.sqrt(D)),0,1
        L.append(a_0)
        while(True):
            p_1=a_0*q_0-p_0
            q_1=(D-p_1**2)//q_0
            a_1=(L[0]+p_1)//q_1
            L.append(a_1)
            if(a_1==2*L[0]):break
            p_0,q_0,a_0=p_1,q_1,a_1;
        print L;
        r=len(L)-2
        if(r%2==0):
            r=2*r+1
            T=L;
            L[len(L):]=T[1:]
            
        a0=int(math.sqrt(D))
        p0,p1,p2=L[0],L[0]*L[1]+1,0;
        q0,q1,q2=1,L[1],0;
        for i in range(2,r+1):
            p2=p1*L[i]+p0
            q2=q1*L[i]+q0
            #print p2,' ',q2
            p0,p1=p1,p2
            q0,q1=q1,q2;

        print p1,' ',q1;
Advertisements

February 25, 2008 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: