Hacker News new | ask | show | jobs
by hakmem 3183 days ago
Great, I will definitely have a look at it. Did you implement exp(x) for any continued fraction x?
1 comments

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).