Square Root: Digit by Digit Algorithm

[Thomas Klemm]

(11-25-2022 02:40 PM)ttw Wrote:  One can get (with a pretty large speed penalty) nice accuracy using continued fractions to represent integers.

Not sure if this is rather "representing real numbers" or maybe "fractions"?
Otherwise I don't understand the sentence and you could explain it in more detail.

(11-25-2022 02:40 PM)ttw Wrote:  Sqrt(2) is the continued fraction (1; 2,2,2,2,2,2...) and approximations have terms like 17/12

Can we digress any more?
C.f. Convergents of a Continued Fraction
The program can be used to get the approximations by entering the coefficients of a continued fraction one by one.

(11-25-2022 02:40 PM)ttw Wrote:  I haven't looked yet, but Gosper's algorithms for continued fractions may speed things up a bit.

We should be able to apply arbitrary (or maybe just analytic?) functions.
These can be approximated by polynomials.

I think the basic arithmetic with sequence of digits is easy.
Even the square root, as we have seen, can be taken digit by digit.
We can also invert any polynomial using the same method.
At least in a certain neighbourhood.

Is this also possible with continued fractions?

In the end, we might want a representation using digits rather than continued fractions, since their coefficients can be any integer, making interpretation difficult for us.