I was about to mention H J S Smith's algorithm for finding integer solutions to $x^2 + y^2 = p$ for $p \equiv 1$ mod 4; but this is referred to in a related thread at Applications of finite continued fractions
(Apologies if that thread is easily found from this one; but I wouldn't have noticed it without doing a Google search, and perhaps some other readers are equally inexperienced in StackOverflow ways or unobservant!)
Also, what about higher-dimensional continued fractions, expressed as matrix recurrence relations? I seem to recall that these can be used to find rational solutions of equations involving some kinds of cubic forms.