Square Root: Digit by Digit Algorithm

11252022, 07:05 PM
Post: #11




RE: Square Root: Digit by Digit Algorithm
(11252022 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. (11252022 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. (11252022 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. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)