Midpoint criteria for solving Pell’s equation using the nearest square continued fraction

We derive midpoint criteria for solving Pell’s equation $x^2-Dy^2=\pm 1$, using the nearest square continued fraction expansion of $\sqrt {D}$. The period of the expansion is on average $70\%$ that of the regular continued fraction. We derive similar criteria for the diophantine equation $x^2-xy-\frac {(D-1)}{4}y^2=\pm 1$, where $D\equiv 1\pmod {4}$. We also present some numerical results and conclude with a comparison of the computational performance of the regular, nearest square and nearest integer continued fraction algorithms.