Hacker News new | ask | show | jobs
by mci 3188 days ago
Ten years ago, I implemented Gosper's continued fraction arithmetics in Python: http://sun.aei.polsl.pl/~mciura/software/cf.py My module can also compute exp() and log() as well as trigonometric and inverse trigonometric functions. Here are slides from my presentation about it: http://sun.aei.polsl.pl/~mciura/cf.pdf
1 comments

Great, I will definitely have a look at it. Did you implement exp(x) for any continued fraction x?
Yes. The key to that is approximating reals by the second Ostrogradsky series (or, more properly, Ostrogradsky-Sierpiński series): x = ⎣x⎦ + 1/q₁ − 1/q₂ + 1/q₃ - 1/q₄ + ⋯, where the denominators qₖ are greedily chosen as the largest possible. The following formulas are true: exp(1/q) = [1; q−1, 1, 1, 3q−1, 1, 1, 5q-1,…], exp(x + y) = exp(x)exp(y), and exp(x - y) = exp(x)/exp(y). The algorithm keeps two most recent partial sums of the O-S series: sₖ₋₁ and sₖ. As long as the partial quotients of exp(sₖ₋₁) and exp(sₖ) are equal, it emits them; otherwise, it computes the next partial sum sₖ₊₁. Similar formulas work for tan(x).