PQA algorithm

This algorithm due to Lagrange gives the expansion as a continued fraction of a quadratic number (u+√D)/v, with u, v, D integers, D not a square.

D :     u :     v :          (u=0, v=1 to solve x²-Dy²=±1)
Value of convergents     number of additional cycles

Working

The algorithm requires v dividing D-u².
If v doesn't divide D-u², we can replace u by u|v|, D by Dv² and v by v|v| then v|v| divides Dv²-u²v², although being the same quadratic number.

Let U0=u, V0=v, a=E[√D], With E[x]=integer part of x (ceil function).
And added variables X, Y, P    X-1=-u, X0=v     Y-1=1, Y0=0     P-1=0, P0=1

then repeat for i≥0:

    ai=E[(Ui+√D)/Vi]=E[(Ui+a)/Vi]
    Ui+1=aiVi-Ui     Vi+1=(D-Ui+1²)/Vi,
    (X,Y,P)i+1=ai(X,Y,P)i+(X,Y,P)i-1

until sequence Vn becomes periodic.
The ai are the terms of the continued fraction,   Pi/Yi are the convergents   and Xi²-DYi²=(-1)iV0Vi

 

Home Arithmetic Geometric Misc Topics Scripts Games Exercices Mail Version Française Previous topic Next topic